8
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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:) $\endgroup$ May 17, 2011 at 9:21
  • $\begingroup$ 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. $\endgroup$ May 17, 2011 at 10:08
  • 2
    $\begingroup$ I have accidentally found a source for this result: Kenneth Lebensold, Disjoint matchings of graphs, Journal of Combinatorial Theory, Series B, Volume 22, Issue 3, June 1977, Pages 207--210, sciencedirect.com/science/article/pii/0095895677900661 . $\endgroup$ Aug 13, 2015 at 12:07

1 Answer 1

8
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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! $\endgroup$ May 17, 2011 at 18:16
  • $\begingroup$ 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? $\endgroup$ May 22, 2011 at 9:19
  • 1
    $\begingroup$ 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). $\endgroup$ May 22, 2011 at 10:20
  • $\begingroup$ 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\right)$ for any nonnegative reals $r$, $a$, $b$. $\endgroup$ May 23, 2011 at 0:12
  • $\begingroup$ yes, but RHS must be $\min(r,a+b)$ $\endgroup$ May 23, 2011 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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