Show that $R(mK_2,mK_2)=3m-1$

110 Views Asked by At

I proved this but I am looking for an easier proof for the second part below.

EDIT: Thanks to Misha, I have a big mistake in the second part. See the comments for the reason. Still looking for a short proof.

First part: To show $R(mK_2,mK_2)>3m-2$, construct a graph $G$ with $3m-2$ vertices such that neither $G$ nor $\bar{G}$ contains a matching of size $m$. We can construct such a $G$ making $m-1$ independent vertices adjacent to every vertex of $K_{2m-1}$.

Second part: Showing $R(mK_2,mK_2) \leq 3m-1$ should be easier then the proof I am going to write down.

Assume that $R(mK_2,mK_2) > 3m-1$. This means that there exists a graph $G$ with $3m-1$ vertices, neither $G$ nor $\bar{G}$ have a matching of size $m$ and so, they don't have $m$ independent edges. This implies that the line graphs of $G$ and $\bar{G}$ do not contain $m$ independent vertices. So, both of the line graphs don't contain $K_m$. Note that the line graphs has $(3m-1)(3m-2)/2$ vertices and the number of their edges in total is

\begin{equation} \frac{\frac{(3m-1)(3m-2)}{2} \left(\frac{(3m-1)(3m-2)}{2}-1 \right)}{2}. \end{equation}

since the union is a complete graph. From Turan theory, the number of edges in the extremal graph that does not contain $K_m$ is bounded from above by

\begin{equation} \left(1-\frac{1}{m-1}\right)\frac{\left(\frac{(3m-1)(3m-2)}{2}\right)^2}{2}. \end{equation}

So, the number of edges in $G$ and $\bar{G}$ in total cannot exceed $\left(1-\frac{1}{m-1}\right)\left(\frac{(3m-1)(3m-2)}{2}\right)^2$. Finally, it is enough to show that

$\frac{(3m-1)(3m-2)}{4} \left(\frac{(3m-1)(3m-2)}{2}-1 \right) > \left(1-\frac{1}{m-1}\right)\left(\frac{(3m-1)(3m-2)}{2}\right)^2$

to get a contradiction. :)

1

There are 1 best solutions below

1
On BEST ANSWER

We want to show that for all $m\ge 1$, every $(3m-1)$-vertex graph $G$ either has an $m$-edge matching, or else its complement $\overline G$ does.

Induct on $m$. When $m=1$, $G$ is any $2$-vertex graph, and either $G$ or $\overline G$ contains an edge. Now assume that the statement holds for some $m \ge 1$; to try to prove it for $m+1$, take any graph $G$ on $3m+2$ vertices.

We can find a matching of size $\lfloor \frac{3m+2}{2}\rfloor \ge m+1$ in $G$ if $G$ is a complete graph, or in $\overline G$ if $G$ is an empty graph. Otherwise, we can find three vertices $v_1, v_2, v_3$ such that $v_1 v_2 \in E(G)$ but $v_2 v_3 \notin E(G)$.

Let $G' = G - \{v_1, v_2, v_3\}$. By the inductive hypothesis, since $G'$ has $3m-1$ vertices, either $G'$ or $\overline {G'}$ contains a matching of size $m$. In the first case, adding on $v_1 v_2$ gives us a matching of size $m+1$ in $G$; in the second case, adding on $v_2 v_3$ gives us a matching of size $m+1$ in $\overline G$.

By induction, this is possible for all $m$.