Si $K_{14}$ se colorea con dos colores, habrá un cuadrilátero monocromático.

Question

Esta pregunta procede de Problem Solving Strategies de Engel, capítulo 4, pregunta 50.

Si $K_{14}$ se colorea con dos colores, habrá un cuadrilátero monocromático.

Aquí, $K_{14}$ es el gráfico completo con 14 vértices, una coloración significa asignar a cada arista un color (digamos rojo o azul) y estoy asumiendo que cuadrángulo significa un ciclo de longitud 4.

Conozco la técnica para demostrar que $R(3,3) = 6$ (el número de Ramsey), e intenté aplicarlo pero sin éxito. Por ejemplo, si tengo un camino rojo de longitud 3, entonces puedo forzar que la última arista sea azul. También empecé por considerar que cada vértice tiene 13 vecinos, por lo que cada vértice tiene más aristas rojas o azules. Así que existen al menos 7 vértices, cada uno con al menos 7 aristas del mismo color. Pero no veo la forma de proceder.

Answer 1

El gráfico completo $K_{14}$ es mucho más grande de lo necesario para este resultado; aquí hay tres subgrafos propios con la misma propiedad.

I. Cada $2$ -de un grafo bipartito completo $K_{3,7}$ contiene un monocromático $C_4$ .

Dejemos que $K_{3,7}$ tienen conjuntos parciales $V_1,V_2$ con $|V_1|=3$ y $|V_2|=7$ . Cada vértice en $V_2$ está unido por aristas de un color a dos vértices en $V_1$ . Por el principio de encasillamiento, dos vértices en $V_2$ están unidos por aristas del mismo color a los mismos dos vértices en $V_1$ .

II. Cada $2$ -coloración del gráfico completo $K_6$ contiene un monocromático $C_4$ . (Esto se demostró en la respuesta de Misha Lavrov; el siguiente argumento es quizá algo más sencillo).

Podemos suponer que existe un vértice $x$ que es incidente con un máximo de dos aristas azules. De hecho, podemos suponer que $x$ es un incidente con exactamente dos bordes azules; en caso contrario $x$ sería incidente con cuatro bordes rojos, llámalos $xa_1$ , $xa_2$ , $xa_3$ , $xa_4$ y entonces podríamos considerar un vértice $y\notin\{x,a_1,a_2,a_3,a_4\}$ y proceder como en la respuesta de paw88789. (Puede ser incluso más fácil observar que el subgrafo inducido por $\{a_1,a_2,a_3,a_4\}$ contiene un rojo $P_3$ o un azul $C_4$ .)

Así que dejemos $x$ sea incidente con exactamente dos aristas azules, $xy$ y $xz$ . Si uno de los tres vértices restantes está unido por el azul a ambos $y$ y $z$ entonces tenemos un azul $C_4$ . Por otro lado, si cada uno de esos tres vértices está unido por el rojo a un vértice en $\{y,z\}$ , entonces dos de ellos están unidos por el rojo al mismo vértice en $\{y,z\}$ y también a $x$ , haciendo un rojo $C_4$ .

III. Cada $2$ -de un grafo bipartito completo $K_{5,5}$ contiene un monocromático $C_4$ .

La prueba se deja como ejercicio para el lector.

Answer 2

Intentemos evitar un cuadrilátero monocromático ( $4$ -ciclo):

Como ha señalado, cada vértice tiene al menos $7$ bordes incidentes con el mismo color. Sea $x$ sea un vértice y que $a_1$ , $a_2$ , $a_3$ , $a_4$ sean cuatro vértices para los que las aristas de $x$ a cada $a_i$ son todos del mismo color ( $i=1,2,3,4$ ). Sin pérdida de generalidad, podemos suponer que el color de esas aristas es rojo.

Ahora dejemos que $y$ sea un vértice diferente (no $x$ y no a cualquiera de $a_1,...,a_4$ ). Al menos tres de las aristas $(y,a_1), (y,a_2), (y,a_3), (y,a_4)$ debe ser azul. (Si dos de ellos son rojos, se obtiene un cuadrilátero rojo utilizando $x,a_i,y,a_j$ donde los bordes $(y,a_i)$ y $(y,a_j)$ son de color rojo). Sin pérdida de generalidad, podemos suponer $(y,a_1), (y,a_2), (y,a_3)$ son todos los bordes azules.

