Explicit Ramsey Bounds & ChatGPT

These days, I do not spend much time writing for my blog. I wrote many nice papers in the last year that deserve their own articles. In particular, I wrote papers with Andrey Kupavskii on the structure of intersecting families and on a $q$-analog of the Erdős–Rado Sunflower Conjecture, and with Yue Zhou on locally repairable codes, together with recent work by Cosmin Pohoata and his coauthors that essentially solves the problem. I can offer talks on these topics here, here, and here (in the same order, some miss the blackboard pictures).

But now I have an urgent reason for a blog post! I started this blog for things that do not belong in my other writings. And I wrote my first paper to which ChatGPT contributed: a paper on explicit constructions for Ramsey numbers, with Sam Mattheus. It is valuable to document how one uses ChatGPT in detail, but I also do not think that lengthy descriptions of technical details belong in a math paper.

For background on Ramsey numbers and their explicit constructions, I refer to my preliminary slides for a short talk on the topic. At the time of writing this blog post and the preprint with Sam Mattheus, we both had access only to ChatGPT Plus. Almost all of the work below was done with ChatGPT 5.6 in a Plus chat on High. This post is partially motivated by a comment on Reddit on our preprint.

Some Background

For the discussion below, let us quickly recall the standard explicit bounds for Ramsey numbers. In 1981, Frankl and Wilson showed

\[ R(s,s) \geq s^{(\frac14-o(1))\log s/\log\log s} \]

using a beautiful $p$-rank argument for set systems. Alternative constructions with the same logarithmic order of magnitude were given by Alon (1998) and Grolmusz (2000).

A line of work using quite elaborate polynomial-time algorithmic techniques, from Barak, Rao, Shaltiel, and Wigderson (2012) to Xin Li (2023), obtained better explicit bounds on $R(s,s)$, but there is surely still some merit in asking about “beautiful” explicit constructions.

For off-diagonal Ramsey numbers, Alon and Pudlák (2001) showed

\[ R(s,t) \geq t^{\varepsilon\sqrt{\log s/\log\log s}}, \]

without working out the exact constants (which are terrible), while Kostochka, Pudlák, and Rödl (2010) showed

\[ R(4,t)=\Omega(t^{8/5}), \qquad R(5,t)=\Omega(t^{5/3}), \qquad R(6,t)=\Omega(t^2). \]

Earlier, in 1994, Alon had obtained the explicit bound $R(3,t)=\Omega(t^{3/2})$ in Explicit Ramsey graphs and orthonormal labelings.

Idea

I have thought about explicit Ramsey bounds since my time as a PhD student, perhaps since 2014. During that time, I had many conceptual ideas, but I could never find a construction that worked. One fundamental problem is not finding a construction that probably works, but finding one for which this can actually be proved.

One very old idea of mine was to use $p$-ranks in the context of finite geometry. The famous explicit Ramsey bound of Frankl and Wilson, of course, uses $p$-ranks, but for set systems. The key idea is that a large independent set corresponds to a matrix of full $p$-rank that is necessarily a principal submatrix of a matrix of small $p$-rank.

Many incidence matrices in finite geometry are known to have incredibly small $p$-rank. For instance, I have a paper with Peter Sin and Qing Xiang about such ranks in generalized polygons. I also explored the connection between $p$-ranks and Ramsey numbers far more recently with John Bamberg, Anurag Bishnoi, and Ananthakrishnan Ravi in Ramsey numbers and extremal structures in polar spaces. The main problem with all these approaches was that I focused on special cases that are almost guaranteed to have large cliques (for insiders: because they correspond to totally isotropic subspaces in some sense).

The new general idea was the following:

• The $2$-rank of the point–hyperplane incidence matrix in $PG(d-1,2^h)$ is $d^h+1$.
• Take a family $\mathcal{F}$ of point–hyperplane flags $(P,H)$ as vertices.
• Declare two flags $(P,H)$ and $(Q,G)$ adjacent if $P\in G$ and $Q\in H$. It is very straightforward to see that the independence number is then bounded by $(d^h+1)^2$ if each point and each hyperplane occurs at most once in $\mathcal{F}$.

The “only” problem was that I was not sure how best to choose such a family of point–hyperplane flags. This gets us to my ChatGPT queries, the main point of this post.

The ChatGPT Queries

As mentioned above, this was all done in a ChatGPT 5.6 Plus chat on High:

Can we pick 15 point-hyperplane flags in PG(3, 2) such that the following is true: take the flags as vertices. Two are incident if the point of the one flag is on the hyperplane of the other flag. We do not want the resulting graph to have a clique of size 3

I interrupted this after 3 minutes, as I forgot to add the following (which I thought was needed for the $p$-rank argument, but is not, as Sam pointed out while reading a draft of this):

No point or hyperplane should be used more than once

Otherwise, there is also an easy solution to my question. But you might notice that I still phrased the question badly, as I forgot a “vice versa” in the adjacency definition. ChatGPT pointed this out in its answer. Under the intended condition, it found 15 point–hyperplane flags. My follow-up was:

So we are $K_4$-free? What about one dimension higher? Can we pick 31 and be $K_5$-free?

Here it gave me a construction in $PG(4,2)$, so I was happy and got more ambitious:

Can we also choose $PG(4,2^h)$ with $(2^{5h}-1)/(2^h-1)$ point-hyperplane flags such that we have no $K_4$?

Here the answer became Remark 2.2 in our preprint, specialized to $PG(4,2^h)$. Nothing looked specific to dimension $4$, so this was already the main work in finding the construction. For reference, here is the definition from the preprint:

Definition. Write $q=2^h$ and write $\operatorname{Tr}$ for the trace from $\mathbb{F}_{q^d}$ to $\mathbb{F}_q$. Put $V=\mathbb{F}_{q^d}$. Choose $\beta\in V$ such that

