## Heisenberg groups, irreducible cubics and minimal Ramsey

As I mentioned in a previous post, we recently improved the upper bound on a Ramsey parameter, in collaboration with John Bamberg and Thomas Lesgourgues. My favourite thing about this work is how it ends up using the properties of certain Heisenberg groups associated to generalized quadrangles, and cubic equations, to say something interesting about a problem in graph Ramsey theory. It makes me really happy to see such harmony in mathematics. In this post I will attempt to describe the main construction in our paper without getting into too many details.

As discussed earlier, we want to determine the smallest possible minimum degree of a graph $G$ that has the property that every $r$-colouring of the edges of $G$ contains a monochromatic clique of size $k$, and no proper subgraph of $G$ has this property. This smallest degree is denoted by $s_r(K_k)$, and the best known upper bounds on it in various ranges are described in the earlier post. All of these bounds use the equality between $s_r(K_{k+1})$ and the following packing parameter:

$P_r(k) =$ the minimum $n$ for which there exist $K_{k+1}$-free pairwise edge disjoint graph $G_1, \dots, G_r$ on a common vertex set $V$ of size $n$ such that for any $r$-colouring of $V$ there exists a $G_i$ that contains a $K_k$ all of whose vertices are coloured in the $i$-th colour.

It is known that $s_2(K_{k+1}) = P_2(k) = k^2$, as proved by Burr, Erdős and Lovász in 1976, but for $r > 2$ our knowledge of this function is quite limited. (As an exercise, try to find such edge disjoint $G_1$ and $G_2$ on a common set of $k^2$ vertices.)

Since we are just looking at upper bounds for now, one can show $P_r(k) \leq n$ by finding a packing of $G_i$‘s where each $G_i$ is $K_{k+1}$ free but every collection of $n/r$ vertices in $G_i$ induces a copy of $K_k$. This works because in any $r$-colouring of $V$ there must exist a colour $i$ which occurs at least $n/r$ times, and then in the graph $G_i$ we have a $K_k$ all of whose vertices are coloured in the $i$-th colour. This has been the main approach so far in showing upper bound on $s_r(K_{k+1})$ for $r \geq 3, k \geq 2$, and we will be doing the same.

Before finding such a collection of edge disjoint $G_i$‘s, the first step is to see if we can find even a single graph $G$ on $n$ vertices which is $K_{k+1}$-free and has the property that any set of $n/r$ vertices in $G$ induce a $K_k$. For $k = 3$, we are looking for triangle-free graphs with independence number $< n/r$. This should remind you of the Ramsey number $R(3, t)$. In fact, such a $G$ on $n$ vertices exists if and only if $n < R(3, \lceil n/r \rceil)$. This connection can in fact be used to prove that $s_r(K_3) = \Theta(r^2 \log r)$ (see Guo and Warnke) by finding not just one triangle-free graph but a packing of triangle-free graphs.

More generally the ideas from the determination of the so-called Erdős-Rogers function were used to prove that for any fixed $k$, and $r$ large enough, $P_r(k) \leq C (\ln r)^{8k^2} r^2$ (see Fox, Grinshpun, Liebenau, Person and Szabó). This is pretty satisfactory as far as the realm of $k$ fixed and $r \rightarrow \infty$ is concerned, but in other ranges this is a terrible bound compared to the more general result of FGLPS that shows $P_r(k) \leq 8k^6 r^3$ for all $k \geq 2, r \geq 3$. Proofs of all these results rely on finite geometric ideas, combined with the probabilistic method, and that’s exactly the path we take as well.

Here is a general idea to construct these graphs. Consider a partial linear space (a.k.a. a linear hypergraph) that is “triangle-free” in the sense that no three lines pairwise meet each other in three distinct points. Then because of this triangle-freeness the only cliques (of size at least 3) in the graph defined on the point-set with two points adjacent if they are collinear, are those contained inside a line. Therefore, we can try to destroy all of the cliques of size $\geq k + 1$, while maintaining some structure so that any set of $n/r$ points contains a $K_k$. This idea, along with a probabilistic argument, can be used to prove the following lemma (which is Lemma 3.1 in our paper) about packings of partial linear spaces:

Lemma 1. Say there exist triangle-free partial linear spaces $(P, \mathcal{L}_1), \dots, (P, \mathcal{L}_r)$, each of order $(s, t)$, such that $(P, \cup_{i = 1}^r \mathcal{L}_i)$ is also a partial linear space. If $s \geq 2rk \ln k$ and $t \geq 2k(1 + \ln r)$, then $P_r(k) \leq |P|$.

