Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's adjacency matrix's or its Laplacian's eigenvalues (without using an algorithm to calculate explicitly a maximum matching)?
5
-
2$\begingroup$ maximal or maximum ? $\endgroup$– Suresh VenkatNov 29, 2011 at 16:44
-
10$\begingroup$ $K_{1,2n-1}$ and $K_{n,n}$ share the same spectrum, so I doubt that there's anything that you can conclude based just on the eigenvalues. $\endgroup$– Josephine MoellerNov 29, 2011 at 21:47
-
4$\begingroup$ @JohnMoeller: Maybe this should be an answer ? $\endgroup$– Suresh VenkatNov 30, 2011 at 3:27
-
$\begingroup$ @JohnMoeller Do you mean spectrum of the adjacency matrix? $\endgroup$– v sNov 30, 2011 at 18:26
-
2$\begingroup$ Spectrum of the adjacency matrix or its Laplacian. I'll write this up as an answer but I don't have time at the moment. $\endgroup$– Josephine MoellerNov 30, 2011 at 18:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
As an expansion of the comment I made above, here it is in answer form.
I'll just talk about maximum matchings, since that will demonstrate the point. Suppose that we consider both $K_{1,2n-1}$ and $K_{n,n}$. The first has a maximum matching of size 1, since it's a star graph, and the other has $n$ for obvious reasons.
It's easiest to reason about the normalized adjacency matrix $D^{-1}A$, but the same applies to the normalized Laplacian. Both of these graphs have an eigenvalue of 1, because every connected graph does. The corresponding eigenvector is the vector of all ones (this is easy enough to see because $A\mathbf{1} = D\mathbf{1}$). Since they're bipartite, they both also have eigenvalues of -1, with eigenvectors corresponding to being negative on one side and positive on the other: e.g. the column vector with parts $\mathbf{1}_L$ and $-\mathbf{1}_R)$.
The trick is to see that the other eigenvalues are zero. But this should be obvious, because the adjacency matrix of a complete bipartite graph only has two independent rows/columns. Any others are just copies of these.