\[ \beta,\beta^q,\ldots,\beta^{q^{d-1}} \]

is a basis of $V$; that is, $\beta$ is a normal element over $\mathbb{F}_q$. Put $a=\beta+\beta^q$. Define the graph $TG_{d,h}$ as follows. The vertex set consists of the points of $PG(d-1,q)$; two points $\langle x\rangle$ and $\langle y\rangle$ are adjacent if $\operatorname{Tr}(ax/y)=\operatorname{Tr}(ay/x)=0$.

Note that this is actually a flag. We can identify $\langle x\rangle$ with a point–hyperplane pair $(\langle x\rangle,H_{a/x})$, where

\[ H_b=\{\langle y\rangle:\operatorname{Tr}(by)=0\}. \]

Also note that the choice $a=\beta+\beta^q$ is crucial for clique-freeness, but nowhere else.

It also supplied an argument for $K_4$-freeness that was easy enough, but this obviously did not generalize. A long and unproductive discussion followed, until I asked this:

I care about fixed clique number in fixed dimension and $q=2^h$ large. Please check that.

Then it failed and just repeated what I already knew. So I followed the principle of asking again:

Maybe the trace construction works for larger dimensions as well, but with a slightly larger forbidden clique.

This worked, and it found an argument for the bound in our preprint. After some conversation about whether it helped for off-diagonal Ramsey numbers, we wanted to understand it:

Please try to fix the gap and (in any case) produce a LaTeX note with the explicit construction and its proof.

Its answer was now positive, but at what cost! Here is an excerpt:

The key replacement for the complex critical-point theorem is algebraic. On the De Concini–Procesi wonderful resolution, the logarithmic $1$-form extends to $\Omega_X^1(\log D)$. For the normal-basis choice

\[ a=\beta+\beta^q, \]

every nonempty proper subset-sum of the conjugate residues $a^{q^i}$ is nonzero. The residue along the exceptional divisor corresponding to a flat $F$ is computed directly as

\[ \sum_{H_i\supset F}a^{q^i}, \]

so no multiplicity issue arises in characteristic $2$. Hence the zero scheme misses the boundary and is finite. Its length is then computed by the top Chern class and algebraic logarithmic Gauss–Bonnet, yielding exactly the Crapo beta invariant. The wonderful-model input is standard De Concini–Procesi; the older Orlik–Terao theorem is the characteristic-zero critical-point result that this argument replaces.

I do not understand any sentence of the above. Even worse, I do not even have a vague idea what it means. So we tried again.

Can you try to rewrite the proof such that it is understandable to someone who does not know the deep algebraic geometry involved. Maybe the finite field calculations can be done in a more elementary way.

That was fine. It gave a proof using valuations and Bézout’s theorem: not tools with which we are entirely comfortable, but also nothing unheard of. This provided a good basis for the way we present the argument in the preprint, with the valuations and some additional algebraic geometry removed.

At this point, we were happy. We used ChatGPT further for polishing and some quick calculations. From here, it was clear that we could improve Alon–Pudlák for off-diagonal Ramsey numbers from

\[ t^{\Omega(\sqrt{\log s/\log\log s})} \qquad\text{to}\qquad t^{\Omega(\log s/\log\log s)}. \]

For a day, we thought that this was all. One gets explicit off-diagonal Ramsey bounds, but only beats the construction for $R(6,t)$ for something like $R(20000,t)$. Not interesting. (ChatGPT tells me that the exact threshold is $R(12871,t)$ and that I should change my claim here, but this only shows how you cannot trust it with style.)

Optimizing

Our thinking was focused mostly on the off-diagonal case, but then Sam Mattheus did the calculation for diagonal Ramsey numbers using our original symmetric construction and obtained

\[ R(s,s) \geq s^{(\frac12-o(1))\log s/\log\log s}. \]

This already improved the leading constant $1/4$ in the Frankl–Wilson bound to $1/2$. Could we improve it further?

After some thought, we added the order to our vertices. This made the clique bound slightly worse, but it improved the independence-number bound from $(d^h+1)^2$ to $d^h+1$, as we no longer needed to square the incidence matrix. For reference, here is the definition from the paper:

Definition. The graph $TG^{\prec}_{d,h}$ has as its vertex set the points of $PG(d-1,q)$ with a given total ordering $\prec$, where $\langle x\rangle$ and $\langle y\rangle$, with $\langle x\rangle\prec\langle y\rangle$, are adjacent if $\operatorname{Tr}(ax/y)=0$.

Thus, we got to

\[ R(s,s) \geq s^{(1-o(1))\log s/\log\log s}. \]

This was the first improvement of Frankl–Wilson in a very long time (ignoring the TCS results), even though “all” we did was replace $1/4$ by $1$.

Another nice thing was that our off-diagonal bound now became reasonably strong for small $s$. We obtained

\[ R(33,t) \geq t^{2.1-o(1)}. \]

A simple probabilistic argument already gives $R(33,t)\geq t^{17-o(1)}$, but this seems to be the first substantial step beyond the explicit bound $R(6,t)\geq t^{2-o(1)}$.

Lean 4 Formalization

Lastly, I used my precious ChatGPT Plus allowance to produce a Lean 4 formalization. This required ChatGPT Work/Codex, so it actually consumed usage or tokens. Because our usage was limited, we restricted the formalization to the clique argument, which is the most complex part. It formalized everything except for the required multihomogeneous Bézout theorem. Once enough of the relevant algebraic geometry has been formalized, we will therefore have a complete Lean 4 formalization.

Blog Post

I also let ChatGPT proofread this blog post. Also a first!

I also let it add all the links. It was very eager to link to OpenAI stuff, but, otherwise, did a nice job.