The minimum degree of
minimal Ramsey graphs for cliques

A graph $G$ is called $r$-Ramsey for another graph $H$, denoted by $G\rightarrow(H)_{r}$, if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $H$. Observe that if $G\rightarrow(H)_{r}$, then every graph containing $G$ as a subgraph is also $r$-Ramsey for $H$. Some very interesting questions arise when we study graphs $G$ which are minimal with respect to $G\rightarrow(H)_{r}$, that is, $G\rightarrow(H)_{r}$ but there is no proper subgraph $G^{\prime}$ of $G$ such that $G^{\prime}\rightarrow(H)_{r}$. We call such graphs $r$-Ramsey minimal for $H$ and we denote the set of all $r$-Ramsey minimal graphs for $H$ by $\mathcal{M}_{r}(H)$. The classical result of Ramsey [21] implies that for any finite graph $H$ and positive integer $r$, there exists a graph $G$ that is $r$-Ramsey for $H$, that is, $\mathcal{M}_{r}(H)$ is non-empty.

Some of the central problems in graph Ramsey theory are concerned with the case where $H$ is a clique $K_{k}$. For example, the most well studied parameter is the Ramsey number $R_{r}(k)$, that denotes the smallest number of vertices of any graph in $\mathcal{M}_{r}(K_{k})$. The classical work of Erdős [8] and Erdős and Szekeres [9] shows that $2^{k/2}\leqslant R_{2}(k)\leqslant 2^{2k}$. While these bounds have been improved since then, most recently by Sah [23] (also see [24] and [5]), the constants in the exponent have stayed the same. We refer the reader to the survey of Conlon, Fox and Sudakov [6] for more on this and other graph Ramsey problems.

Several other questions on $\mathcal{M}_{r}(H)$ have also been explored; for example, the well studied size-Ramsey number $\hat{R}_{r}(H)$ which is the minimum number of edges of a graph in $\mathcal{M}_{r}(H)$. We refer the reader to [1, 3, 18, 22] for various results on minimal Ramsey problems. In this paper, we will be interested in the smallest minimum degree of an $r$-Ramsey minimal graph, which is defined by

for a finite graph $H$ and positive integer $r$, where $\delta(G)$ denotes the minimum degree of $G$. Trivially, we have $s_{r}(H)\leqslant R_{r}(H)-1$, since the complete graph on $R_{r}(H)$ vertices is $r$-Ramsey for $H$ and has minimum degree $R_{r}(H)-1$. The study of this parameter was initiated by Burr, Erdős and Lovász [2] in 1976. They were able to show the rather surprising exact result, $s_{2}(K_{k})=(k-1)^{2}$, which is far away from the trivial exponential bound of $s_{2}(K_{k})\leqslant R_{r}(k)-1$. The behaviour of this function is still not so well understood for $r>2$ colours. Fox et al. [10] determined this function asymptotically for every fixed $k$ up-to a polylogarithmic factor, and for $k=3$ their result was further improved by Guo and Warnke [12] who managed to obtain matching logarithmic factors.

The constant in the upper bound of Theorem 1.1(ii) is rather large ($C_{k}\sim k^{2}e^{4k^{2}\ln 2}$), and in particular not polynomial in $k$. To remedy this, they proved the following general upper bound which is polynomial in both $k$ and $r$.

For a fixed $r$ and $k\rightarrow\infty$, Hàn, Rödl and Szabó [13] determined this function up-to polylogarithmic factors by proving the following.

We prove the following general upper bound that improves Theorem 1.3, and thus provides the best known upper bound on $s_{r}(K_{k})$ outside the special ranges covered by Theorem 1.1 and 1.4.

Our proof uses the equivalence between $s_{r}(K_{k})$ and another extremal function, called the $r$-colour $k$-clique packing number [10], defined as follows. Let $P_{r}(k)$ denote the minimum $n$ for which there exist $K_{k+1}$-free pairwise edge disjoint graphs $G_{1},\dots,G_{r}$ on a common vertex set $V$ of size $n$ such that for any $r$-colouring of $V$, there exists an $i$ such that $G_{i}$ contains a copy of $K_{k}$ all of whose vertices are coloured in the $i$^th colour.

