Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a monochromatic matching in color $i$ of size $m_i$ (and this is tight). When $m_1=\dots=m_r$, we get $n=(r+1)m-(r-1)$. Their proof is a clever induction argument, but it seems to fundamentally use the fact that they are proving the more general ("non-diagonal") version. There should be no complaints since they are able to prove the statement by proving something more general. However, if you think about the problem for a few minutes, you will be able to come up with a proof of the 2-color case, and a few minutes more, you'll get the three color case, but I haven't found a proof for the $r$-color case which does not rely on proving the more general non-diagonal statement. Basically, I'm curious if there is another proof of the diagonal version of their result along the lines of the $r=2$ and $r=3$ case below. Beyond that, I'm wondering if there is a non-inductive proof which uses the Berge-Tutte theorem/formula (for instance) on the size of a largest matching in a graph.

First note that the result holds when $r=1$ or $m=1$, so suppose $r, m\geq 2$ and the result holds for all $1\leq r', m'$ with $r'+m'<r+m$.

Proof for $r=2$: We have $n=3m-1$, so if we can find a set of three vertices which contain both a red edge and a blue edge, we can apply induction on the remaining $n-3$ vertices to get a matching of size $m-1$ in one of the colors, which together with either the red edge or the blue edge gives a matching of size $m$. If we can't find such a set, then only one color is used.

Proof for $r=3$: We have $n=4m-2$, so if we can find a set of at most four vertices which contain edges of all three colors, we can apply induction on the remaining at least $n-4$ vertices as before. If we can't find such a set, then we can deduce that only two colors are used. Indeed, we are done if some vertex is incident with edges of all three colors or all vertices are incident with edges of only one color, so some vertex is incident with say only red and blue edges. But now if there is a green edge anywhere, this will give a set of size at most 4 which sees edges of all three colors.

  • $\begingroup$ Sorry, but what do you mean in Proof for r=2, " we can apply induction on the remaining n−3 vertices"? I can't see why this induce proven. $\endgroup$ – Bonbon May 4 '18 at 15:57
  • $\begingroup$ Sorry for the lack of details. I just edited my question to make that step more clear. $\endgroup$ – Louis D May 4 '18 at 17:58
  • $\begingroup$ Got it, I misunderstood the word "match". $\endgroup$ – Bonbon May 4 '18 at 19:53

Here goes a direct proof of a general fact. It is not inductive, so you may substitute $m_1=m_2=\dots=m_r=m$ into it, but it does not become any shorter. It uses Tutte/Berges formula of the maximal matching, as you ask for.

We use two easy lemmas.

Lemma 1. A graph on $N$ vertices with at least $N-k$ components has at most $\binom{k+1}2$ edges.

Proof. Let $C_0$ denote a maximal component. If certain component $C\ne C_0$ contains at least two vertices, move one of them to $C_0$. The number of edges increases. After several steps all components different from $C_0$ contain 1 vertex, and $C_0$ at most $k+1$ vertices, thus the number of edges does not exceed $\binom{k+1}2$.

Lemma 2. If $p=0$ or $p\geqslant 1$, and $p_1,\dots,p_r\in [0,p]$ are real numbers, than $\sum_i \binom{2p_i+1}2\leqslant \binom{p+p_1+\dots+p_r+1}2$.

Proof. The case $p=0$ is clear, assume that $p\geqslant 1$. Fix $p$ and note that the difference LHS-RHS is a quadratic trinomial in $p_i$ with positive leading coefficient, thus its maximal value (with all other $p_j$'s being fixed and $p_i$ varying from 0 to $p$) is attained either for $p_i=0$ or $p_i=p$. So, we need to check it only when $p_1=\dots=p_s=p,p_{s+1}=\dots=p_r=0$ for certain index $s$. This rewrites as $sp(2p+1)\leqslant (s+1)p((s+1)p+1)/2$, $2s(2p+1)\leqslant p(s+1)^2+s+1$, $p(s-1)^2\geqslant s-1$, which is true.

Now assume that $n\geqslant 2m_1+m_2+\dots+m_r-(r-1)$ and $G$ is a complete graph on the ground set $V$, $|V|=n$, edges of $G$ are colored in $r$ colors so that the maximal matching of color $i$ contains $f_i<m_i$ edges. Then $n\geqslant \max(f_i)+f_1+\dots+f_r+2$. By Tutte/Berges there exist subsets $U_i$ of the vertex set $V$ such that the graph $G_i$ formed by the edges of color $i$ on the vertex set $V\setminus U_i$ has $|U_i|+(n-2f_i)$ odd components. Actually I need only that it has at least $|U_i|+(n-2f_i)$ components. In particular this implies $n-|U_i|=|V\setminus U_i|\geqslant |U_i|+(n-2f_i)$, $|U_i|\leqslant f_i$. Denote $p_i=f_i-|U_i|$, these are non-negative integer numbers, and denote $p=\max(p_i)\leqslant \max(f_i)$.

Denote $U=\cup U_i$, $W=V\setminus U$. The number of components formed by color $i$ on the set $W$ is not less than $|U_i|+n-2f_i-|U\setminus U_i|=|W|-2p_i$. Thus the number of edges of color $i$ between the vertices from $W$ does not exceed $\binom{2p_i+1}2$ by Lemma 1, and the total number of edges between the vertices of $W$ does not exceed $\binom{p+p_1+\dots+p_r+1}2$ by Lemma 2. On the other hand, we have $|W|=n-|U|\geqslant n-\sum |U_i|\geqslant 2+p+\sum p_i$. This gives a contradiction.

  • $\begingroup$ 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$? $\endgroup$ – Louis D May 10 '18 at 13:37
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov May 10 '18 at 14:17
  • $\begingroup$ 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. $\endgroup$ – Louis D May 10 '18 at 14:39
  • $\begingroup$ 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. $\endgroup$ – Louis D May 10 '18 at 14:43
  • $\begingroup$ @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$. $\endgroup$ – Fedor Petrov May 10 '18 at 15:03

Strictly speaking, no. Because the implication "there are at least $C$ colors" => "there is a complete subgraph in $C+1$ vertices that has at least $C$ colors" is true only for $C<4$.

In fact, for $C<4$ is even true that "there are at least $C$ colors" => "there is a connected subgraph with $C$ edges all of different color".

Instead, for $C\geq 4$ we can have examples as the following: a complete graph with vertices $\{1,2,3,4,5,6\}$ and all edges red, except for $(1,2):=blue$, $(3,4):=green$, $(5,6):=yellow$.

Of course this doesn't exclude that some clever and relatively simple observation may solve the general induction step, but at least this shows why the steps $r=1,2,3$ are so easy in comparison.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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