Si el borde de $a_1$ a $a_2$ es rojo, entonces la arista de $a_2$ a $a_3$ debe ser azul (de lo contrario $x,a_1,a_2,a_3$ es un cuadrilátero rojo). Pero entonces el borde de $a_1$ a $a_3$ completará un cuadrilátero monocromático (si es rojo: $x,a_2,a_1,a_3$ ; si es azul: $y,a_1,a_3,a_2$ ).

Del mismo modo, si la arista de $a_1$ a $a_2$ es azul, obtendrá de nuevo un cuadrilátero monocromático.

Nota: Me parece que este argumento podría ser utilizado para demostrar que un cuadrilátero monocromático debe existir en un borde de 2 colores $K_9$ .

Answer 3

Un resultado más agudo muestra que cualquier $2$ -coloración de $K_6$ contiene un monocromático $C_4$ .

Sabemos que $R(3,3)=6$ Así que cualquier $2$ -coloración de $K_6$ contiene un triángulo monocromático. Sea $\{x,y,z\}$ sean los vértices del triángulo, y sin pérdida de generalidad dejemos que el rojo sea el color de las aristas $xy, xz, yz$ .

Si hay otro vértice $w$ con aristas rojas a al menos dos vértices entre $\{x,y,z\}$ , entonces obtenemos un rojo $C_4$ . Diga $wx$ y $wy$ son de color rojo: entonces las aristas $wx, xz, zy, yw$ forman un ciclo rojo.

En caso contrario, cada uno de los tres vértices fuera de $\{x,y,z\}$ tiene como máximo una arista roja para $\{x,y,z\}$ - y al menos dos bordes azules a $\{x,y,z\}$ . Si hay dos vértices $w_1, w_2$ con aristas azules a los mismos dos vértices entre $\{x,y,z\}$ , entonces obtenemos un azul $C_4$ . Diga $w_1x, w_1y, w_2x, w_2y$ son azules: entonces los bordes $w_1x, xw_2, w_2y, yw_1$ forman un ciclo azul.

La posibilidad restante es que los otros tres vértices tengan exactamente dos aristas azules para $\{x,y,z\}$ y es un conjunto diferente de bordes azules para cada uno. Podemos etiquetar los vértices restantes $\{x', y', z'\}$ tal que las aristas $xx', yy', zz'$ son de color rojo mientras que $xy', xz', yx', yz', zx', zy'$ son azules, obteniendo la coloración parcial de abajo:

Ahora miramos los colores de las tres aristas restantes $x'y', x'z', y'z'$ .

• Si $x'y'$ es rojo, entonces las aristas $x'y', y'y, yx, xx'$ forman un ciclo rojo.
• Si $y'z'$ es rojo, entonces las aristas $y'z', z'z, zy, yy'$ forman un ciclo rojo.
• Si $x'y'$ y $y'z'$ son ambas azules, entonces las aristas $x'y', y'z', z'y, yx'$ forman un ciclo azul.

Answer 4

Supongamos que no hay ningún monocromático $C_4$ . Entonces, para cada par de vértices $a,b$ tenemos $|N(a)\cap N(b)|\leq 1$ y $|N'(a)\cap N'(b)|\leq 1$ . Por otro lado, cada elemento está conectado a $$d={x\choose 2}+{y\choose 2}$$ pares de vértices (en $G$ y $G'$ ), por lo que $x+y=13$ . Por la desigualdad de Jensen tenemos $$d\geq {{1\over 2}13^2-13\over 2}={143\over 4}\implies d\geq 36 $$

por lo que tenemos $$2 {14\choose 2}\geq 14\cdot 36$$ lo cual es una clara contradicción.

---

Tenemos un resultado más fuerte: Si pasamos de 14 a 8 obtenemos $d\geq 9$ por lo que obtenemos $$2 {8\choose 2}\geq 8\cdot 9$$ lo cual es de nuevo una contradicción. Así que $K_8$ contiene monocromos $C_4$ .