4
$\begingroup$

I'm studying graph theory and the follow question is driving me crazy. Any hint in any direction would be appreciated.

Here is the question:

Let $G = G[X, Y]$ be a bipartite graph in which each vertex in $X$ is of odd degree. Suppose that any two distinct vertices of $X$ have an even number of common neighbours. Show that $G$ has matching covering every vertex of $X$.

$\endgroup$
  • 2
    $\begingroup$ Curiously, this is related to the "Clubs of Oddtown" problem. Every club in Oddtown has an odd number of members, and every two distinct clubs have an even number of members in common (your $X$ is the set of clubs, $Y$ the set of residents of Oddtown). The question usually asked is to show that there can't be more clubs than residents. It forms Chapter 3 of Matousek, Thirty-three Miniatures. The matching covering question doesn't come up, but still the discussion might be helpful. $\endgroup$ – Gerry Myerson Oct 14 '12 at 22:38
  • $\begingroup$ Also posted, without advising either site, to MO: mathoverflow.net/questions/109633/matching-in-bipartite-graphs --- very bad form. $\endgroup$ – Gerry Myerson Oct 15 '12 at 4:19
1
$\begingroup$

Hint for one possible solution:

Consider the adjacency matrix $M\in\Bbb F_2^{|X|\times|Y|}$ of the bipartite graph, i.e. $$M_{x,y}:=\left\{ \begin{align} 1 & \text{ if }x,y \text{ are adjacent} \\ 0 & \text{ else} \end{align} \right. $$ then try to prove, it has rank $|X|$, and then, I think, using Gaussian elimination (perhaps only on the selected linearly independent columns) would produce a proper matching..

$\endgroup$
3
$\begingroup$

The first section of this PDF (Lecture 1 from the HS11 class "Linear Algebra Methods in Combinatorics" by Penna and Hruz at ETH Zürich) gives a brief solution of the Clubs of Oddtown problem mentioned by Gerry Myerson in the comments; this PDF ("Linear Methods in Discrete Mathematics" by Dan Farkas) gives a much more extensive introduction to the necessary linear algebra and goes on to deal with much more difficult problems as well.

Let $A$ be the adjacency matrix of $G$, with rows indexed by $X$ and columns by $Y$. The material in the references (specifically, the analysis of the Oddtown problem) shows that the rows of $A$ are linearly independent as vectors in $\Bbb F_2^{|Y|}$, so the rank of $A$ is $|X|$. $A$ therefore contains an $|X|\times|X|$ invertible submatrix $B$. I’ve not entirely thought through the details, but I’d try to show that this submatrix must contain a permutation matrix, which will give you the desired matching. It may be useful to row-reduce $B$; note that this is exceptionally simple over $\Bbb F_2$.

Added: Just look at the determinant of $B$ as defined by the Leibniz formula: one of the terms must be non-zero.

$\endgroup$
  • $\begingroup$ Very nice! ${}$ $\endgroup$ – joriki Oct 15 '12 at 1:45

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.