Condition on a bipartite graph to have an $m$-factor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:24:55Z http://mathoverflow.net/feeds/question/65211 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65211/condition-on-a-bipartite-graph-to-have-an-m-factor Condition on a bipartite graph to have an $m$-factor darij grinberg 2011-05-17T08:36:19Z 2011-11-14T15:45:57Z <p>This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&amp;t=137128" rel="nofollow">I proposed on MathLinks long ago</a>.</p> <p>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|$.</p> <p>Some matchings of $G$ are called <em>disjoint</em> if there is no edge common to two or more of these matchings.</p> <p>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$.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/65211/condition-on-a-bipartite-graph-to-have-an-m-factor/65224#65224 Answer by Fedor Petrov for Condition on a bipartite graph to have an $m$-factor Fedor Petrov 2011-05-17T11:43:31Z 2011-06-17T19:04:14Z <p>Take the general Ore-Ryser theorem:</p> <p>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$.</p> <p>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). </p> <p>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$.</p> http://mathoverflow.net/questions/65211/condition-on-a-bipartite-graph-to-have-an-m-factor/80901#80901 Answer by unknown (google) for Condition on a bipartite graph to have an $m$-factor unknown (google) 2011-11-14T15:45:57Z 2011-11-14T15:45:57Z <p>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.</p>