Contraejemplo para $R(4,4) \neq 8$

Question

Intento encontrar un contraejemplo para $R(4,4)\neq 8$. (R es el de Ramsey-número).

Me dibujó un gráfico con 8 vedges y yo de color de todos los bordes $(v_i,v_j)$ con $i-j =\pm 2,4,6$ en el mismo color (por ejemplo rojo). Pero, a continuación, voy a buscar una $K_4$ con $(v_1,v_3,v_5,v_7)$, que definitivamente no es un contraejemplo.

Tal vez alguien puede ayudarme a salir de aquí? Gracias de antemano.

Answer 1

He aquí una prueba de que $R(4,4)>17$ que yo "prestado" de cortar el nudo. Tomamos el $17$-vértice circulantes gráfico con los bordes de las distancias de $\{1,2,4,8\}$ como los bordes rojos y distancias $\{3,5,6,7\}$ como el azul de bordes.

Así tenemos los bordes rojos:

y el azul de bordes:

Dado que el gráfico es el vértice transitiva es suficiente para comprobar que el barrio de algunos fijos vértice no contiene un inducida por monocromática $K_3$.

Comprobamos la monocromía de los barrios:

y

y encontrar que no hay triángulos (omitiendo los puntos de los bordes).

Answer 2

Una manera sencilla de ver que $R(4,4) > 9$ es tomar tres desconectado copias de $K_3$:s. Por supuesto, esto está muy lejos de ser óptima, ya que el valor real es de $R(4,4)=18$.