Un límite inferior constructivo en los números de Ramsey
El teorema de Ramsey establece que
Dado $s, t\in \mathbb{N}$, Ahi esta $n\in \mathbb{N}$ tal que para cada gráfico con $n$ vértices, contiene un $s$-clique o su complemento contiene un $t$-camarilla.
El mas pequeño $n$ Satisfacer la declaración se denota por $R(s, t)$.
Encontré en el artículo "El método probabilístico en combinatoria, conferencias de Niranjan Balachandran" la siguiente declaración:
Un límite inferior constructivo en R (s, s), descubierto por Nagy, es el siguiente: $$R(s, s)\ge \binom{s}{3}$$ (Explícitamente, su construcción es la siguiente: tome cualquier conjunto $S$y convertir la colección de todos $3$-subconjuntos de elementos de $S$ en un gráfico conectando subconjuntos si su intersección es impar).
No pude probar que este gráfico y su complemento no contienen $s$-cliques. Cualquier ayuda en este asunto sería muy apreciada.
Respuestas
Echemos $S = \{1, 2, \dots, s\}$. Lo que realmente podemos mostrar es que la gráfica de Nagy tiene
- camarillas de tamaño como máximo $\max\{7, \frac{s-1}{2}\}$y
- conjuntos independientes de tamaño como máximo $s-1$ o menos cuando $s \not\equiv 0 \pmod 4$, y como mucho $s$ cuando $s \equiv 0 \pmod 4$.
Esto no demuestra que $R(s,s) \ge \binom s3$ para todos $s$, pero muestra que $R(s,s) > \binom s3$, e incluso eso $R(\frac{s}{2}, s) > \binom s3$, para infinitos valores de $s$.
Primero, busquemos la camarilla más grande. Hay dos casos:
- La camarilla contiene $4$ vértices que se cruzan en el mismo elemento de $S$: decir, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$y $\{1,8,9\}$. Entonces todos los demás vértices deben contener$1$: de lo contrario, tendría que tener un elemento de cada uno de $\{2,3\}$, $\{4,5\}$, $\{6,7\}$y $\{8,9\}$, lo cual es imposible. Tal camarilla puede tener como mucho$\frac{s-1}{2}$ vértices.
- La camarilla contiene como máximo $3$ vértices que se cruzan en el mismo elemento de $S$. Decir$\{1,2,3\}$es uno de los vértices. Entonces puede haber como máximo$2$ otros vértices que contienen cada uno de $1$, $2$o $3$, entonces la camarilla tiene como máximo $7$ vértices.
A continuación, busquemos el conjunto independiente más grande. Aquí, observe que si dos vértices en el conjunto independiente comparten$2$ elementos, y tercer vértice en el conjunto independiente comparte $2$ elementos con uno de ellos, debe compartir al menos un elemento (y por lo tanto $2$elementos) con el otro. Por tanto, el conjunto independiente debe constar de grupos, donde dos vértices cualesquiera de un grupo comparten$2$ elementos, y dos vértices fuera del clúster comparten $0$.
Una vez más, los grupos pueden tener dos formas diferentes:
- Suponga que un clúster tiene $3$ vértices que todos comparten lo mismo $2$ elementos: decir, $\{1,2,3\}$, $\{1,2,4\}$,y $\{1,2,5\}$. Otro vértice en el grupo que contenía solo uno de$\{1,2\}$ tendría que contener cada uno de $3$, $4$y $5$, lo cual es imposible. Entonces el clúster consta de$k$ vértices de la forma $\{1,2,x\}$, que "agotar" $k+2$ elementos de $S$.
- Suponga que un clúster tiene como máximo $2$ vértices que comparten cualquier $2$elementos. Entonces sí$\{1,2,3\}$ es un vértice en el grupo, cada uno de los otros vértices en el grupo debe contener dos de $\{1,2,3\}$, pero puede haber como máximo uno de cada tipo, por $4$vértices totales. Estos deben consumir al menos$4$ elementos de $S$, como con $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
Vemos que un clúster agota $k$ elementos de $S$ puede contener como máximo $k$ vértices, por lo que en conjunto los grupos pueden contener como máximo $S$vértices. Pero esto solo es posible cuando todos los grupos son del segundo tipo y cubren todos los elementos de$S$, que requiere $s \equiv 0 \pmod 4$.