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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.