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.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Ramsey Theory and tagged , , , , , , , , . Bookmark the permalink.

2 Responses to Heisenberg groups, irreducible cubics and minimal Ramsey

  1. Pingback: Improved lower bounds for multicolour diagonal Ramsey numbers | Anurag's Math Blog

  2. Pingback: To cheer you up in difficult times 12: Asaf Ferber and David Conlon found new lower bounds for diagonal Ramsey numbers | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s