Ramsey number $R(3,7)=23$

Question

Im reading the prove the Ramsey of number $R(3,7)=23$ of "Some Graph Theoretic Results Associated with Ramsey’s Theorem"JACK and JAMES YACKEL.

$G$ is an $(x,y)$-graph if $x>C(G)$ and $y>I(G)$, where $I(G)$ is the maximum number of points of $G$ that can be chosen so that no two are joined by an edge and $C(G)$ is the maximum number of points in any complete subgraph of $G$. (in other word, $G$ is a graph that does not have cliques of size $x$ neither independent sets of size $y$)

Define: Let $G$ be a graph and $p$ a point of $G$. By $H_1$ we will mean the graph spanned by all points of $G$ which are joined to $p$ by an edge. $H_2$ will denote the graph spanned by all points different from $p$ which are not joined to $p$ by an edge. In the proof to Lemma $2$ we proved that if $G$ is an $(x, y)$-graph then $H_1$ is an $(x- 1, y)$-graph and $H_2$ is an $(x, y- 1)$-graph. We will indicate this disection of $G$ by stating that $p$ is the preferred. point.

The autor define: $R'(x,y)$ is the largest integer such that there is an $(x, y)$-graph on $R'(x,y)$ points. In other words $R'(x,y)=R(x,y)-1$, at the end of the article prove that $R(3,7)\geq 22$, but there are several things that I can't understand,

If someone could break me down a bit, the demonstration would greatly appreciate it.

I don't understand why there are many triangles and they are in H2.. In $R'(3,7)\leq 22$ prove that $G$ contains only points of valence $6$.

Answer 1

Let's first deal with the fact that there are many triangles and these are in $H_2$.

Think of the points as being in three groups:-

The preferred point $p$

The six points $p_1, ..., p_6$ of $H_1$ which are joined to $p$

The 15 points $p_{ij}$ of $H_2$, each of which is joined to two of the points in $H_1$ and to six of the points in $H_2$.

Now let us look at possibilities for triangles.

(1) Consider the point $p$. This is only joined to points of $H_1$ and no two points of $H_2$ are joined to each other so $p$ is not in a triangle.

(2) Consider the point $p_1$ of $H_1$. This is joined to the five points $p_{12}, ..., p_{16}$ of $H_2$ but no pair of these points are joined and so $p_1$ is not in a triangle. Similarly no point of $H_1$ is in a triangle.

We now know that triangles can only be in $H_2$.

Let's look for just those which include $p_{12}$. They are $p_{12},p_{34},p_{56}$ and $p_{12},p_{35},p_{46}$ and $p_{12},p_{36},p_{45}$ and ...

There are lots!

The next part of the proof starts with the assertion that the reduced $H_2$ (i.e. with the Hamiltonian cycle removed) is a (3,6) graph.

The author does not prove this but you might like to check that you can see this to be true.

Once you have done this it is now obvious that the reduced graph $G$ has no triangles because all the original triangles were in $H_2$. So the crux of the proof is to obtain a contradiction to the supposition:

Suppose G has an independent set of size 7

Since $H_2$ has no independent set of size 6 we would require at least two points from $p,p_1, ..., p_6$. However, $p$ is joined to the points of $H_1$ and so we require at least two points from $H_1$.

If we had three points from $H_1$, say $p_1, p_2, p_3$, then the only points from $H_2$ that we can have are $p_{45},p_{46},p_{56}$ i.e a maximum of 6 points. Similarly, if we had four points from $H_1$, then we can have only 1 point from $H_2$ and if we had five or six points from $H_1$, then we can have no points from $H_2$.

The only case needing study is if we have two points from $H_1$, say $p_1, p_2$.

This is an important part of the author's construction so check that you understand the set up we now have. The only points in $H_2$ independent of $p_1, p_2$ are $$p_{34}-p_{56},p_{35}-p_{46},p_{36}-p_{45}$$ where the dashes indicate edges in the author's original graph. So, for an independent set of size 7 we require at least two of these three edges to be in the Hamiltonian cycle that was removed. A quick check will show you that only $p_{34}-p_{56}$ has been removed and so there is no independent set of size 7 including $p_1, p_2$.

