Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm new here. Well, actually 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]$ a bipartite graph in which each vertex in X is of odd degree. Suppose at any two vertices of X have an even number of common neighbours. Show that G has matching covering every vertex of X.

share|improve this question
2  
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. –  Gerry Myerson Oct 14 '12 at 22:38
    
Also posted, without advising either site, to MO: mathoverflow.net/questions/109633/matching-in-bipartite-graphs --- very bad form. –  Gerry Myerson Oct 15 '12 at 4:19

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

The first section of this PDF gives a brief solution of the Clubs of Oddtown problem mentioned by Gerry Myerson in the comments; this PDF 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 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.

share|improve this answer
    
Very nice! ${}$ –  joriki Oct 15 '12 at 1:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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