Mi pregunta es cómo demostrar que $R(2K_3, 2K_3)$ es 10.
Primero, $2K_3$ son dos triángulos distintos, por lo que se trata de demostrar que si coloreamos las aristas de $K_{10}$ en dos colores, habrá dos triángulos con el mismo color.
Lo único que he conseguido es que haya una "mariposa", es decir, dos triángulos monocromáticos que comparten un vértice.
En primer lugar, debemos demostrar que la coloración $K_9$ no es suficiente. He aquí un contraejemplo:
Rojo $K_3$ se limitan a los vértices $\{1,2,3,4,5\}$ así que están fuera: dos de ellos comparten un vértice. Un azul $K_3$ puede utilizar como máximo uno de los vértices $\{1,2,3,4,5\}$ por lo que debe utilizar dos vértices de $\{6,7,8,9\}$ no puede incluir $6$ porque las aristas de $6$ à $\{7,8,9\}$ son rojos. Así que cualquier azul $K_3$ incluye dos vértices de $\{7,8,9\}$ y dos de ellos comparten un vértice.
He aquí una prueba de que $K_{10}$ est suficiente. En primer lugar, observe que algunos colores $c \in \{\text{red}, \text{blue}\}$ debe tener la siguiente propiedad: no importa qué dos vértices de $K_{10}$ que elijas, hay un $c$ -color monocromático $K_3$ sin usar esos dos vértices.
(Si no, entonces podemos eliminar algunos dos vértices y destruir todos los rojos $K_3$ y, a continuación, eliminar dos vértices y destruir todos los vértices azules. $K_3$ pero ahora seguimos teniendo un grafo completo en $6$ vértices, que sabemos que contiene un rojo o un azul $K_3$ . Contradicción!)
Supongamos que rojo triángulos tienen esta propiedad, y supongamos también que no hay (¿hay?) triángulos rojos $2K_3$ . Esto implica algo mucho más fuerte: dos rojos cualesquiera $K_3$ se cruzan sólo en un vértice o forman parte de una camarilla mayor. Para ver esto, supongamos que tenemos rojo $K_3$ inducida por $\{v_1, v_2, v_3\}$ y $\{v_2, v_3, v_4\}$ . Borrar los vértices $v_2$ y $v_3$ sabemos que debemos ser capaces de encontrar otro rojo $K_3$ . Si interseca a ambos, debe incluir vértices $v_1$ y $v_4$ por lo que la arista $v_1 v_4$ también es rojo.
Así que $\{v_1, v_2, \dots, v_n\}$ sea una camarilla roja máxima. Por la observación anterior, cualquier otro vértice $v_i$ , $i \ge n+1$ sólo puede tener un borde rojo para un de $v_1, \dots, v_n$ . Consideramos dos casos para el valor de $n$ .
Caso 1: ${n\le 4}$ . A continuación, la coloración de los restantes $6$ Los vértices deben tener un $K_3$ ; asumimos que no hay rojo $2K_3$ así que debe ser azul. Además, si los vértices $\{w_1, w_2, w_3\}$ formar el azul $K_3$ entre los vértices restantes debe haber una arista azul $x_1x_2$ (o bien ellos forman un rojo $K_3$ ). Dado que hay como máximo una arista roja $x_1 v_i$ y como máximo una arista roja $x_2 v_j$ , obtenemos otro azul $K_3$ formado por $\{x_1, x_2, v_k\}$ para algunos $k$ disjunta de la primera.
Caso 2: $n=5$ . Si el resto $5$ los vértices no contienen un rojo $K_3$ deben tener al menos dos aristas azules disjuntas $w_1w_2$ y $x_1x_2$ . Cada elemento de $\{w_1, w_2, x_1, x_2\}$ sólo puede tener una arista roja hacia un vértice en $\{v_1,\dots,v_5\}$ por lo que hay al menos tres opciones de $v_i$ y al menos dos opciones $v_j \ne v_i$ tal que $\{w_1, w_2, v_i\}$ y $\{x_1, x_2, v_j\}$ forman azules disjuntos $K_3$ 's.
En ( Burr, Erdős, Spencer 1975 ): $$R(mK_3, nK_3) = 3m+2n \qquad \text{for }m \ge n \ge 2.$$ No lo leí porque quería resolverlo yo mismo, pero probablemente tenga una prueba más bonita.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