Now we have to do this analysis for any two distinct points $p_x, p_y$ of $H_1$. Therefore we must prove that for any four distinct indices $a,b,c,d$, at most one of the three edges in $$p_{ab}-p_{cd},p_{ac}-p_{bd},p_{ad}-p_{bc}$$ are in the Hamiltonian cycle. This has to be checked; the author does not do so but claims that the check is easy. (At worst it's a mechanical task and you may spot some clever shortcuts.)

Answer 2

Addendum - A proof of the claim that the reduced $H_2$ has no independent set of size 6

Suppose that there is a set $X$ of 6 independent points.

First we prove $X$ is not independent in $H_2$

In view of the symmetry of $H_2$ we can suppose that $p_{12} \in X$. The only points in $H_2$ independent of $p_{12}$ are $p_{13}-p_{24},p_{14}-p_{23},p_{15}-p_{26},p_{16}-p_{25}$ where the dashes indicate some of the edges in $H_2$. We can only have one of each pair of joined points in $X$ and so there can be at most $5$ independent points in $H_2$.

We now know that $X$ contains two adjacent points in the Hamiltonian path

There are 15 possibilities (unless we establish some symmetries amongst the points in the path). We shall consider one possibility; that $X$ contains $p_{35}$ and $p_{16}$.

The only points independent of both $p_{35}$ and $p_{16}$ in the reduced $H_2$ are either adjacent to one of them in the Hamiltonian path or contain both one of the suffices $3,5$ and one of the suffices $1,6$. So the possibilities are $p_{12}-p_{36},p_{13}-p_{56},p_{15}-p_{23}$ where the dashes indicate some of the edges in the reduced $H_2$. Again there can be at most $5$ independent points.

Answer 3

Above answers solve the problem, but they leave a lot of cases that must be explored. This answer eliminates most of the cases by exhibiting symmetry. Note that the graph $H_2$ is the complement of the line graph $L(K_6)$. This implies that any permutation of the indices is an automorphism. We will take $p_{i,j}$ to be the pair $\{i,j\}$ (which allows us to ignore the ordering of $i$ and $j$). When using digits as elements of a pair, we will just concatenate them, e.g. we will write $12$ for $\{1,2\}$. We see that the Hamiltonian cycle has $5$ groups of $3$ pairs, where the middle pair always contains the element $5$. We use a permutation that makes the fixed element of the middle pair equal to $1$, and that makes the other element in the middle pair increasing.

The new Hamiltonian cycle looks like $P_2,P_3,P_4,P_5,P_6$ where $P_i$ is the sequence $\{i+3,i+4\},\{1,i\},\{i+1,i+3\}$ (in this proof we use modular arithmetic in $S=\{2,3,4,5,6\}$, i.e. $6+1=2$).

Showing that the reduced $H_2$ has no triangle now reduces to one single case, as follows.

Any triangle contains three pairs that partition $[6]$, so it contains some pair $\{1,i\}$. Looking at part $P_i$ of the Hamiltonian cycle we see that the triangle cannot contain $\{i+3,i+4\}$ (with third vertex $\{i+1,i+2\}$) and it cannot contain $\{i+1,i+3\}$ (with third vertex $\{i+2,i+4\}$). Since the triangle must contain a pair containing $i+3$, the only remaining possibility is that the triangle contains $\{i+2,i+3\}$ and the third vertex must be $\{i+1,i+4\}$. However $\{i+2,i+3\}$ is the first element of $P_{i-1}$ and $\{i+1,i+4\}$ is the last element of $P_{i-2}$, and these are not adjacent in the reduced $H_2$. So there cannot be a triangle in the reduced $H_2$.

Proving that the reduced $H_2$ has no independent set of size $6$ requires three cases, as follows.

$\alpha(H_2)=5$ (remember that $H_2$ is the complement of $L(K_6)$), so in order to get an independent set $I$ of size $6$ in the reduced $H_2$, at least $2$ vertices in $I$ must be separated by an edge of the Hamiltonian cycle. Because of the rotational symmetry (the cyclic permutation $(2,3,4,5,6)$ of the elements of the pairs is an automorphism of the reduced $H_2$) we may assume that this edge is either in $P_1$, or between $P_1$ and $P_2$. This gives us three cases to analyze.

Case 1: Both $12$ and $56$ are in $I$. $12$ blocks $34,35,36,45,46,56$ in $H_2$, but $35$ and $56$ are unblocked by the Hamiltonian cycle. $56$ blocks $12,13,14,23,24,34$ in $H_2$, but $12$ and $24$ are unblocked by the Hamiltonian cycle. This means that the remaining $4$ points of $I$ must be chosen from $15,16,24,25,26,35$, but these points induce $P_6$ ($25,16,35,24,15,26$) in the reduced $H_2$, which has no independent set of size $4$.

Case 2: Both $(1,2)$ and $(3,5)$ are in $I$. Similar.

Case 3: Both $(2,6)$ and $(3,5)$ are in $I$. Similar.