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)?

  • 2
    $\begingroup$ maximal or maximum ? $\endgroup$ – Suresh Venkat Nov 29 '11 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 Moeller Nov 29 '11 at 21:47
  • 4
    $\begingroup$ @JohnMoeller: Maybe this should be an answer ? $\endgroup$ – Suresh Venkat Nov 30 '11 at 3:27
  • $\begingroup$ @JohnMoeller Do you mean spectrum of the adjacency matrix? $\endgroup$ – v s Nov 30 '11 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 Moeller Nov 30 '11 at 18:41

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.


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.