Interlacing Theorem
Thm(Eigenvalue Interlacing Theorem)
Let A be a symmetric real $n\times n$ and let B be an m-th principal submatrix(obtained by deleting both i-th row and i-th column for some n-m values of i). Suppose A has eigenvalues $\lambda_1\geq\cdots\geq\lambda_n$, and B has eigenvalues $\beta_1\geq\cdots\geq\beta_m$.Then
Further,if $m=n-1$, then
Proof
Without loss of generality, assume that $A=\left[\begin{matrix}B&X\X^T&C\end{matrix}\right]$ and $\lambda_i\vec{x}_i=A\vec{x}_i$ for $i\in[n]$ such that all $\vec{x}_i$ are linearly independent and normalized, and $\beta_j\vec{y}_j=B\vec{y}_j$ for $j\in[m]$ s.t. all $\vec{y}_j$ are linearly independent and normalized.
Let $V=span{\vec{x}_k,\cdots,\vec{x}_n}$ and $W=span{\vec{y}_1,\cdots,\vec{y}_k}$. Extend $W$ to a subspace of $\mathbb{R}^n$ s.t.
Then $\dim(V)=n-k+1$ and $\dim(\widetilde{W})=\dim(W)=k$
Note that both $V\subset \mathbb{R}^n$ and $\widetilde{W}\subset \mathbb{R}^n$, and
It follows that there exists a vector $\tilde{w}$ which satisfies $\tilde{w}\in V\cap\widetilde{W}$.
$\lambda_k$ is the largest eigenvalue with an eigenvector in V; $\beta_k$ is the smallest eigenvalue with an eigenvector in W.Therefore,
So we have $\lambda_k\geq\beta_k$.
On the other hand, let $V=span{\vec{x}1,\cdots,\vec{x}{k+n-m}}$ (i.e. $\lambda_{k+n-m}$ is the smallest eigenvalue with an eigenvector in V) and $W=span{\vec{y}1,\cdots,\vec{y}{k+n-m}}$ (i.e. $\beta_k$ is the largest eigenvalue with an eigenvector in W).
Let $\widetilde{W}=\left{\left.\left[\begin{matrix}\vec{w}\0\end{matrix}\right]\right|\vec{w}\in W\right}\subset\mathbb{R}^n$. Then $\dim(V)=k+n-m$ and $\dim(\widetilde{W})=m-k+1$.
Therefore, $\dim(V)+\dim(\widetilde{W})=n-k+1+k=n+1>\dim(\mathbb{R}^n)$
It follows that there exists a vector $\tilde{w}$ which satisfies $\tilde{w}\in V\cap\widetilde{W}$.
So $\lambda_{k+n-m}\leq\beta_k$.
Bounding degree of induced subgraph
Thm(Huang,2019) Let H be an induced subgraph of the n-dimensional hypercube $Q_n$. If $|V(H)|>2^{n-1}=\frac{|V(Q)|}{2}$,then $\Delta (H)\geq\sqrt{n}$
**n-dimensional hypercube $Q_n$**
The adjacency matrix of n-dimensional hypercube $Q_n$ satisfies the following
If we give every edge in n-dimensional hypercube $Q_n$ a sign, we can get a signed adjacency matrix.
Lemma The signed n-dimensional hypercube with adjacency matrix $S_n$ has an eigenvalue $\sqrt{n}$ of multiplicity $2^{n-1}$ and eigenvalue $-\sqrt{n}$ with multiplicity $2^{n-1}$
Proof
claim: $S_n^2=nI$
If $n=1$, $S1=\left[\begin{matrix}0&1\1&0\end{matrix}\right],S_1^2=I$. Assume that $S{n-1}^2=(n-1)I$
Then
So claim holds.
Note that $nI$ has eigenvalues n. Therefore, $S_n$ has eigenvalues either $\sqrt{n}$ or $-\sqrt{n}$.
Since the trace of $S_n$ is 0, $S_n$ has eigenvalues $\sqrt{n}$ of multiplicity $2^{n-1}$ and $-\sqrt{n}$ with multiplicity $2^{n-1}$.
Proof of Huang’s Theorem
Let H be a induced subgraph of $Q_n$ with more than $2^{n-1}$ vertices. It suffices to show that every subgraph H with exactly $2^{n-1}+1$ vertices has maximum degree at least $\sqrt{n}$.
Let $(Q_n,\sigma)$ be the signed graph with adjacency matrix $S_n$ as defined above. Then $(H,\sigma)$ is a signed induced subgraph of $(Q_n,\sigma)$, whose adjacency matrix $A$ is a $(2^{n-1}+1)$-principle submatrix of $S_n$.
By the proposition (i.e. $|\lambda(H,\sigma)|\leq\Delta (H)$ and the interlacing theorem
$\lambda_1(A)$ means the largest eigenvalue of A.
Unfriendly partitions of subcubic graphs
A graph G is subcubic if the maximum degree of G is at most 3. ($\Delta(G)\leq3$)
Conjecture (Pisanski and Fowler,2012)All subcubic graphs except finitely many have median eigenvalues in the interval$[-1,1]$. There exists a constant c such that if $|V(G)|\geq|c|$, then $\lambda_{\lfloor\frac{\lambda+1}{2}\rfloor},\lambda_{\lceil\frac{\lambda+1}{2}\rceil}\in[-1,1]$
Let G be a graph. A partition $(X,Y)$ of $V(G)$ is unfriendly if every vertex has at least the same number of neighbors in the other subset as in it owns.
In other words, for every vertex v of G, $d_{G[x]}(v)\leq\frac{1}{2}d_G(v)$ and $d_{G[Y]}(v)\leq\frac{1}{2}d_G(v)$If $(X,Y)$ is an unfriendly partition of a subcubic graph $G$, then the maximum degree of the induced subgraph $G[X]$ and $G[Y]$ is at most 1.
An unfriendly partition $(X,Y)$ is unbalanced if $|X|\not=|Y|$
A partition is a bisection if $\Big||X|-|Y|\Big|\leq1$
Proposition Let G be a subcubic graph with n vertices. If G has an unbalanced unfriendly partition, then
Proof
Let G be a subcubic graph with n vertices and $(X,Y)$ be an unbalanced unfriendly partition.
Without loss of generality, assume that $|X|>|Y|$
Then $\lambda_1(X)\leq\Delta(X)\leq1$ and $\lambda_1(Y)\leq\Delta(Y)\leq1$. So both X and Y are bipartite.
All eigenvalues of $X$ and $Y$ belong to $[-1,1]$. Since $|X|>|Y|$, it holds that
It follows that the interlacing theorem that
The completes the proof.
Q: Does every subcubic graph have an unbalanced unfriendly partition? A: No