Our graphs $G_{i}$ in the packing would come from certain point-line geometries known as generalised quadrangles that we define in the next section. In Section 3, we show that any packing of ‘triangle-free’ point-line geometries implies an upper bound on $P_{r}(k)$, assuming certain conditions on the parameters of the geometry. In Section, 4 we give a packing of certain subgeometries of the so-called Hermitian generalised quadrangles using a group theoretic model given by Kantor in the 1980’s [15], and deduce that this packing implies our main result.

A (finite) generalised quadrangle $\mathcal{Q}$ of order $(s,t)$ is an incidence structure of points $\mathcal{P}$, lines $\mathcal{L}$, together with a symmetric point-line incidence relation satisfying the following axioms:

1. (i)

   Each point lies on $t+1$ lines ($t\geqslant 1$) and two distinct points are incident with at most one line.

2. (ii)

   Each line lies on $s+1$ points ($s\geqslant 1$) and two distinct lines are incident with at most one point.

3. (iii)

   If $P$ is a point and $\ell$ is a line not incident with $P$, then there is a unique point on $\ell$ collinear with $P$.

Notice that the third axiom above ensures that there are no triangles (i.e., three distinct lines pairwise meeting in three distinct points) in $\mathcal{Q}$. The standard reference on finite generalised quadrangles is the book by Payne and Thas [20]. The collinearity graph of a generalised quadrangle is the graph on the set of points with two points adjacent when they are both incident with a common line. A collineation $\theta$ of $\mathcal{Q}$, that is, an automorphism of its collinearity graph, is an elation about the point $P$ if it is either the identity collineation, or it fixes each line incident with $P$ and fixes no point not collinear with $P$. If there is a group $E$ of elations of $\mathcal{Q}$ about the point $P$ such that $E$ acts regularly on the points not collinear with $P$, then we say that $\mathcal{Q}$ is an elation generalised quadrangle with elation group $E$ and base point $P$. Necessarily, $E$ has order $s^{2}t$, as there are $s^{2}t$ points not collinear to a given point in any generalised quadrangle.

Now suppose we have a finite group $E$ of order $s^{2}t$ where $s,t>1$. A Kantor family of $E$ is a set $\mathcal{A}:=\{A_{i}\colon i=0,\ldots,t\}$ of subgroups of order $s$, and a set $\mathcal{A}^{*}:=\{A_{i}^{*}\colon i=0,\ldots,t\}$ of subgroups of order $st$, such that the following are satisfied:

1. (K0)

   $A_{i}\leqslant A_{i}^{*}$ for all $i\in\{0,\ldots,t\}$;

2. (K1)

   $A_{i}\cap A_{j}^{*}=\{1\}$ whenever $i\neq j$;

3. (K2)

   $A_{i}A_{j}\cap A_{k}=\{1\}$ whenever $i,j,k$ are distinct.

Due to a theorem of Kantor (c.f., [15, Theorem A.3.1]), a Kantor family as described above, gives rise to an elation generalised quadrangle of order $(s,t)$, which we briefly describe in Table 1.

We will simply be needing to use the Kantor family for a well-known family of generalised quadrangles, where the Heisenberg groups appear as the group $E$ in the description above. We remark that the main property we will need is (K2), since it ensures that lines of the form $A_{i}g$, never form a triangle.For self-containment, we give a proof here. Suppose $f,g,h$ are three elements of $E$ forming the vertices of a triangle. Then there are three elements $A,B,C\in\mathcal{A}$ such that $Af=Ag$, $Bg=Bh$, $Ch=Cf$. Therefore, $fg^{-1}\in A$, $gh^{-1}\in B$, $fh^{-1}\in C$, from which it follows that $fh^{-1}=(fg^{-1})(gh^{-1})\in AB\cap C$. Since $f\neq h$, we have $AB\cap C\neq\{1\}$. So the condition $AB\cap C=\{1\}$ given by (K2) ensures that there are no triangles.

