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?

Improve this question
$\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$
    – Fedor Petrov
    Commented 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$
    – darij grinberg
    Commented 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$
    – darij grinberg
    Commented Aug 13, 2015 at 12:07

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – darij grinberg
    Commented 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$
    – darij grinberg
    Commented 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$
    – Fedor Petrov
    Commented 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$
    – darij grinberg
    Commented May 23, 2011 at 0:12
  • $\begingroup$ yes, but RHS must be $\min(r,a+b)$ $\endgroup$
    – Fedor Petrov
    Commented May 23, 2011 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .