Usbrth

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)^wsum_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 kgeq sum_j=0^a(-1)^j left( sum_i=0^kv-i choose k-ir_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)^jleftsum_Gin G_jleft[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 $Tsqcup(H_1-S)$ is a independient set content in $G$ ; then

$$y-1geq |Tsqcup(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 kgeq sum_j=0^a(-1)^jleft sum_Kin G_jv-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 kgeq sum_i=0^a(-1)^ig_iv 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_Kin G_jv-omega(K) choose k-omega(K)$$

for
$$g_jv 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 sumlimits_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] vchoose k$, as you pointed out, because they summed the same quantity $vchoose 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 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
$$sumlimits_L in G_j^v - omega (L)choose k - omega (L)$$