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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .