I'm studying the ramsey numbers, especially $R(3,6)=18$ for Graver and Jackel, and i have tried to understand the theorem $2$ for quite some time but I have not succeeded.
Theorem 1: Let $G$ be a graph with girth $z$ and let $g_i$ be the number of connected subgraphs of $G$ with $i$ edges. Then for all integers $w < z$,
$$(-1)^wI(G)\leq (-1)^w\sum_{i=0}^w(-1)^ig_i$$
Where the girth of a graph is the length of a shortest cycle contained in the graph.
$I(G)$: Maximum independient set of $G$
$G$ is an $(3, y)$-graph if $3 > C(G)$ and $y > I(G)$, that is to say, in a $(3,y)$-graph there can not be triangles.
Consider an independent set $H_1$ in a $(3, y)$-graph $G$ and let $H_2$ be the subgraph spanned by the remaining points. A point $p$ of $H_2$ is said to be above a set of points $S$ from $H_1$ if all edges from $p$ to $H_1$ have their other end-point in $S$. Any subgraph of $H_2$ will be said to be above $S$ if all of its points are above $S$. Finally we define the graph with support $S$ (supp) as the subgraph in $H_2$ spanned by the points of $H_2$ which are above $S$.
Theorem 2: Let $G$ be a $(3, y)$-graph with a independent set $H_1$. In either case let $H_1$ contain $v$ points and let $r_i(j)$ be the number of connected subgraphs of $H_2$ with $j$ edges and having a total of $i$ edges from these points of $H_2$ to points of $H_1$. Also let $G_j$ be the set of connected subgraphs of $H_2$ with j edges. For $K$ a subgraph of $H_2$, let $\omega(K)$ be the number of points of $H_1$ which are joined to $K$ by an edge and $\mu(K)$ equal the number of edges from $K$ to $H_1$ . Then
$$[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)$$
where $a$ is odd and all subgraphs of $G$ with a $k$-set as support have girth greater than $a$, and where
$$\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\}$$
Proof (reformulated for me):
Given that $G$ is $(3,y)-graph$ and $H_1$ is a independient set, then $v=|H_1|\leq y-1$, that is to say $(y-1)-(v-k)\geq 0$. Now, get $T$ a maximum independient set in $K$ $(|T|=I(K))$, then $T\sqcup(H_1-S)$ is a independient set content in $G$ ; then
$$y-1\geq |T\sqcup(H_1-S)|=I(K)+(v-k)$$ $$[k+y-1-v] \geq I(K)$$
for theorem $1$
$$I(K)\geq \sum_{i=0}^a(-1)^ig_i$$ where $g_i$ is the number of connected subgraphs of $K$ which have $i$ edges. Hence $$[k+y-1-v] \geq \sum_{i=0}^a(-1)^ig_i$$
part of the test that I do not understand:
Now summing this inequality over all subsets of $H_1$ containing $k$ points, the left side is $$[k+y-1-v]{v \choose k}$$
To compute the right side consider a connected subgraph $K$ with $j$ edges ($K \in G_j$). K will be above exactly $${v-\omega(K) \choose k-\omega(K)}$$ $k$-sets of $H_1$ and hence will appear in the summation that many times with $(-1)^j$ as a coefficient each time. Thus
$$[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:
First, all subsets of $H_1$ containing $k$ points are ${v \choose k}$, then $$[k+y-1-v]{v \choose k}\geq \sum_{i=0}^a(-1)^ig_i{v \choose k}$$
Second, I know that if $\omega(K)=|supp(K)|\leq k$, then the number of $k$-subset $S$ of $H_1$ such that $K$ is above $S$ are exactly $${v-\omega(K) \choose k-\omega(K)}$$
but i dont understand how can he replace $$\sum_{K\in G_j}{v-\omega(K) \choose k-\omega(K)}$$
for $$g_j{v \choose k}$$
can you help me understand that point, or will I be misunderstanding and not replacing.!!
I believe that they do not replace those two terms you described in your "TRY:" section. Instead, they do the following. First, they take one fix $S \subseteq H_1$ where $|S| = k$. Note, that the graph $K$ supported by $S$ is unique (because one can take those points of $H_2$ into $K$ having all of their neighbors in $S$). Now, as you pointed out, they apply theorem 1 for this $K$, eventually resulting in
$$[k + y - 1 - v] \geq \sum\limits_{i=0}^a (-1)^i g_i$$ where $g_i$ is the number of connected subgraphs of $K$ having $i$ edges. Remember, this inequality holds for a fixed $K$ determined by the fixed $S$ they chose at the beginning.
What they do now is summing this inequality for all such $S \subseteq H_1$ that has $k$ elements. The left side is $[k + y - 1 -v] {v\choose k}$, as you pointed out, because they summed the same quantity ${v\choose k}$ times.
On the right side of their inequality, they count subgraphs of the graphs $K$ determined by the $S$ sets. As the support of one such $K$ is $S$, any subgraph of $K$ must be above $S$. The question is that after they summed these inequalities for all such $S$, how many times one fixed subgraph of $H_2$ having $j$ edges is counted?
To answer this, let $L$ be a connected subgraph of $H_2$ having $j$ edges (in the original paper, they use the notation $K$, but that is a different $K$ from the one they introduced before). As you noticed, this $L$ is above ${v - \omega (L)\choose k - \omega (L)}$ instances of such $S \subseteq H_1$ that has $k$ elements. This means that on the right side of the summation of those inequalities, $L$ will be counted exactly ${v - \omega (L)\choose k - \omega (L)}$ times! As all the subgraphs of $H_2$ having $j$ edges are counted this many times, the term multiplied by $(-1)^j$ is $$\sum\limits_{L \in G_j}^{}{{v - \omega (L)\choose k - \omega (L)}}$$
Edit 1: More details of the last part
Consider the following approach. Let $A = \{S_{1}, ... S_{{v\choose k}}\}$ be the set of all the subsets of $H_1$ having $k$ elements and let the set of the graphs supported by these be $B = \{K_{1},...,K_{{v\choose k}}\}$, respectively. Let $g_{i}^{K_j}$ denote the number of connected subgraphs of $K_j$ having $i$ edges. Now let's sum the above mentioned inequality to all these $K_{n}$ graphs: $$\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}$$ This is the formal description of what they do in the proof (and also what I tried to express in my answer). By changing the sums on the right side we get:
$$\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}$$ Now the question would be that how many times a fixed $L$ connected subgraph of $H_2$ with $j$ edges is counted in the sum $$\sum\limits_{K_{n} \in B}^{} g_{i}^{K_{n}}$$ and this is explained in my original answer.
One additional remark. If such an $L$ graph is not a subgraph of any $K_{n} \in B$, that means that $L$ is not above any $k$-set of $H_1$, meaning that $\omega (L) > k$ and the corresponding binomial coefficient will be zero, hence $L$ is (correctly) not counted.