Quiero intentar una prueba probabilística para este problema. Por favor, comenten este intento de prueba.
Dejemos que $G$ sea nuestro gráfico completo $K_{2^{3d}}$ con los bordes coloreados en rojo/azul de forma aleatoria e independiente. Mi observación es que, cualquier $d$ -cubo de dimensiones $Q_d$ puede construirse a partir de $2$ copias de $Q_{d-1}$ con las aristas que faltan añadidas adecuadamente. Como $2^{3d} = 2^{3(d-1)}\cdot 8$ por inducción $G$ contiene $8$ copias de monocromáticas $Q_{d-1}$ Al menos $4$ de los cuales deben ser del mismo color (wlog que el color sea rojo).
Ahora considere el evento $X$ que ninguno de los pares de $Q_{d-1}$ entre los que $4$ las copias forman un rojo monocromático $Q_d$ . Se trata de la unión de los eventos que todos los pares de $Q_{d-1}$ no son válidos. Por el límite de la unión, tenemos: $$\mathbb{P}(X) \leq \sum \mathbb{P} \text{(the pair of $ Q_{d-1} $ forms invalid $ Q_d $)} = {4 \choose 2} \cdot \left( \frac{1}{2} \right)^{2^{d-1}} = \frac{6}{2^{2^{d-1}}} < 1, \text{ for $ d>1 $.}$$
Por lo tanto, la probabilidad de que uno de los pares de $Q_{d-1}$ forma un rojo válido y monocromático $Q_d$ es estrictamente positivo.
-------------
Editar: Pongo una recompensa por esta pregunta. Se agradecerán las pistas o respuestas.
