MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 edited body

I have a strategy I would want to use, but would need to know something about the $(n-1)$-cliques that show up when you have a colouring avoiding $n$-cliques to make it work

Start off with a 2-edge colouring of $K_{R(n,n)-1}$ avoiding $n$-cliques. Add $100n$ new vertices. Colour the edges between old and new at random with P(red)=$p_1$, small; Colour the edges between the new vertices randomly with P(blue)=$p_2$, small (so that the old-new edges are mostly blue; the new-new edges are mostly red).

You want to avoid a blue $K_{n+1}$ and a red $K_n$. There is basically one way to get a blue $K_{n+1}$: start from a previously existing blue $K_{n-1}$ and find two new points connected by a blue edge such that all edges connecting to the existing $K_{n-1}$ are blue.

There are essentially 2 ways to get a red $K_n$: by finding an existing red $K_{n-1}$ and a new point such that all of the edges connecting the new point to the existing $K_{n-1}$ are red; or by finding a red $K_n$ amongst the newly added vertices.

Let $R$ denote the number of red $n-1$-cliques in the original stuff; let $B$ denote the number of blue $n-1$-cliques.

The expected number of red $n$-cliques of the first type is $100Rnp_1^{n-1}$.

The expected number of red $n$-cliques of the second type is $\binom{100n}{n}(1-p_2)^{n(n-1)/2}$. This is something like $(100e)^ne^{-p_2n^2/2}$ so to make this small you need $p_2=\omega(1/n)$.

The expected number of blue $n+1$-cliques of the type described above is $5000Bn(n-1)(1-p_1)^{2(n-1)}p_2$

If you know something about $B$ and $R$ and can make the sum of these quantities less than 1 by a smart choice of $p_1$ and $p_2$ you'd be in business (e.g. if $B$ and $R$ were known to be $O(2^n)$, o(2^n)$, you can take$p_1=p_2=1/2$and everything is small) 2 +details; added 28 characters in body I have a strategy I would want to use, but would need to know something about the$(n-1)$-cliques that show up when you have a colouring avoiding$n$-cliques to make it work Start off with a 2-edge colouring of$K_{R(n,n)-1}$avoiding$n$-cliques. Add$100n$new vertices. Colour the edges between old and new at random with P(red)=$p_1$, small; Colour the edges between the new vertices randomly with P(blue)=$p_2$, small (so that the old-new edges are mostly blue; the new-new edges are mostly red). You want to avoid a blue$K_{n+1}$and a red$K_n$. There is basically one way to get a blue$K_{n+1}$: start from a previously existing blue$K_{n-1}$and find two new points connected by a blue edge such that all edges connecting to the existing$K_{n-1}$are blue. There are essentially 2 ways to get a red$K_n$: by finding an existing red$K_{n-1}$and a new point such that all of the edges connecting the new point to the existing$K_{n-1}$are red; or by finding a red$K_n$amongst the newly added vertices. Let$R$denote the number of red$n-1$-cliques in the original stuff; let$B$denote the number of blue$n-1$-cliques. The expected number of red$n$-cliques of the first type is$100Rnp_1^{n-1}$. The expected number of red$n$-cliques of the second type is$\binom{100n}{n}(1-p_2)^{n(n-1)/2}$. This is something like$(100e)^ne^{-p_2n^2/2}$so to make this small you need$p_2=\omega(1/n)$. The expected number of blue$n+1$-cliques of the type described above is$5000Bn(n-1)(1-p_1)^{2(n-1)}p_2$If you know something about$B$and$R$and can make the sum of these quantities less than 1 by a smart choice of$p_1$and$p_2$you'd be in business .(e.g. if$B$and$R$were known to be$O(2^n)$, you can take$p_1=p_2=1/2$and everything is small) 1 I have a strategy I would want to use, but would need to know something about the$(n-1)$-cliques that show up when you have a colouring avoiding$n$-cliques to make it work Start off with a 2-edge colouring of$K_{R(n,n)-1}$avoiding$n$-cliques. Add$100n$new vertices. Colour the edges between old and new at random with P(red)=$p_1$, small; Colour the edges between the new vertices randomly with P(blue)=$p_2$, small (so that the old-new edges are mostly blue; the new-new edges are mostly red). You want to avoid a blue$K_{n+1}$and a red$K_n$. There is basically one way to get a blue$K_{n+1}$: start from a previously existing blue$K_{n-1}$and find two new points connected by a blue edge such that all edges connecting to the existing$K_{n-1}$are blue. There are essentially 2 ways to get a red$K_n$: by finding an existing red$K_{n-1}$and a new point such that all of the edges connecting the new point to the existing$K_{n-1}$are red; or by finding a red$K_n$amongst the newly added vertices. Let$R$denote the number of red$n-1$-cliques in the original stuff; let$B$denote the number of blue$n-1$-cliques. The expected number of red$n$-cliques of the first type is$100Rnp_1^{n-1}$. The expected number of red$n$-cliques of the second type is$\binom{100n}{n}(1-p_2)^{n(n-1)/2}$. This is something like$(100e)^ne^{-p_2n^2/2}$so to make this small you need$p_2=\omega(1/n)$. The expected number of blue$n+1$-cliques is$5000Bn(n-1)(1-p_1)^{2(n-1)}p_2$If you know something about$B$and$R$and can make the sum of these quantities less than 1 by a smart choice of$p_1$and$p_2\$ you'd be in business.