Pruébalo: $[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j \left( \sum_{i=0}^k{v-i \choose k-i}r_i(j)\right)+\epsilon(a,k,p)$

Question

Estoy estudiando los números de Ramsey, especialmente $R(3,6)=18$ para Graver y Jackel, y he tratado de entender el teorema $2$ desde hace tiempo, pero no lo he conseguido.

Teorema 1: Sea $G$ sea un gráfico con circunferencia $z$ y que $g_i$ sea el número de subgrafos conectados de $G$ con $i$ bordes. Entonces para todos los enteros $w < z$ ,

$$(-1)^wI(G)\leq (-1)^w\sum_{i=0}^w(-1)^ig_i$$

---

Donde la circunferencia de un gráfico es la longitud de un ciclo más corto contenido en el gráfico.

$I(G)$ : Conjunto máximo independiente de $G$

$G$ es un $(3, y)$ -gráfica si $3 > C(G)$ y $y > I(G)$ es decir, en un $(3,y)$ -gráfica no puede haber triángulos.

---

Consideremos un conjunto independiente $H_1$ en un $(3, y)$ -gráfica $G$ y que $H_2$ sea el subgrafo abarcado por los puntos restantes. Un punto $p$ de $H_2$ se dice que está por encima de un conjunto de puntos $S$ de $H_1$ si todas las aristas de $p$ a $H_1$ tienen su otro punto final en $S$ . Cualquier subgrafo de $H_2$ se dirá que está por encima de $S$ si todos sus puntos están por encima de $S$ . Por último, definimos el gráfico con soporte $S$ (supp) como el subgrafo en $H_2$ abarcados por los puntos de $H_2$ que están por encima de $S$ .

---

Teorema 2: Sea $G$ ser un $(3, y)$ -con un conjunto independiente $H_1$ . En cualquier caso, dejemos $H_1$ contienen $v$ puntos y dejar que $r_i(j)$ sea el número de subgrafos conectados de $H_2$ con $j$ bordes y tener un total de $i$ bordes de estos puntos de $H_2$ a los puntos de $H_1$ . Además, deja que $G_j$ sea el conjunto de subgrafos conectados de $H_2$ con j aristas. Para $K$ un subgrafo de $H_2$ , dejemos que $\omega(K)$ sea el número de puntos de $H_1$ que se unen a $K$ por un borde y $\mu(K)$ es igual al número de aristas de $K$ a $H_1$ . Entonces

$$[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j \left( \sum_{i=0}^k{v-i \choose k-i}r_i(j)\right)+\epsilon(a,k,p)$$

donde $a$ es impar y todos los subgrafos de $G$ con un $k$ -ser el soporte tiene una circunferencia mayor que $a$ y donde

$$\epsilon(a,k,p)=\sum_{j=0}^a(-1)^j\left\{\sum_{G\in G_j}\left[{v-\omega(G) \choose k-\omega(G)}- {v-\mu(G) \choose k-\mu(G)}\right] \right\}$$

Prueba (reformulada para mí):

Dado que $G$ es $(3,y)-graph$ y $H_1$ es un conjunto independiente, entonces $v=|H_1|\leq y-1$ Es decir, que $(y-1)-(v-k)\geq 0$ . Ahora, consigue $T$ un conjunto máximo independiente en $K$ $(|T|=I(K))$ entonces $T\sqcup(H_1-S)$ es un contenido de conjunto independiente en $G$ Entonces

$$y-1\geq |T\sqcup(H_1-S)|=I(K)+(v-k)$$ $$[k+y-1-v] \geq I(K)$$

para el teorema $1$

$$I(K)\geq \sum_{i=0}^a(-1)^ig_i$$ donde $g_i$ es el número de subgrafos conectados de $K$ que tienen $i$ bordes. Por lo tanto, $$[k+y-1-v] \geq \sum_{i=0}^a(-1)^ig_i$$

part of the test that I do not understand:

Ahora, sumando esta desigualdad sobre todos los subconjuntos de $H_1$ que contiene $k$ puntos, el lado izquierdo es $$[k+y-1-v]{v \choose k}$$

Para calcular el lado derecho considere un subgrafo conectado $K$ con $j$ bordes ( $K \in G_j$ ). K estará exactamente por encima de $${v-\omega(K) \choose k-\omega(K)}$$ $k$ -conjuntos de $H_1$ y por lo tanto aparecerá en la suma que muchas veces con $(-1)^j$ como coeficiente cada vez. Así,

$$[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j\left\{ \sum_{K\in G_j}{v-\omega(K) \choose k-\omega(K)} \right\}$$

---

TRY:

En primer lugar, todos los subconjuntos de $H_1$ que contiene $k$ los puntos son ${v \choose k}$ entonces $$[k+y-1-v]{v \choose k}\geq \sum_{i=0}^a(-1)^ig_i{v \choose k}$$

En segundo lugar, sé que si $\omega(K)=|supp(K)|\leq k$ , entonces el número de $k$ -subrayado $S$ de $H_1$ tal que $K$ está por encima de $S$ son exactamente $${v-\omega(K) \choose k-\omega(K)}$$

pero no entiendo cómo puede reemplazar $$\sum_{K\in G_j}{v-\omega(K) \choose k-\omega(K)}$$

para $$g_j{v \choose k}$$

¡¡¡me pueden ayudar a entender ese punto, o estaré entendiendo mal y no lo reemplazaré!!!

Answer 1

Creo que no sustituyen a esos dos términos que has descrito en tu sección "TRY:". En cambio, hacen lo siguiente. Primero, toman un arreglo $S \subseteq H_1$ donde $|S| = k$ . Obsérvese que el gráfico $K$ con el apoyo de $S$ es única (porque se pueden tomar esos puntos de $H_2$ en $K$ tener a todos sus vecinos en $S$ ). Ahora, como has señalado, aplican el teorema 1 para esto $K$ , lo que finalmente resulta en
$$[k + y - 1 - v] \geq \sum\limits_{i=0}^a (-1)^i g_i$$ donde $g_i$ es el número de subgrafos conectados de $K$ teniendo $i$ bordes . Recordemos que esta desigualdad es válida para un $K$ determinado por el fijo $S$ que eligieron al principio.

Lo que hacen ahora es sumar esta desigualdad para todos esos $S \subseteq H_1$ que tiene $k$ elementos. El lado izquierdo es $[k + y - 1 -v] {v\choose k}$ como usted señaló, porque sumaron la misma cantidad ${v\choose k}$ tiempos.

En el lado derecho de su desigualdad, cuentan subgrafos de los grafos $K$ determinado por el $S$ conjuntos. Como el soporte de uno de estos $K$ es $S$ cualquier subgrafo de $K$ debe estar por encima de $S$ . La cuestión es que después de haber sumado estas desigualdades para todos esos $S$ , cuántas veces un subgrafo fijo de $H_2$ teniendo $j$ ¿se cuentan los bordes?

Para responder a esto, dejemos que $L$ sea un subgrafo conexo de $H_2$ teniendo $j$ bordes (en el documento original, utilizan la notación $K$ pero eso es otra cosa. $K$ del que introdujeron antes). Como ha podido comprobar, este $L$ está por encima de ${v - \omega (L)\choose k - \omega (L)}$ casos de este tipo $S \subseteq H_1$ que tiene $k$ elementos. Esto significa que en el lado derecho de la suma de esas desigualdades, $L$ se contará exactamente ${v - \omega (L)\choose k - \omega (L)}$ ¡tiempos! Como todos los subgráficos de $H_2$ teniendo $j$ Los bordes se cuentan esta cantidad de veces, el término multiplicado por $(-1)^j$ es $$\sum\limits_{L \in G_j}^{}{{v - \omega (L)\choose k - \omega (L)}}$$

Edición 1: Más detalles de la última parte

Considere el siguiente enfoque. Sea $A = \{S_{1}, ... S_{{v\choose k}}\}$ sea el conjunto de todos los subconjuntos de $H_1$ teniendo $k$ elementos y que el conjunto de los gráficos soportados por estos sea $B = \{K_{1},...,K_{{v\choose k}}\}$ respectivamente. Sea $g_{i}^{K_j}$ denotan el número de subgrafos conectados de $K_j$ teniendo $i$ bordes. Ahora sumemos la desigualdad mencionada a todas estas $K_{n}$ gráficos: $$\sum\limits_{K_{n} \in B}^{}[k + y - 1 - v] \geq \sum\limits_{K_{n} \in B}^{}\sum\limits_{i = 0}^{a}(-1)^{i}g_{i}^{K_n}$$ Esta es la descripción formal de lo que hacen en la prueba (y también lo que intenté expresar en mi respuesta). Cambiando las sumas del lado derecho obtenemos:
$$\sum\limits_{i = 0}^{a}\sum\limits_{K_{n} \in B}^{}(-1)^{i}g_{i}^{K_n} = \sum\limits_{i = 0}^{a} (-1)^{i} \sum\limits_{K_{n} \in B}^{}g_{i}^{K_n}$$ Ahora la pregunta sería que cuántas veces un fijo $L$ subgrafo conectado de $H_2$ con $j$ bordes se cuenta en la suma $$\sum\limits_{K_{n} \in B}^{} g_{i}^{K_{n}}$$ y esto se explica en mi respuesta original.
Una observación adicional. Si tal $L$ no es un subgrafo de ningún $K_{n} \in B$ , lo que significa que $L$ no está por encima de ningún $k$ -conjunto de $H_1$ , lo que significa que $\omega (L) > k$ y el coeficiente binomial correspondiente será cero, por lo que $L$ no se cuenta (correctamente).