Timeline for A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 17, 2018 at 5:46 | history | suggested | Louis D | CC BY-SA 4.0 |
I was thinking about this again and realized that there was a typo in Lemma 2. It should be p, not 2p in the term on the right. It turns out the calculation in the proof is correct, although there was a typo there as well. It should be (s+1), not p(s+1) just before the end.
|
| May 16, 2018 at 19:41 | review | Suggested edits | |||
| S May 17, 2018 at 5:46 | |||||
| May 10, 2018 at 15:03 | comment | added | Fedor Petrov | @LouisD the intuition was very simple: to care on the example for $n-1$ vertices and look for the estimate which is sharp for $n-1$. | |
| May 10, 2018 at 14:47 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 1 character in body
|
| May 10, 2018 at 14:44 | vote | accept | Louis D | ||
| May 10, 2018 at 14:43 | comment | added | Louis D | Also, for your inequality in Lemma 2, maybe put a comma after $p\geq 1$, because I first read it as $p=0$ or ($p\geq 1$ and $p_1,…,p_r\in [0,p]$), not ($p=0$ or $p\geq 1$) and $p_1,…,p_r\in [0,p]$ as I later understood it. I was wondering if this inequality follows from an existing well-known inequality, or maybe just what your intuition was for why this should be true. | |
| May 10, 2018 at 14:39 | comment | added | Louis D | I started to come to that realization after I asked the question. That is, of course we can count the edges inside the set $U$ and the edges between $U$ and $W$, but we might as well just count the edges inside $W$ since that is where the problem will lie. | |
| May 10, 2018 at 14:17 | comment | added | Fedor Petrov | I think, the appearance of $W$ is natural, since the edges from $U_i$ are permitted to have color $i$, and therefore they can not help us with contradiction. | |
| May 10, 2018 at 13:37 | comment | added | Louis D | Thanks. This is exactly the type of thing I was looking for. I'm currently trying to figure out if we can just bound the number of edges in each $G_i$ using Berge/Tutte as you did, and then add them all up and show that it is less than $\binom{n}{2}$. Or is it vital to the proof that we must first define the set $W$ and upper bound the number of edges inside $W$ while lower bounding the size of $W$? | |
| May 9, 2018 at 16:07 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 423 characters in body
|
| May 9, 2018 at 14:53 | history | answered | Fedor Petrov | CC BY-SA 4.0 |