<p>As an expansion of the comment I made above, here it is in answer form. </p>

<p>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.</p>

<p>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)$. </p>

<p>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.</p>

CC BY-SA 3.0
2011-12-01T01:48:27.087Z
2011-12-01T01:48:27.087Z
Josephine Moeller
<p>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)?</p>

CC BY-SA 3.0
2011-11-29T16:44:59.170Z
maximal or maximum ?
Suresh Venkat
CC BY-SA 3.0
2011-11-29T21:47:39.110Z
$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.
Josephine Moeller
CC BY-SA 3.0
2011-11-30T03:27:01.343Z
@JohnMoeller: Maybe this should be an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-11-30T18:26:49.907Z
@JohnMoeller Do you mean spectrum of the adjacency matrix?
v s
CC BY-SA 3.0
2011-11-30T18:41:09.540Z
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.
Josephine Moeller
<graph-theory><co.combinatorics><spectral-graph-theory><matching>
Bipartite maximum matching size from eigenvalues
v s
# Bipartite maximum matching size from eigenvalues

(Asked by: username_0 on 2011-11-29)

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

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory, matching
> **Comments:**
> **username_1**: maximal or maximum ?  
> **username_2**: $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.  
> **username_1**: @JohnMoeller: Maybe this should be an answer ?  
> **username_0**: @JohnMoeller Do you mean spectrum of the adjacency matrix?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-12-01. Score: 7 | Accepted answer

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.


---

