En primer lugar, vamos a comprobar que $R(3,5)>13$. Como es típico para explícita los límites inferiores en la teoría de Ramsey, nos muestran esta desigualdad mediante la exhibición de un hormigón $\{\mbox{red},\mbox{blue}\}$colorear de $K_{13}$ sin un triángulo rojo o un azul $K_5$.
Una buena manera de describir este colorante es el siguiente: Identificar los vértices de $K_{13}$ con los elementos de la $\mathbb Z/13\mathbb Z=\{0,1,\dots,12\}$, y la de color rojo el borde entre dos vértices $i$ $j$ iff su diferencia es un (distinto de cero) cúbicos de residuos de mod $13$.
El cúbicos de residuos modulo 13$1=1^3=3^3=9^3$, $5=7^3=8^3=11^3$, $8=2^3=5^3=6^3$, y $-1=4^3=10^3=12^3$. Tenga en cuenta que desde $-1$ es un cúbicos de residuos, es indiferente el orden en que se considere la posibilidad de $i$ $j$ cuando se toma su diferencia.
Es fácil ver que este colorante no admitir un triángulo rojo.
A ver que no tenemos una azul $K_5$, argumentan que la de cualquier $5$ vértices que elegir, dos debe ser un cúbicos de residuos separados. Por simetría, podemos suponer que la $0$ es uno de los elegidos, de los vértices. Si cualquiera de $1,5,8,12$ es elegido entre el resto de los cuatro vértices, hemos terminado. De lo contrario, deberán ser elegidos entre los tres "clusters" $2,3,4$, e $6,7$, e $9,10,11$. Dos vértices deben pertenecer al mismo grupo (principio del palomar). Si son consecutivos, hemos terminado. Así que podemos asumir que ellos pertenecen a un grupo de tres, y son dos separados. Por simetría, podemos suponer que son$2$$4$. Esto elimina $3,7,10$ (debido a $2$) y $9$ (debido a $4$). Ahora estamos obligados a elegir $6$ $11$ como el resto de los vértices, pero son $5$ aparte, y hemos terminado.
Segundo, podemos comprobar que $R(3,5)\le 14$. El más simple argumento es mediante el uso de la desigualdad de $R(3,5)\le R(3,4)+R(2,5)$. En general, se $R(m,n)\le R(m-1,n)+R(m,n-1)$. Esto se ha pedido en este sitio antes, una prueba puede ser visto aquí.
Brevemente, si $N=R(m-1,n)+R(m,n-1)$, e $K_N$ $2$- color, podemos arreglar un vértice $v$, y llame a $A$ el conjunto de vértices se unió a $v$ por un arco rojo, y $B$ el conjunto de vértices unidos por un arco azul. A continuación, $|A|\ge R(m-1,n)$ o $|B|\ge R(m,n-1)$. De lo contrario, $N-1=|A|+|B|\le (R(m-1,n)-1)+(R(m,n-1)-1)=N-2$. En el primer caso, o tenemos un azul $K_n$ entre los vértices en $A$, y hemos terminado, o tenemos una red $K_{m-1}$. Pero todos estos vértices se unen a $v$ por un arco rojo, así que la adición de $v$ nos da un rojo $K_m$. El otro caso es similar.
Claramente, $R(2,5)=5$. Estamos por hacer si queremos mostrar que $R(3,4)=9$. El argumento anterior sólo da $R(3,4)\le R(3,3)+R(2,4)=6+4=10$. A ver que $9$ vértices suficiente, tenga en cuenta que por el argumento general que nos dio, si tenemos un $2$colorear de $K_9$ sin triángulos de color rojo o azul $K_4$s, se debe tener que el azul del grado de cada vértice es $5$ y sus roja de grado es $3$. Pero esto es imposible, porque la suma de la roja grados es el doble del número de bordes rojos, sino $9\times 3=27$.
En general, lo que dice es que si tanto $R(n-1,m)$ $R(n,m-1)$ son incluso, a continuación,$R(n,m)<R(n-1,m)+R(n,m-1)$.
Esto completa la prueba. Permítanme añadir algunas referencias. El primer argumento en la impresión mostrando que $R(3,5)=14$ es de
Para arriba-a-fecha de la encuesta de pequeños números de Ramsey, incluyendo referencias, ver
- Stanislaw Radziszowski. Pequeño Ramsey Números, La Revista Electrónica de la Combinatoria, la Dinámica de la encuesta DS1, la versión más reciente: 22 de agosto de 2011.
Siempre es agradable ver una imagen de los gráficos uno está describiendo. El colorante de $K_{13}$ I se mencionó anteriormente puede ser visto aquí (con el rojo y el azul intercambiados).
Por último, permítanme mencionar que el argumento esbozado en la pregunta es deficiente, porque no hay simetría en las funciones de rojo y azul (que es ciertamente más fácil de asegurar la existencia de un triángulo azul de la existencia de un azul $K_5$).
