Please note that I'm just looking for a partial answer to this question.

Definition Let $G=U\cup V$ be a bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. $K_{p,q}$ is bipartite graph where every vertex in $U$ is connected to every vertex in $V$.

Background It is known that the spectrum of the complete bipartite graph $K_{p,p}$ is $(p, -p,0\ldots,0)$ (see Theorem 3.4 in this book).

Let $E'=\{e_1,\ldots,e_l\}\subset K_{p,p}$, where $l\leq \frac{|V(K_{p,p})|}{2} =p$
Let $G'$ be the graph obtain from $K_{p,p}$ in the following way:
That means $G'$ is the graph obtained from $K_{p,p}$ by removing "relatively" small number of edges (since $|E(K_{p,p})|=p^2$).

Is it possible to calculate the spectrum of $G'$ if $E'$ satisfies certain conditions? for example one of the following:
-$E'$ is a perfect matching of $K_{p,p}$
-$|E'|\leq 4$.
Is there any work in this direction?

Ideas that could help:
1-If $\lambda$ is eigenvalue of $G'$ with multiplicity $l$ then $-\lambda$ is also eigenvalue of $G'$ with multiplicity $l$ (since $G'$ is bipartite graph, see Lemma 3.13 and Theorem 3.14 in this book).
2-From here we know that if $l$ vertices have the same neighbourhood (that is $N(u_1)=N(u_2)=...=N(u_l)$), then $0$ is eigenvalue with multiplicity at least $l-1$.
3-Since $0$ is eigenvalue of $K_{p,p}$ with very high multiplicity (that is $|V(K_{p,p})|-2$), then I guess that by removing small number of edges from $K_{p,p}$, $0$ will still be eigenvalue with high multiplicity. 4-Interlacing theorem could help in commutating the eigenvalues of $G'$.

Any idea will be useful!


If $E'$ is a perfect matching then there are eigenvalues $\pm(p-1)$, each with multiplicity $1$, and $\pm 1$, each with multiplicity $p-1$.

To see this, recall that the eigenspaces for $K_{p,p}$ are:

constant functions on the vertices: dimension $1$, eigenvalue $p$;
functions taking $U$ to $c$ and $V$ to $-c$: dimension $1$, eigenvalue $-p$;
functions that sum to $0$ on both $U$ and $V$: dimension $2p-2$, eigenvalue $0$.

(We regard the adjacency matrix as acting on functions $U \cup V \to \bf R$.)

On $G'$, the first two spaces still consist of eigenvectors, with eigenvalues $p-1$ and $-(p-1)$ respectively. The last space splits into two eigenspaces, each of dimension $p-1$: on one, corresponding vertices of $U$ and $V$ map to the same number; on the other, the images of corresponding vertices sum to zero. These eigenspaces have eigenvalues $-1$ and $+1$ respectively. $\Box$

  • $\begingroup$ Thanks! I edited just to correct a typo: in $K_{p,p}$ the $0$-eigenspace has dimension $2p-2$, not $p-2$ $\endgroup$ – Noam D. Elkies May 15 '16 at 18:05

Your Answer

