2
$\begingroup$

Prove: if we $t$-color the edges of the complete graph on $2^t+1$ vertices, then there must be a monochromatic odd cycle.

This is supposed to be an easy exercise but I haven't made much progress. Here are my attempts.

I have tried the probabilistic method, but it doesn't seem feasible because the number of possible odd cycles is $\frac{1}{2}2^{2^t+1}-(2^t+1)=2^{2^t}-2^t-1$ which doesn't seem like a workable number. In addition the probability that a cycle is monochromatic depends on the length. So the chance of an odd cycle is something like

$${2^t+1\choose 3}\frac{1}{t^2}+{2^t+1\choose 5}\frac{1}{t^4}+\cdots+{2^t+1\choose 2^t+1}\frac{1}{t^{2^t}}$$

and I really don't see this method being very helpful.

The other route is induction: suppose it is true for $k$ vertices. Then we need to find a monochromatic odd cycle in the $k+1$ coloring on $2^{t+1}+1$ vertices. I would guess there is some clever way to split the vertices into two, but I'm not sure how.


If anyone has a guiding hint, it would be appreciated.

$\endgroup$
2
$\begingroup$

Let's call the colour $1,2,\dots,r$.

Suppose that there is a $r$-colouring of $K_{2^r+1}$ with no monochromatic odd cycle. Consider the graph $G_r$ of the edges coloured with colour $r$. This graph is bipartite, say with bipartition $A$ and $B$ of the vertex set. We can assume $|A|\geq 2^{r-1}+1$.

This means that we can have a $(r-1)$-colouring of $K_{2^{r-1}+1}$ with no monochromatic odd cycle. This leads a contradiction if we do it recursively, since we cannot have $1$-colouring for $K_3$ with no monochromatic odd cycle.

Actually there is another part of this question which shows that the bound $2^r+1$ is tight, namely: there is a $r$-colouring of $K_{2^r}$ such that there is no monochromatic odd cycle. That can be constructed by recursively combined two $(r-1)$-coloured $K_{2^{r-1}}$ and colour the edges between them by colour $r$.

$\endgroup$
  • $\begingroup$ Wow thanks a ton. I was frustratingly close to this a few hours ago but didn't put it all together. Cool problem. $\endgroup$ – Elliot G Jul 6 '16 at 20:42
  • $\begingroup$ Another way of thinking about it is that you want to cover the edges of the complete graph by bipartite graphs. If a graph $G=G_1 \cup G_2$, then $\chi(G) \leq \chi(G_1)\chi(G_2)$. Hence if a graph can be covered by $k$ bipartite graphs, then $\chi(G) \leq 2^k$. To cover $K_{2^r}$ by $r$ bipartite graphs, consider the $r$ partitions where in the $ith$ partition, vertices with $ith$ bit zero are in one part and those with $i$th bit one are in the other part. $\endgroup$ – Aravind Jul 7 '16 at 4:05

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.