3
$\begingroup$

By 2-edge-colouring of $K_n$ I mean an assignment $c$ of the colours red and blue to the edges of $K_n$, i.e. $c:E(K_n) \to \{0, 1\}$. By monochromatic induced subgraph $K_m$ I mean an induced subgraph $K_m$ of $K_n$ such that all edges in $K_m$ are coloured red, or all edges in $K_m$ are coloured blue.

I have to show that there exists $c$ such that $m = \lceil 4 \log_2(n) \rceil$, that is there is some 2-edge-colouring of $K_n$ such that it contains no induced subgraph $K_{\lceil 4 \log_2(n) \rceil}$. I am unsure where to start with this; I think induction is ruled out as transforming $\log_2(n-1)$ into $\log_2(n)$ seems fairly hard. Proof by contradiction may work but I feel like the simplest proof will be constructive.

I have been trying to figure out a way to start the proof for hours now, and just can't think of a way in. Any help appreciated.

From searching it seems like Ramsey numbers (more precisely monochromatic Ramsey numbers) might be helpful, but these tend to deal with "all assignments $c$ such that ..." style problems instead of "their exists an assignment $c$ such that ..." problems.

$\endgroup$
2
  • $\begingroup$ The question isn't entirely clear. The title says "smallest possible", but this seems to be missing in the question itself, where $m$ is never defined. It seems you mean that $m$ is the least natural number (depending on $n$) for which a monochromatic induced subgraph $K_m$ exists? Also a lower bound for $n$ seems to be missing, since for small $n$ we'd have $m = \lceil 4 \log_2(n) \rceil\gt n$. $\endgroup$
    – joriki
    Mar 13, 2016 at 23:06
  • $\begingroup$ You're right, I'm sorry; it is late here and my brain is tired from staring at this problem. I've edited the question, I can see how it was misleading. $\endgroup$
    – D. P
    Mar 13, 2016 at 23:56

1 Answer 1

2
$\begingroup$

My proof uses the probabilistic method, to show that the probability of such a monochromatic subset of size $k=\lceil 4\log_2 n\rceil$ occuring in a ramdonly coloured $K_n$ is less than one.


Consider a random colouring of $K_n$, where each edge is coloured red or blue with probability $p=1/2$.

For each subset $V_i\subseteq V(K_n)$ such that $|V_i|=k$, define a random variable $X_i$ such that $X_i=1$ if $V_i$ is monochromatic and $X_i=0$ otherwise. The probability $P(X_i=1)$ is equal to $2p^{\binom{k}{2}}$, since there are $\binom{k}{2}$ edges in $V_i$ which are independently coloured with probability $p=1/2$, and it could either be red or blue.

The probability that there is at least one monochromatic $k$-tuple is equal to the probability that for at least one $i$, $X_i=1$.

We know that $P(X_i=1)=2p^{\binom{k}{2}}$, and there are $\binom{n}{k}$ such $k$-tuples. Putting this together gives \begin{align*} P(\text{There is a monochromatic }k\text{-tuple}) &\le 2\binom{n}{k}p^{\binom{k}{2}}. \end{align*}(The inequality here follows from the fact that the $X_i$ are not independent, as the $k$-tuples are not disjoint.)

Moreover notice that an upper bound can be obtained from \begin{align*} \binom{n}{k}&=\frac{n!}{k!(n-k)!}\\ &=\frac{n(n-1)\cdots (n-k+1)}{k!}\le \frac{n^k}{k!}. \end{align*} For $n\ge 2$, $4\log_2 n> 2$, and so $$\frac{2}{\lceil 4\log_2 n\rceil!}<\frac{2}{\lceil 4\log_2 n\rceil}<\frac{2}{ 4\log_2 n}<1.$$ Finally, we can re-write $\binom{k}{2}=\frac{k(k-1)}{2}$ just using the definition. Putting these arguments together,

\begin{align*} P(\text{There is a monochromatic }k\text{-tuple})&\le 2\binom{n}{k}p^{\binom{k}{2}}\\ &\le \frac{2n^k p^{\frac{k(k-1)}{2}}}{k!}\\ &=\frac{2}{\lceil 4\log_2 n\rceil!}\cdot\frac{n^{\lceil 4\log_2 n\rceil} }{2^{\lceil 4\log_2 n\rceil(\lceil 4\log_2 n\rceil-1)/2}}\\ &\le \frac{n^{\lceil 4\log_2 n\rceil} }{2^{2\log_2 n ( 4\log_2 n-1)}}\\ &=\frac{n^{\lceil 4\log_2 n\rceil} }{n^{2(4\log_2 n-1)}} %&=n^{\lceil 4\log_2 n\rceil-2(4\log_2 n-1)}\\ %&= \frac{n^{\lceil 4\log_2 n\rceil} n^2}{n^{8\log_2 n}}\\ %&=\frac{n^{\lceil 4\log_2 n\rceil+2}}{n^{8\log_2 n}} =n^{\lceil 4\log_2 n\rceil-8\log_2 n+2}<1. \end{align*} This is because $n\ge 2$, and \begin{align*} \lceil 4\log_2 n\rceil+2&< 4\log_2 n+3\\ &<4(\log_2 n + 1)\\ &\le 4 (2\log_2 n), \end{align*} implying that $$\lceil 4\log_2 n\rceil + 2-8\log_2 n<0.$$

Since $P(\text{There is a monochromatic }k\text{-tuple})<1$, it follows that the probability of such a tuple is not guaranteed: that is, you can find some colouring such that no monochromatic $k$-tuple exists in the case $n\ge 2$.

$\endgroup$
1
  • $\begingroup$ That's a really clever way to think about the problem, I hadn't thought of this approach. Solution is clear, thank you very much. $\endgroup$
    – D. P
    Mar 16, 2016 at 17:13

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.