The order $(s, t)$ denotes that every line has $s + 1$ points on it and every point has $t + 1$ lines through it. The condition that $(P, \cup_{i = 1}^r \mathcal{L}_i)$ is a partial linear space, is really important, and we overlooked it in our previous version of the paper which led to an error. I would like to thank Simona Boyadzhiyska for pointing this out to me.

The best sources of such triangle-free partial linear spaces, and in fact the only sources I know of, are generalized quadrangles (GQ). One can take any “regular” subhypergraph of a GQ to get these spaces. The main difficulty though is to find a packing of such spaces, as required in Lemma 3.1. In Fox et al. they managed to find such a packing with $s = t = q - 1$, an arbitrary prime power $q$, using what is known as the $T_2(O)$ generalized quadrangle (even though they don’t call it that in the paper). Since $|P| = q^3$ in their packing, we get the upper bound of $P_r(k) \leq 8k^6 r^3$ by picking a prime $q$ such that $rk^2 < q \leq 2rk^2$. We have managed to find such a packing with $s = q^2 - 1$ an $t = q - 1$, for an arbitrary odd prime power $q$, that gives us the following improvement:

Theorem 2. $P_r(k) \leq C k^5 r^{5/2}$.

The construction relies on a group theoretic model of generalized quadrangles, introduced by Bill Kantor in 1980. Consider the Heisenberg group $E$ defined on the set $\mathbb{F}_{q^2} \times \mathbb{F}_{q^2} \times \mathbb{F}_{q}$ by the following group operation $(x, z, y) \circ (x', z', y') = (x + x', z + z', y + y' + z^qx' + zx'^q)$. Note that $(a, b) \rightarrow a^q b + ab^q$ is a bilinear map on $\mathbb{F}_{q^2}$ when identified as the vector space $\mathbb{F}_q^2$.

Our points will be the elements of $E$, and thus we have a point set of size $q^5$. It is known that $E$ contains subgroups $A_i$, for $i \in \mathbb{F}_q$, such that (1) $|A_i| = q^2$; (2) $A_i \cap A_j = \{(0, 0, 0\})$ for any $i \neq j$ and (3) for any three distinct $i, j, k$ we have $(A_i A_j) \cap A_k = \{(0, 0, 0)\}$. These subgroups are $A_i = \{(a, ai, a^{q+1}i) : a \in \mathbb{F}_{q^2}\}$. The partial linear space obtained by taking the set of all cosets of $A_i'$ as lines, is of the order $(q^2 - 1, q - 1)$ and the third condition on these subgroups ensures that it is triangle-free. You should try to prove the triangle-freeness. For the finite geometers reading this post, this partial linear space is a subgeometry of the Hermitian generalized quadrangle $H(3, q^2)$.

We obtain a packing of partial linear spaces isomorphic to this one, on the same point set $E$, by taking a group of automorphisms of $E$ which then acts naturally on the set $\{A_i : i \in \mathbb{F}_q\}$. Each such automorphism $\tau$ defines a new set of subgroups $A^\tau_i$, $i \in \mathbb{F}_q$, which have the same three properties. What we want from our automorphisms though, because of the condition in Lemma 1 regarding $(P, \cup \mathcal{L}_i)$ being a partial linear space, is that every subgroup in $\{A_i : i \in \mathbb{F}_q\}$ must intersect ever subgroup in $\{A_i^\tau : i \in \mathbb{F}_q\}$ trivially. This turns out to be quite tricky, and for this we had to be very careful in our choice of automorphisms. In particular, one can show that none of the inner automorphisms of $E$ would work. In the end end we managed to find $q^2$ outer automorphisms of $E$ that give us the required packing of size $q^2$. Very interestingly, to prove that our packing is good, we had to rely on the following two results on irreducible cubics:

Proposition 1: (Kim-Kim-Yie 2009) There is a bijective correspondence between the set of irreducible polynomials of the form $x^3 - cx^2 + c^q x - 1$ in $\mathbb{F}_{q^2}[x]$ and the set of irreducible polynomials of the form $x^3 + ax^2 + bx + c$ in $\mathbb{F}_q[x]$ where $-b$ is a non-square in $\mathbb{F}_q$.

Proposition 2: For every finite field $\mathbb{F}_q$, and every $\lambda \in \mathbb{F}_q$, there exists an irreducible cubic $x^3 + ax^2 + bx + c$ where $b = \lambda$.

This can be shown via the Hansen-Mullen Irreducibility Conjecture (which was proved by Wan for all but finitely many cases, and those small cases were handled by Ham and Mullen). See this recent paper of Tuxanidy and Wang, and the references therein, for more on this conjecture and its generalizations where we look for irreducible polynomials with more than one of its coefficients prescribed.