In this paper, we will also need two commonly used maps on finite fields: the trace and norm maps. For a finite field, they are the analogues of ‘real part’ and ‘square-modulus’ for the complex numbers. We will not be needing the general theory of traces and norms, just two functions in particular. The relative trace map from $\mathbb{F}_{q^{2}}$ to $\mathbb{F}_{q}$ is defined by $\operatorname{\mathsf{Tr}}(x)=x+x^{q}$. If $\phi$ is a field-automorphism of $\mathbb{F}_{q^{2}}$, then $\operatorname{\mathsf{Tr}}\left(\phi(x)\right)=\operatorname{\mathsf{Tr}}(x)$ for all $x\in\mathbb{F}_{q^{2}}$. Also, $\operatorname{\mathsf{Tr}}$ is additive; that is, $\operatorname{\mathsf{Tr}}(x+y)=\operatorname{\mathsf{Tr}}(x)+\operatorname{\mathsf{Tr}}(y)$ for $\mathbb{F}_{q^{2}}$. The relative norm map $\mathbb{F}_{q^{2}}$ to $\mathbb{F}_{q}$ is defined by $\mathsf{N}(x)=x^{q+1}$. It is also invariant under field-automorphisms, and is surjective. We will make use of the following property: if $q$ is odd, then every element of $\mathbb{F}_{q}$ is a square in $\mathbb{F}_{q^{2}}$. To see this, let $t\in\mathbb{F}_{q}$. Since $\mathsf{N}$ is surjective, there exists $x\in\mathbb{F}_{q^{2}}$ such that $t=x^{q+1}$. Since $q$ is odd, the element $y=x^{(q+1)/2}$ is well defined, and then $t=y^{2}$.

A partial linear space is a point-line incidence structure with the property that any two distinct points are incident to at most one common line. A triangle-free partial linear space of order $(s,t)$ is an incidence structure satisfying Axioms (i) and (ii) of a generalised quadrangle, and (iii)^′ there are no three distinct lines pairwise meeting each other in three distinct points. Clearly, any subgeometry of a generalised quadrangle where the number of points on a line and the number of lines through a point are constants is a triangle-free partial linear space. We now prove the main lemma that will imply Theorem 1.5 once we have the construction outlined in Section 4. Our proof follows the same idea as in Dudek and Rödl [7], and Fox et al. [10].

Let $q$ be a prime power, and denote the finite field of order $q^{2}$ by $\mathbb{F}_{q^{2}}$. We will use the model of the Hermitian generalised quadrangle $H(3,q^{2})$ that appears in [14, Section 3] (see Example 3). For a definition of $H(3,q^{2})$ see [20, Chapter 3].

Let $E$ be the group defined on $\mathbb{F}_{q^{2}}\times\mathbb{F}_{q}\times\mathbb{F}_{q^{2}}$ by the following operation:

where $\operatorname{\mathsf{Tr}}(x)=x+x^{q}$ is the relative trace map from $\mathbb{F}_{q^{2}}$ to $\mathbb{F}_{q}$. It turns out that $E$ is the Heisenberg group of order $q^{5}$ with centre of order $q$.

We can construct a generalised quadrangle by constructing a Kantor family of $E$. Define

Then $\mathcal{A}:=\{A_{\infty}\}\cup\{A_{t}\colon t\in\mathbb{F}_{q}\}$ and $\mathcal{A}^{*}:=\{A^{*}_{\infty}\}\cup\{A^{*}_{b}\colon b\in\mathbb{F}_{q}\}$ form a Kantor family of $E$ giving rise to a generalised quadrangle isomorphic to $H(3,q^{2})$.¹¹1In [14] the dual of this generalised quadrangle is defined, denoted by $O^{-}(6,q)$, but it is well known that $H(3,q^{2})$ is isomorphic to the dual of the elliptic generalised quadrangle $O^{-}(6,q)$ (see [20, Chapter 3], where $O^{-}(6,q)$ is denoted by $Q(5,q)$).

From now on we will assume that $q$ is odd. Let $\kappa$ be an element of $\mathbb{F}_{q^{2}}$. For each $\lambda\in\mathbb{F}_{q^{2}}$, define $\tau_{\lambda}:E\rightarrow E$ as follows. Let

By Axiom (K1), we have $|A_{0}A_{\infty}^{*}|=|A_{0}||A_{\infty}^{*}|/|A_{0}\cap A_{\infty}^{*}|=s(st)/1=|E|$. So $E=A_{0}A_{\infty}^{*}$. Therefore, we can write every element $g\in E$ as $g=g_{0}g_{\infty}^{*}$, with $g_{0}\in A_{0}$ and $g_{\infty}^{*}\in A_{\infty}^{*}$. Define $\tau_{\lambda}(g)\coloneqq\tau_{\lambda}(g_{0})\circ\tau_{\lambda}(g_{\infty}^{*})$.