Bounds on Ramsey numbers from finite geometry

In an earlier post I talked about the work of Mubayi and Verstraete on determining the off-diagonal Ramsey numbers via certain optimal pseudorandom graphs, which are not yet known to exist except for the case of triangles. Beyond this conditional result, they also improved the lower bounds on certain cycle-complete Ramsey numbers using generalized polygons. In some cases they even beat the exponent provided by the general $F$ -free process studied by Bohman and Keevash, which

“appears to be the first instance of a graph $F$ containing cycles for which random graphs do not supply the right exponent for $r(F, k)$ .”

(I have changed the $t$ from their paper to $k$ for my own convenience). In this post I will talk about the basics of their construction, hoping that these ideas can be used in future to obtain similar results on Ramsey numbers.

One of the fundamental objects that are studied in finite geometry are partial linear spaces, a.k.a., linear hypergraphs. These are point-line geometries with the property that through any two points there is at most one line, or equivalently, these are hypergraphs in which every two hyperedges share at most one common vertex. A partial linear space has order $(s, t)$ if ever line contains exactly $s + 1$ points and through every point there are exactly $t + 1$ lines (in hypergraph terminology we have an $(s + 1)$ -uniform $(t + 1)$ -regular hypergraph). For every partial linear space we can define the collinearity graph on the points by making to points adjacent if they lie on a common line (in hypergraph terminology this is sometimes referred to as the skeleton of the hypergraph). Note that the lines of the partial linear space correspond to cliques of size $s + 1$ in the collinearity graph, and any two such cliques meet in at most a vertex. From now on denote the number of points in the partial linear space by $n$ and the number of lines by $m$ . In several classes of such spaces these numbers are a function of $s, t$ . For example, in the case of a finite projective plane we have $s = t$ and $n = m = (s - 1)^2 + (s - 1) + 1$ . Note that we always have $n(t + 1) = m(s + 1)$ .

For a graph $F$ , the Ramsey number $r(F, k)$ can be defined as the largest number of vertices for which there exists a graph that has no subgraphs isomorphic to $F$ , and has independence number $< k$ (the existence of such a maximum is a special case of Ramsey’s theorem). We would like to know the growth of this function as $k \rightarrow \infty$ for various kinds of fixed size graphs $F$ . When $F$ is the complete graph, then this is the classical off-diagonal Ramsey number that we saw in the earlier post.

The basic idea behind the construction that I want to discuss in this post is as follows:

start with a partial linear space for which all copies of $F$ in the collinearity graph are contained inside the cliques corresponding to the lines and then destroy all of these copies of $F$ while keeping the independence number under control.

Let’s start with the independence number. If $I$ is a set of pairwise non-collinear points, then by an easy double count of pairs $(p, \ell)$ where $p$ is a point of $I$ and $\ell$ is a line through $p$ , we get $|I|(t + 1) \leq m$ . Therefore, the independence number is always at most $m/(t + 1)$ .

If the graph $F$ contains odd cycles (which is the case we will focus on), then one easy way of getting rid of all the copies of $F$ is to convert each clique of size $s + 1$ , which is where all copies of $F$ lie by our assumption, into a bipartite graph on the same set of vertices by destroying some edges. To be more precise, for each line $\ell$ we take two disjoint subsets $A_\ell, B_\ell$ of the points on $\ell$ , with $A_\ell \cup B_\ell = \ell$ and we define a graph on the set of all points where two points $x$ and $y$ are adjacent if (i) they lie in a common line $\ell$ and (ii) $x \in A_\ell$ , $y \in B_\ell$ or $x \in B_\ell, y \in A_\ell$ . This graph is well defined because we have a partial linear space, that is, no two points can lie in two different lines.

While what we do above ensures that there are no copies of $F$ in our collinearity graph, destroying edges would typically increase the independence number of the graph. What we can show though is that there does exist a choice of bipartition on each line so that the independence number cannot increase by much. We will show this by an easy probabilistic argument.

Here is our probability space. For each line $\ell$ , we choose a bipartition $(A_\ell, B_\ell)$ of the set of $s+1$ points on $\ell$ uniformly at random (from the set of all bipartitions). Then for any line $\ell$ , the probability that a point $x$ of $\ell$ lies in $A_\ell$ (or $B_\ell$ ) is equal to $1/2$ . We do this independently for each line.

Let $I$ be a subset of points, of size $k$ , and for each line $\ell$ let $k_\ell$ be the number of points of $I$ contained in $\ell$ . The probability that $I$ is an independent set in the graph $G$ obtained by removing all edges within $A_\ell$ and $B_\ell$ in the collinearity graph, for each line $\ell$ , is equal to the probability that for every line $\ell$ the set $I \cap \ell$ is either a subset of $A_\ell$ or $B_\ell$ . Since all these are independent events, with an event corresponding to $\ell$ having probability $(1/2)^{k_\ell} + (1/2)^{k_\ell} = 2^{1 - k_\ell}$ , the probability that $I$ is an independent set is equal to $\prod_{\ell} 2^{1 - k_\ell} = 2^{m - \sum k_\ell} = 2^{m - (t + 1)k}$ . The probability that there exists an independent set of size $k$ is then at most $\binom{n}{k} 2^{m - (t + 1)k}$ , by the union bound. Therefore, to show the complementary event that there exists a bipartition of each line for which the graph defined above has no independent sets of size $k$ , it suffices to show that this probability is $< 1$ . By the inequality $\binom{n}{k} \leq n^k = 2^{k \log n}$ , we see that it suffices to show

$2^{k \log n + m - (t + 1)k} < 1.$

This is true if and only if $k > m/(t + 1 - \log n)$ . Thus, for, say $k = \lceil m/(t - \log n) \rceil$ , we get $R(F, k) \geq n$ as there exists an $F$ -free graph on $n$ vertices with independence number $< k$ .

This shows that to get a good lower bound on $R(F, k)$ , what we want from our partial linear space of order $(s, t)$ on $n$ points and $m$ lines is $\log n << t$ and $n >> m$ , beyond the condition we started with of all copies of $F$ being contained in the $(s + 1)$ -cliques.

If you are still with me right now, then here is a concrete example. We know that any triangle in the collinearity graph of a generalized quadrangle (or see this) must be contained in the clique corresponding to a line. We also know that a generalized quadrangle (GQ for short) of order $(s, t)$ has $n = (s + 1)(st + 1)$ points and $m = (t + 1)(st + 1)$ lines. For $n >> m$ , we would thus want $s >> t$ and for $t >> \log n$ we would want $t$ to not be a constant. Considering this, the best choice that we have with us here is $s = t^2$ , and $t \rightarrow \infty$ , as we know that in any GQ one always has $s \leq t^2$ . Such GQ’s are known to exist whenever $t$ is a prime power (see Chapter 5 of my lecture notes). From them we get the lower bound $R(3, k) \geq (1 + o(1))k^{5/3}$ , which is not that great considering we know $R(3, k) = \Theta(k^2/\log k)$ . But there is some good news, as Mubayi and Verstraete have shown. If we consider generalized hexagons of order $(q^3, q)$ , then we get