A constructive lower bound on Ramsey numbers

Question

The Ramsey's theorem states that

Given $s, t\in \mathbb{N}$, there is $n\in \mathbb{N}$ such that for every graph with $n$ vertices, it contains a $s$-clique or its complement contains a $t$-clique.

The smallest $n$ satisfying the statement is denoted by $R(s, t)$.

I found in the article "The Probabilistic Method in Combinatorics, Lectures by Niranjan Balachandran" the following statement:

A constructive lower bound on R(s, s), discovered by Nagy, is the following: $$R(s, s)\ge \binom{s}{3}$$ (Explicitly, his construction goes as follows: take any set $S$, and turn the collection of all $3$-element subsets of $S$ into a graph by connecting subsets iff their intersection is odd.)

I was not able to prove that this graph and its complement does not contain $s$-cliques. Any help in this matter would be greatly appreciated.

Answer 1

Let's take $S = \{1, 2, \dots, s\}$. What we can actually show is that Nagy's graph has

• cliques of size at most $\max\{7, \frac{s-1}{2}\}$, and
• independent sets of size at most $s-1$ or less when $s \not\equiv 0 \pmod 4$, and at most $s$ when $s \equiv 0 \pmod 4$.

This does not show that $R(s,s) \ge \binom s3$ for all $s$, but it does show that $R(s,s) > \binom s3$, and even that $R(\frac{s}{2}, s) > \binom s3$, for infinitely many values of $s$.

---

First, let's find the largest clique. There are two cases:

• The clique contains $4$ vertices intersecting at the same element of $S$: say, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, and $\{1,8,9\}$. Then every other vertex must contain $1$: otherwise, it would have to have an element from each of $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, and $\{8,9\}$, which is impossible. Such a clique can have at most $\frac{s-1}{2}$ vertices.
• The clique contains at most $3$ vertices intersecting at the same element of $S$. Say $\{1,2,3\}$ is one of the vertices. Then there can be at most $2$ other vertices containing each of $1$, $2$, or $3$, so the clique has at most $7$ vertices.

Next, let's find the largest independent set. Here, note that if two vertices in the independent set share $2$ elements, and third vertex in the independent set shares $2$ elements with one of them, it must share at least one element (and therefore $2$ elements) with the other. So the independent set must consist of clusters, where any two vertices in a cluster share $2$ elements, and any two vertices outside the cluster share $0$.

Once again, clusters can have two different shapes:

• Suppose a cluster has $3$ vertices that all share the same $2$ elements: say, $\{1,2,3\}$, $\{1,2,4\}$,and $\{1,2,5\}$. Another vertex in the cluster that contained only one of $\{1,2\}$ would have to contain each of $3$, $4$, and $5$, which is impossible. So the cluster consists of $k$ vertices of the form $\{1,2,x\}$, which "use up" $k+2$ elements of $S$.
• Suppose a cluster has at most $2$ vertices sharing any $2$ elements. Then if $\{1,2,3\}$ is a vertex in the cluster, each other vertex in the cluster must contain two of $\{1,2,3\}$, but there can be at most one of each kind, for $4$ vertices total. These must use up at least $4$ elements of $S$, such as with $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.

We see that a cluster using up $k$ elements of $S$ can contain at most $k$ vertices, so altogether the clusters can contain at most $S$ vertices. But this is only possible when all clusters are of the second type, and cover all elements of $S$, which requires $s \equiv 0 \pmod 4$.