Mi prueba utiliza el método probabilístico, para mostrar que la probabilidad de tal subconjunto monocromático de tamaño $k=\lceil 4\log_2 n\rceil$ que ocurre en un color rampante $K_n$ es menor que uno.
Considere una coloración aleatoria de $K_n$ donde cada arista se colorea de rojo o azul con probabilidad $p=1/2$ .
Para cada subconjunto $V_i\subseteq V(K_n)$ tal que $|V_i|=k$ definan una variable aleatoria $X_i$ tal que $X_i=1$ si $V_i$ es monocromática y $X_i=0$ en caso contrario. La probabilidad $P(X_i=1)$ es igual a $2p^{\binom{k}{2}}$ ya que hay $\binom{k}{2}$ bordes en $V_i$ que se colorean independientemente con probabilidad $p=1/2$ y puede ser rojo o azul.
La probabilidad de que haya al menos un monocromático $k$ -es igual a la probabilidad de que al menos una $i$ , $X_i=1$ .
Sabemos que $P(X_i=1)=2p^{\binom{k}{2}}$ y hay $\binom{n}{k}$ tal $k$ -tuplas. Al juntar todo esto se obtiene \begin{align*} P(\text{There is a monochromatic }k\text{-tuple}) &\le 2\binom{n}{k}p^{\binom{k}{2}}. \end{align*} (La desigualdad aquí se deduce del hecho de que el $X_i$ no son independientes, ya que el $k$ -no son disjuntos).
Además, observe que se puede obtener un límite superior a partir de \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*} Para $n\ge 2$ , $4\log_2 n> 2$ y así $$\frac{2}{\lceil 4\log_2 n\rceil!}<\frac{2}{\lceil 4\log_2 n\rceil}<\frac{2}{ 4\log_2 n}<1.$$ Por último, podemos reescribir $\binom{k}{2}=\frac{k(k-1)}{2}$ sólo con la definición. Juntando estos argumentos,
\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*} Esto se debe a que $n\ge 2$ y \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*} lo que implica que $$\lceil 4\log_2 n\rceil + 2-8\log_2 n<0.$$
Desde $P(\text{There is a monochromatic }k\text{-tuple})<1$ se deduce que la probabilidad de dicha tupla no está garantizada: es decir, se puede encontrar alguna coloración tal que ninguna monocromática $k$ -existe en el caso $n\ge 2$ .
