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é!!!
