Timeline for Condition on a bipartite graph to have an $m$-factor
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2022 at 11:15 | comment | added | Vincent Pfenninger | This paper combinatorics.org/ojs/index.php/eljc/article/view/v20i3p11 provides references about the Ore-Ryser theorem and says that it was called the Ore-Ryser theorem by Katerinis who however did not provide a reference to Ryser's work. | |
| Nov 14, 2011 at 17:53 | comment | added | darij grinberg | 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... | |
| Nov 14, 2011 at 15:45 | comment | added | user19259 | 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. | |
| Jun 18, 2011 at 7:38 | comment | added | Fedor Petrov | @Darij. I agree. | |
| Jun 17, 2011 at 19:04 | comment | added | darij grinberg | I have edited your post slightly. Do you agree or am I off-track? | |
| Jun 17, 2011 at 19:04 | history | edited | darij grinberg | CC BY-SA 3.0 |
added 82 characters in body
|
| May 23, 2011 at 17:02 | comment | added | Fedor Petrov | yes, but RHS must be $\min(r,a+b)$ | |
| May 23, 2011 at 0:13 | vote | accept | darij grinberg | ||
| May 23, 2011 at 0:12 | comment | added | darij grinberg | 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$. | |
| May 22, 2011 at 10:20 | comment | added | Fedor Petrov | 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). | |
| May 22, 2011 at 9:19 | comment | added | darij grinberg | 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? | |
| May 17, 2011 at 18:16 | comment | added | darij grinberg | 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! | |
| May 17, 2011 at 18:15 | history | edited | darij grinberg | CC BY-SA 3.0 |
fixing some inaccuracies, or what appeared to me as such
|
| May 17, 2011 at 11:43 | history | answered | Fedor Petrov | CC BY-SA 3.0 |