Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.

Let $G$ be a bipartite graph, i. e., a graph such that the set of its vertices is the union of two sets $A$ and $B$, and each edge of the graph $G$ connects a vertex from $A$ with a vertex from $B$. For every subset $U$ of $A$ and every integer $k$, let $N_{k}\left(U\right)$ denote the set of all vertices from $B$ which have at least $k$ neighbours in the set $U$. Assume that $\left|A\right|=\left|B\right|$.

Some matchings of $G$ are called disjoint if there is no edge common to two or more of these matchings.

Let $m$ be a positive integer. Prove or disprove that the graph $G$ has $m$ disjoint perfect matchings if and only if the inequality $\left|N_{1}\left(U\right)\right|+\left|N_{2}\left(U\right)\right|+...+\left|N_{m}\left(U\right)\right|\geq m\left|U\right|$ holds for every subset $U$ of $A$.

Note that probably the assumption $\left|A\right|=\left|B\right|$ can be dropped if we replace "perfect matchings" by "$A$-complete matchings" (i. e., every vertex of $A$ is matched in every of these matchings). Also note that the "only if" direction is easy. Finally, of course, for $m=1$, this is Hall's marriage theorem.

The fact that I have posted the above problem on MathLinks in 2007 speaks for it being easy, but the fact that I have always been too lazy to write up my solution speaks for it being wrong. I have tried the obvious induction approach now, but I fail to obtain a reasonable inequality for $m-1$ instead of $m$ after deleting the first perfect matching. Any ideas?

share|improve this question
    
If I remember well, for $m=2$ it is proved here onlinelibrary.wiley.com/doi/10.1002/jgt.3190110102/abstract but I do not have the access for larger $m$ there was counterexample, or the proof, or it was called open, one of these - I also do not remember:) –  Fedor Petrov May 17 '11 at 9:21
    
Thanks for the link. It calls my assertion the Ore-Ryser theorem, so apparently it is not open. Finding a proof which does not use max-flow-min-cut seems a different problem, though. –  darij grinberg May 17 '11 at 10:08

2 Answers 2

up vote 5 down vote accepted

Take the general Ore-Ryser theorem:

Let $G$ be bipartite graph with vertex set $V=X\coprod Y$ ($X$, $Y$ parts) and $f:V\rightarrow \{0,1,2,\dots\}$ be a function such that $f\left(x\right)\leq\left(\text{degree of }x\right)$ for every $x\in X$. Then there exists a subgraph of $G$ (obtained from $G$ by removing some edges, not vertices), for which $f$ is degree function, if and only if for any $Y_1\subset Y$ one has $$ \sum_{y\in Y_1} f(y)\leq \sum_{x\in X} \min(f(x),d_{Y_1}(x)), $$ and this becomes an equality for $Y=Y_1$ (not necessarily only for $Y=Y_1$). Here, $d_{Y_1}(x)$ denotes the number of neighbors of $x$ in $Y_1$.

If $f(v)\equiv m$, it is easy to verify that we get your problem (or, strictly speaking, we get that one has a $m$-regular subgraph, but it is well known that it factors onto $m$ 1-regular subgraphs).

And the Ore-Ryser theorem may be proved by easy induction, the same as is used for the Hall marriage problem. Either there exists some nonempty $Y_1\ne Y$, for which the equality occurs, then we apply the induction propose for $X$ and $Y_1$ (with $f$ changed on $X$ to $\min(f,d_{Y_1})$) and then to $X$ and $Y\setminus Y_1$. Or we have strict inequalities for all nonempty $Y_1\ne Y$, then take any edge $xy$, remove it and replace $f(x)$ to $f(x)-1$, $f(y)$ to $f(y)-1$.

share|improve this answer
    
Hi Fedor, thanks a lot. This sounds like a beautiful proof. I haven't understood it in detail yet, but I have edited it to make some things (hopefully) clearer (you can check the changelog to see what I did there). At least I see that this theorem follows from max-flow-min-cut! –  darij grinberg May 17 '11 at 18:16
    
Sorry, I don't get it. More precisely, I don't get the case when some nonempty $Y_1\neq Y$ exists for which the equality occurs. When you apply the induction assumption to $X$ and $Y\setminus Y_1$, how do you modify $f$ on $X$ ? Because if you don't modify $f$ on $X$, then upon combining these two subgraphs you don't get the right degree function. Or am I mistaken here? –  darij grinberg May 22 '11 at 9:19
1  
denote $Y_2=Y\setminus Y_1$, $G_{i}$ is the graph formed by vertices $X$ and $Y_i$ ($i=1,2$). Clearly, if one constructs $f$-subgraph for $G$, she must take $f_1(x):=\min(f(x),d_{Y_1}(x))$ edges from $x$ to $Y_1$ for any $x\in X$. So, change $f$ to $f_1$ on $X$ and apply induction propose for $G_1$, then change $f(x)$ to $f_2(x):=f(x)-f_1(x)$ on $X$ and apply induction propose for $X$ and $Y_2$. We may do it, since if some $Y_3\subset Y_2$ contradicts to our main inequality in $G_2$, then $Y_1\cup Y_3$ contradicts in $G$ (straightforward check). –  Fedor Petrov May 22 '11 at 10:20
    
Thanks, I see it now. The straightforward check you have in mind uses the identity $\min\left(r-\min\left(r,a\right),b\right)+\min\left(r,a\right)=\min\left(r,b\ri‌​ght)$ for any nonnegative reals $r$, $a$, $b$. –  darij grinberg May 23 '11 at 0:12
    
yes, but RHS must be $\min(r,a+b)$ –  Fedor Petrov May 23 '11 at 17:02

Fedor, has this proof been published anywhere? I've been searching for an elementary proof (i.e. one not using Tutte's f-factor theorem) in print to reference. Also, do you happen to know why Ryser is given credit for the theorem? Many thanks.

share|improve this answer
    
I think there is a mess of different statements that are all called Ore-Ryser theorem, and are all interrelated. As for elementary proofs, probably the simplest one is by using the max flow min cut theorem (which is very elementary in its own), and I remember seeing that in print. Sorry for not being more precise out of lack of time; I believe Fedor could help a lot more than me anyway... –  darij grinberg Nov 14 '11 at 17:53
    
This should be a comment rather than an answer. –  Julian Kuelshammer Jun 25 '13 at 7:32

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.