On the chromatic number of a random hypergraph

Introduction

We study the problem of $k$-colouring a random $r$-uniform hypergraph with $n$ vertices and $cn$ edges, where $k,\,r$ and $c$ are considered to be constant as $n\to\infty$. We generalise a theorem of Achlioptas and Naor for $k$-colouring a random graph ($2$-uniform hypergraph) on $n$ vertices.

Their theorem specifies the two possible values for the chromatic number of the random graph as $n\to\infty$. We give a complete generalisation of the result of . We broadly follow the approach of Achlioptas and Naor , although they rely on simplifications which are available only in the case $r=2$. We show that these simplifications can be replaced by more general techniques, valid for all $k,\,r\geq 2$ except $k=r=2$.

There is an extensive literature on this problem in the case $r=2$, colouring random graphs. In the setting we consider here, this culminates with the results of Achlioptas and Naor , though these do not give a complete answer to the problem. Our results here include those of .

There is also a literature for the case $k=2$, random hypergraph $2$-colouring. Achlioptas, Kim, Krivelevich and Tetali gave a constructive approach, but their results were substantially improved by Achlioptas and Moore , using non-constructive methods. The results of are asymptotic in $r$. Our results here include those of , but we also give a non-asymptotic treatment. Recently, Coja-Oghlan and Zdeborová have given a small qualitative improvement of the result of , which goes beyond what can be proved here. See these papers, and their references, for further information.

Finally, we note that Krivelevich and Sudakov studied a wide range of random hypergraph colouring problems, and some of their results were recently improved by Kupavskii and Shabanov . But, in the setting of this paper, these results are much less precise than those we establish here.

After preparing this paper, we learnt of related work by Coja-Oghlan and his coauthors in the case $r=2$. Coja-Oghlan and Vilenchik improved the upper bound on the $k$-colourability threshold, restricting the sharp threshold for $k$-colourability to an interval of constant width, compared with logarithmic width in . (See also Remark 3.7 below.) A small improvement in the lower bound was obtained by Coja-Oghlan . Additionally, Coja-Oghlan, Efthymiou and Hetterich adapted the methods from to study $k$-colourability of random regular graphs.

Let $[n]=\{1,2,\ldots,n\}$. Unless otherwise stated, the asymptotic results in this paper are as $n\to\infty$. Consider the set $\Omega(n,r,m)$ of $r$-uniform hypergraphs on the vertex set $[n]$ with $m$ edges. Such a hypergraph is defined by its edge set $\mathcal{E}$, which consists of $m$ distinct $r$-subsets of $n$. Let $N=\binom{n}{r}$ denote the total number of $r$-subsets.

Now let $\mathcal{G}(n,r,m)$ denote the uniform model of a random $r$-regular hypergraph with $m$ edges. So $\mathcal{G}(n,r,m)$ consists of the set $\Omega(n,r,m)$ equipped with the uniform probability distribution. We write $G\in\mathcal{G}(n,r,m)$ for a random hypergraph chosen uniformly from $\Omega(n,r,m)$. The edge set $\mathcal{E}$ of this random hypergraph may be viewed as a sample of size $m$ chosen uniformly, without replacement, from the set of $N$ possible edges.

Although our main focus is the uniform model $\mathcal{G}$, it is simpler for many calculations to work with an alternative model. Let $\Omega^{*}(n,r,m)$ denote the set of all $r$-uniform multi-hypergraphs on $[n]$, defined as follows: each element of $\Omega^{*}(n,r,m)$ consists of vertex set $[n]$ and a multiset of edges, where each edge is now a multiset of $r$ vertices (not necessarily distinct). We can generate a random element of $G$ of $\Omega^{*}(n,r,m)$ using the following simple procedure: choose $\boldsymbol{v}=(v_{1},v_{2},\ldots,v_{rm})\in[n]^{rm}$ uniformly at random and let the edge multiset of $G$ be $\{e_{1},\ldots,e_{m}\}$, where $e_{i}=\{v_{r(i-1)+1},\ldots,v_{ri}\}$ for $i\in[m]$. Let $\mathcal{G}^{*}(n,r,m)$ denote the probability space on $\Omega^{*}(n,r,m)$ which arises from this procedure, and write $G\in\mathcal{G}^{*}(n,r,m)$ for a hypergraph $G$ generated in this fashion.

Observe that an element $G\in\Omega^{*}(n,r,m)$ may not satisfy the definition of $r$-uniform hypergraph given above, for two reasons. First, an edge of $G$ may contain repeated vertices, which $\Omega(n,r,m)$ does not permit. We call such an edge defective. Second, an edge of $G\in\Omega^{*}(n,r,m)$ may be identical to some other edge, which again $\Omega(n,r,m)$ does not permit. We call such an edge a duplicate.

Say an edge is bad if it is a defective or duplicate edge. Note that $\mathcal{G}^{*}(n,r,m)$ is not the uniform probability space over $\Omega^{*}(n,r,m)$, but that all $G$ without bad edges are equiprobable. Thus $\mathcal{G}^{*}(n,r,m)$, conditional on there being no bad edges, is identical to $\mathcal{G}(n,r,m)$.

If $E_{n}$ is a sequence of events, we say that $E_{n}$ occurs “asymptotically almost surely” (a.a.s.) if $\Pr(E_{n})\to 1$ as $n\to\infty$. In this paper, the event $E_{n}$ usually concerns $G\in\mathcal{G}^{*}(n,r,m)$, where $m(n)=\lfloor cn\rfloor$, for some constant $c$. The difference between $cn$ and $\lfloor cn\rfloor$ is usually negligible, and we follow in disregarding it unless the distinction is important. Thus we will write the model simply as $G\in\mathcal{G}^{*}(n,r,cn)$, and similarly for the other models we consider.

Let $c$ be a positive constant. For $G\in\mathcal{G}^{*}(n,r,cn)$,

Furthermore, for $G\in\mathcal{G}^{*}(n,r,cn)$, a.a.s. $G$ has at most $2\ln n$ bad edges.

Throughout this proof, all probabilities are calculated in $\mathcal{G}^{*}(n,r,cn)$. For any edge $e\in\mathcal{E}$,

Since this is true independently for each $e\in\mathcal{E}$, we have

as $m\sim cn$. Next note that, conditional on there being no defective edges, $\mathcal{E}$ is a uniform sample of size $m$ chosen, with replacement, from the $N$ possible $r$-subsets of $[n]$. Thus

Combining (1) and (2) proves the first statement.

Now let $m_{\textrm{def}}$ ($m_{\textrm{dup}}$, $m_{\textrm{bad}}$, respectively) denote the number of defective edges (duplicate edges, bad edges, respectively) in $G\in\mathcal{G}^{*}(n,r,m)$ (counting multiplicities). For the second statement, note that $m_{\textrm{def}}$ has distribution Bin($m,p_{\textrm{def}}$), and so $\mathbf{E}[m_{\textrm{def}}]\sim cr(r-1)/2$ as $n\to\infty$. Hence Chernoff’s bound [13, Corollary 2.4] gives, for large enough $n$,

Therefore a.a.s. $G\in\mathcal{G}^{*}(n,r,cn)$ has at most $\ln n$ defective edges. Next, note that each edge in $\mathcal{E}$ has at most $(m-1)/n^{r}$ duplicates in expectation, and so

for large $n$. (Indeed, if $r>2$ then $\mathbf{E}[m_{\textrm{dup}}]=o(1)$, but we do not exploit this.) Thus, using Markov’s inequality [13, (1.3)],

Combining this with (3) proves the second statement, since $m_{\textrm{bad}}\leq m_{\textrm{def}}+m_{\textrm{dup}}$. ∎

As already stated, conditional on there being no bad edges, $\mathcal{G}^{*}(n,r,cn)$ is identical to $\mathcal{G}(n,r,cn)$. By the first statement of Lemma 1.1, $G$ has no bad edges with probability $\Omega(1)$ as $n\to\infty$. This implies that any event occurring a.a.s. in $\mathcal{G}^{*}(n,r,cn)$ occurs a.a.s. in $\mathcal{G}(n,r,cn)$. In Lemma 1.4 we use the second statement of Lemma 1.1 to show that $\mathcal{G}(n,r,cn)$ and $\mathcal{G}^{*}(n,r,cn)$ are essentially equivalent, for our purposes.

We also make use of the following simple property of $\mathcal{G}^{*}(n,r,m)$. A vertex $i\in[n]$ of $G\in\Omega^{*}(n,r,m)$ is isolated if it appears in no edge. Note that a vertex is isolated if and only if it is absent from the vector $\boldsymbol{v}\in[n]^{rm}$ defined above. The following simply restates this property.

For $S\subseteq[n]$, let $\mathcal{I}_{S}$ be the event that all vertices in $S$ are isolated in $G\in\mathcal{G}^{*}(n,r,m)$. Let $G^{\prime}$ be $G$ conditional on $\mathcal{I}_{S}$ and let $G^{\prime\prime}$ be obtained from $G^{\prime}$ by deleting all vertices in $S$ and relabelling the remaining vertices by $[n-|S|]$, respecting the original ordering. Then $G^{\prime\prime}\in\mathcal{G}^{*}(n-|S|,r,m)$.

We show, in the proof of Lemma 4.1, that $G\in\mathcal{G}^{*}(n,r,cn)$ has $\Omega(n)$ isolated vertices a.a.s. and hence $G$ has many disconnected components.

A further model of random hypergraphs is often used, which we will denote by $\widehat{\mathcal{G}}(n,r,p)$. In this, the edge set $\mathcal{E}$ of $G$ is chosen by Bernoulli sampling. Each of the $N$ possible $r$-subsets of $[n]$ is included in $\mathcal{E}$ independently with probability $p$. Essentially, this is $\mathcal{G}(n,r,m)$ where $m$ is a binomial random variable Bin($N,p$). We show in Section 1.2 below that $\widehat{\mathcal{G}}(n,r,cn/N)$ and $\mathcal{G}(n,r,cn)$ are equivalent for our problem.

2 Hypergraph colouring

Note that what we study here is sometimes called the weak chromatic number of the hypergraph. The strong chromatic number is defined similarly in terms of strong colourings, which are $k$-partitions $\sigma$ such that $|\sigma(e)|=|e|$ for each edge $e\in\mathcal{E}$. Even more general notions of colouring may be defined. See, for example, . We will not consider this further here, though it seems probable that the methods we use would be applicable.

The principal objective of the paper will be to prove the following result.

Define $u_{r,k}=k^{r-1}\ln k$ for integers $r\geq 2$ and $k\geq 1$. Suppose that $r\geq 2$, $k\geq 1$, and let $c$ be a positive constant. Then for $G\in\mathcal{G}(n,r,cn)$,

If $c\geq u_{r,k}$ then a.a.s. $\chi(G)>k$.

If $k\geq 2$ and $\max\{r,k\}\geq 3$ then there exists a constant $c_{r,k}\in(u_{r,k-1},\,u_{r,k})$ such that if $c<c_{r,k}$ is a positive constant then a.a.s. $\chi(G)\leq k$.

Now the following theorem, which is a complete generalisation of the result of to uniform hypergraphs, follows easily. Note that the lower bound $u_{r,k-1}\leq c$ from Theorem 1.2 is trivial when $k=2$, since $u_{r,1}=0$ for all $r\geq 2$.

For all $r,\,k\geq 2$, if $c\in[u_{r,k-1},\,u_{r,k})$ is a positive constant then a.a.s. the chromatic number of $G\in\mathcal{G}(n,r,cn)$ is either $k$ or $k+1$. Indeed, if $\max\{r,k\}\geq 3$ and $c\in[u_{r,k-1},\,c_{r,k})$, where $c_{r,k}$ is a constant satisfying the conditions of Theorem 1.1(b), then a.a.s. $\chi(G)=k$ for $G\in\mathcal{G}(n,r,cn)$.

Let $G\in\mathcal{G}(n,r,cn)$ and suppose that $u_{r,k-1}\leq c<u_{r,k}$. By Theorem 1.1(a), we know that $\chi(G)\geq k$ a.a.s., and by Theorem 1.1(b) we know that $\chi(G)\leq k+1$ a.a.s., since $c<u_{r,k}<c_{r,k+1}$. This proves the first statement. Furthermore, if $\max\{r,k\}\geq 3$ and $c<c_{r,k}$ then $\chi(G)\leq k$ a.a.s., by Theorem 1.1(b), proving the final statement. ∎

For all but a few small values of $(r,k)$ we will see that $c_{r,k}$ is much closer to $u_{r,k}$ than to $u_{r,k-1}$, so that for most values of $c$, the chromatic number of $G\in\mathcal{G}(n,r,cn)$ is a.a.s. uniquely determined. For more detail see Remark 3.7.

Although based on a rather simple idea, the second moment method is often very laborious to apply, and our analysis will be no exception.

A $k$-partition is called balanced if $\lfloor n/k\rfloor\leq n_{i}\leq\lceil n/k\rceil$ for $i=1,\ldots,k$. A balanced $k$-colouring of a $H$ is a balanced $k$-partition which is also a $k$-colouring of $H$. For convenience, we will assume that $k$ divides $n$, so in a balanced colouring, each colour class has precisely $n/k$ vertices. Since we suppose $k$ to be constant, the effects of this assumption are asymptotically negligible as $n\to\infty$. (This is proved in Lemma 1.4 below.) Following , our analysis will be carried out mainly in terms of balanced colourings. Indeed, we will apply (5) to the random variable $Z$ which is the number of balanced $k$-colourings (defined formally in Section 2.1).

Clearly, if $Z>0$ then a $k$-colouring exists. However, the analysis in Section 2 will only allow us to conclude that $c<c_{r,k}$ implies that $\liminf_{n\to\infty}\Pr(Z>0)>0$. Thus, we first prove a weaker statement about $G\in\mathcal{G}(n,r,cn)$:

If $r,\,k\geq 2$ then there exists a constant $c_{r,k}\in(u_{r,k-1},u_{r,k})$ such that if $c<c_{r,k}$ is a positive constant then

Then part (b) of Theorem 1.1 will follow from the fact that there is a sharp threshold for $k$-colourability of a random hypergraph (see Lemma 1.3, below). Achlioptas and Naor used a result of Achlioptas and Friedgut which established that random graph $k$-colourability has a sharp threshold. We will use instead the following, more general, result.

Hatami and Molloy studied the problem of the existence of a homomorphism from a random hypergraph to a fixed hypergraph $H$. They used the Bernoulli random hypergraph model $\widehat{\mathcal{G}}(n,r,p)$, defined at the end of Section 1.1.

Given a fixed hypergraph $H=([\nu],\mathcal{E}_{H})\in\Omega^{*}(\nu,r,\mu)$, Hatami and Molloy considered the threshold $p$ for the existence of a homomorphism from $G=([n],\mathcal{E}_{G})\in\widehat{\mathcal{G}}(n,r,p)$ to $H$. A homomorphism from $G$ to $H$ is a function $\sigma:[n]\to[\nu]$ such that $\sigma(e)\in\mathcal{E}_{H}$ for all $e\in\mathcal{E}_{G}$. If $H^{\prime}$ is formed from $H$ by deleting duplicate edges then the homomorphisms from $G$ to $H^{\prime}$ are identical to those from $G$ to $H$, so we may assume that $H$ has no duplicate edges. A loop in $H$ is an edge $e\in\mathcal{E}_{H}$ for which the underlying set is a singleton. A triangle in $H$ is a sequence $(v_{1},e_{1},v_{2},e_{2},v_{3},e_{3})$ of distinct vertices $v_{i}\in[\nu]$ and edges $e_{i}\in\mathcal{E}_{H}$ ($i\in$), such that $v_{1},\,v_{2}\in e_{1}$, $v_{2},\,v_{3}\in e_{2}$ and $v_{1},\,v_{3}\in e_{3}$. The following was proved in (with minor changes of notation):

Let $H$ be a connected undirected loopless $r$-uniform hypergraph with at least one edge. Then the $H$-homomorphism problem has a sharp threshold iff (i) $r\geq 3$ or (ii) $r=2$ and $H$ contains a triangle.

Here a sharp threshold means that there exists a function $p(n)$ taking values in $$for all sufficiently large$n$such that, for all$0<\varepsilon<1$,$G\in\widehat{\mathcal{G}}(n,r,(1-\varepsilon)p)$has a homomorphism to$H$a.a.s., and$G\in\widehat{\mathcal{G}}(n,r,(1+\varepsilon)p)$has no homomorphism to$H$ a.a.s.

The property of having an $H$-homomorphism is a monotone decreasing property of $G$, that is, an $H$-homomorphism cannot be destroyed by deleting arbitrary edges of $G$. This fact will be used later.

A random hypergraph in $G\in\widehat{\mathcal{G}}(n,r,cn/\binom{n}{r})$ a.a.s. has $cn\left(1+\Theta\left(n^{-1/4}\right)\right)$ edges (see (7), and $G\in\widehat{\mathcal{G}}(n,r,cn/\binom{n}{r})$ is uniformly random conditioned on the number of edges it contains. Hence if an existence problem has a sharp threshold (with respect to $p$) for $\widehat{\mathcal{G}}(n,r,p)$ then it has a sharp threshold (with respect to $c$) for $\mathcal{G}(n,r,cn)$. In this setting, existence of a sharp threshold means that there exists a function $c(n)=\Theta(1)$ such that, for all $0<\varepsilon<1$, $G\in\mathcal{G}(n,r,(1-\varepsilon)cn)$ has a homomorphism to $H$ a.a.s., and $G\in\mathcal{G}(n,r,(1+\varepsilon)cn)$ has no homomorphism to $H$ a.a.s.

Suppose that $r,k\geq 2$ with $\max\{k,r\}\geq 3$, and let $c$ be a positive constant. Then the problem of $k$-colouring $G\in\mathcal{G}(n,r,cn)$ has a sharp threshold.

Take $K=([k],\mathcal{E}_{K})\in\Omega^{*}(k,r,\mu)$ to be such that $\mathcal{E}_{K}$ contains all $r$-multisets with elements in $[k]$, except for the $k$ possible loops. Then $\mu=\binom{k+r-1}{r}-k$. It is easy to see that the homomorphisms from a graph $G$ to $K$ are precisely the $k$-colourings of $G$. If $r=2$ and $k\geq 3$ then $K$ contains a triangle. (We may take $v_{i}=i\pmod{3}+1$ and $e_{i}$ to be an edge with underlying set $\setminus\{i\}$, for $i\in$.) Thus it follows from Theorem 1.3 that the problem of $k$-colouring $G\in\widehat{\mathcal{G}}(n,r,p)$ has a sharp threshold unless $k=r=2$. Hence, by Observation 1.3, the problem of $k$-colouring $G\in\mathcal{G}(n,r,cn)$ has a sharp threshold unless $k=r=2$. ∎

In the excluded case, which is the question of whether a random graph is $2$-colourable, it is known that there is no sharp threshold (see [9, Corollary 7]).

We now use Lemma 1.2 to prove the following.

Suppose that $k\geq 2$ and $\max\{r,k\}\geq 3$. Then (b′) implies (b).

From part (b′) of Theorem 1.1, we have a constant $c_{r,k}\in(u_{r,k-1},u_{r,k})$ such that for $G\in\mathcal{G}(n,r,cn)$,

whenever $c<c_{r,k}$ is a positive constant. Then Lemma 1.2 implies that the threshold function $c(n)$ satisfies $\liminf_{n\to\infty}c(n)\geq c_{r,k}$. Thus for any $c<c_{r,k}$ we have a.a.s. $\chi(G)\leq k$, proving part (b) of Theorem 1.1. ∎

In fact, we will prove an even weaker statement than (b′).

If $r,\,k\geq 2$ then there exists a constant $c_{r,k}\in(u_{r,k-1},u_{r,k})$ such that for any positive constant $c<c_{r,k}$, the random hypergraph $G\in\mathcal{G}^{*}(kt,r,ckt)$ satisfies $\liminf_{t\to\infty}\Pr(\chi(G)\leq k)>0$.

Observe that, in addition to restricting $n$ to multiples of $k$, the random hypergraph model for (b′′) is different from that used in (b′). We now show why (b′′) is sufficient.

Let $\textrm{P}^{*}(n,m)=\Pr(\chi(G)\leq k)$, where $G\in\mathcal{G}^{*}(n,r,m)$, and let $\delta(c)=\liminf_{t\to\infty}\textrm{P}^{*}(kt,ckt)$. Then (b′′) is the statement that there exists a constant $c_{r,k}\in(u_{r,k-1},u_{r,k})$ such that $\delta(c)>0$ for all positive $c<c_{r,k}$. Assume that (b′′) holds.

Given $n$ and $c<c_{r,k}$, let $t=\lfloor n/k\rfloor$ and let $c^{\prime}$ be such that $c<c^{\prime}<c_{r,k}$. We show in Lemma 4.1 that $G\in\mathcal{G}^{*}(n,r,cn)$ has at least $k-1$ isolated vertices a.a.s.. Let $I$ be a set of $n-kt\leq k-1$ isolated vertices in $G$, chosen randomly from the set of isolated vertices in $G$. Form $G^{\prime}$ from $G$ by deleting the set $I$ of isolated vertices and relabelling the vertices in $G^{\prime}$ with $[kt]$, respecting the relative ordering. By symmetry, each set of size $n-kt$ is equally likely to be the chosen set $I$. Hence $G^{\prime}\in\mathcal{G}^{*}(kt,r,cn)$, by Observation 1.1, since $G$ can be uniquely reconstructed from $G^{\prime}$ and $I$. So $\textrm{P}^{*}(n,cn)=\textrm{P}^{*}(kt,cn)-o(1)$. Next, if $n\geq c^{\prime}k/(c^{\prime}-c)$ then $c^{\prime}kt>c^{\prime}(n-k)\geq cn$. Therefore, since $k$-colourability is a monotone decreasing property (Observation 1.2), it follows that $\textrm{P}^{*}(kt,cn)\geq\textrm{P}^{*}(kt,c^{\prime}kt)$.

Finally, since $c^{\prime}<c_{r,k}$, (b′′) implies that $\textrm{P}^{*}(kt,c^{\prime}kt)>\delta(c^{\prime})-o(1)$, with $\delta(c^{\prime})>0$. Hence we have

By Lemma 1.1, a.a.s. $G^{\prime}\in\mathcal{G}^{*}(n,r,c^{\prime}n)$ has at most $2\ln n$ bad edges. Denote the set of bad edges in $G^{\prime}$ by $B(G^{\prime})$. Let $G^{\prime}$ be a uniformly chosen element of $\Omega^{*}(n,r,c^{\prime}n)$ with at most $2\ln n$ bad edges, and form the random hypergraph $\varphi(G^{\prime})$ as follows: delete $B(G^{\prime})$ and a set of $(c^{\prime}-c)n-|B(G^{\prime})|$ randomly chosen good edges from $G^{\prime}$. (If $n$ is sufficiently large then $2\ln n\leq(c^{\prime}-c)n$, making this procedure possible.) The resulting hypergraph $\varphi(G^{\prime})$ belongs to $\Omega(n,r,cn)$, and, by symmetry, it is a uniformly random element of $\Omega(n,r,cn)$. That is, that $\varphi(G^{\prime})$ has the same distribution as $G\in\mathcal{G}(n,r,cn)$ when $G^{\prime}$ is chosen uniformly from those elements of $\Omega^{*}(n,r,c^{\prime}n)$ with at most $2\ln n$ bad edges.

Now choose a constant $c^{\prime\prime}$ with $c^{\prime}<c^{\prime\prime}<c_{r,k}$. Then by (6) applied to $c^{\prime}$, we have $\textrm{P}^{*}(n,c^{\prime}n)\geq\delta(c^{\prime\prime})>0$. It follows that for $G^{\prime}\in\mathcal{G}^{*}(n,r,c^{\prime}n)$,

By monotonicity (Observation 1.2), since $\varphi(G^{\prime})$ has fewer edges than $G^{\prime}$, we conclude that

Hence using the second statement of Lemma 1.1, $\Pr(\chi(G)\leq k)\geq\delta(c^{\prime\prime})-o(1)$ for $G\in\mathcal{G}(n,r,cn)$. This shows that (b′) holds, completing the proof. ∎

The remainder of the paper will be devoted to proving Theorem 1.1, with part (b) weakened to (b′′). First we obtain expressions for $\mathbf{E}[Z]$ and $\mathbf{E}[Z^{2}]$ in Sections 2.1 and 2.2, respectively. The expression for $\mathbf{E}[Z^{2}]$ is analysed using Laplace’s method, under the assumption that constants $c_{r,k}\in(u_{r,k-1},u_{r,k})$ exist which satisfy some other useful conditions (see Lemma 2.2). This is established in Section 3, completing the proof. Some remarks about asymptotics are made in Section 3.9.

The analysis of Section 3 will require many technical lemmas, some merely verifying inequalities. These inequalities are obvious for large $r$ and $k$ but, since $r$ and $k$ are constants, we need to establish precise conditions under which they are true. We relegate the proofs of most technical lemmas to the appendix, since they complicate what are fairly natural and straightforward arguments. Therefore, whenever we use a lemma without proof, the proof can be found in the appendix.

To complete this section, we prove the result corresponding to Theorem 1.2 for the Bernoulli random hypergraph model $\widehat{\mathcal{G}}(n,r,p)$. Recall that $u_{r,k}=k^{r-1}\ln k$ and $N=\binom{n}{r}$.

Let $r\geq 2$. Given a positive constant $c$, let $k(c,r)$ be the smallest integer $k$ such that $c\leq u_{r,k}$. (Note, $u_{r,k}>0$ by definition.) If $G\in\widehat{\mathcal{G}}(n,r,cn/N)$ then $\chi(G)\in\left\{k(c,r),\,k(c,r)+1\right\}$ a.a.s.

Let $G\in\widehat{\mathcal{G}}(n,r,cn/N)$, and let $m$ be its (random) number of edges. Then Chernoff’s bound [13, Corollary 2.3] gives

Therefore $cn(1-n^{-\nicefrac{{1}}{{4}}})\leq m\leq cn(1+n^{-\nicefrac{{1}}{{4}}})$ a.a.s., and hence $c^{\prime}n<m<c^{\prime\prime}n$ a.a.s. for any positive constants $c^{\prime}$, $c^{\prime\prime}$ such that $c^{\prime}<c<c^{\prime\prime}$.

Let $k=k(r,c)$, so $u_{r,k-1}<c\leq u_{r,k}$. Choose $c^{\prime}\in(u_{r,k-1},c)$, so $m>c^{\prime}n$ a.a.s. Now, conditional on $m>c^{\prime}n$, $c^{\prime}>u_{r,k-1}$ implies $\chi(G)\geq k$ a.a.s., by Theorem 1.2 and monotonicity (Observation 1.2).

Similarly, choose $c^{\prime\prime}\in(c,c_{r,k+1})$, so $m<c^{\prime\prime}n$ a.a.s. Then, conditional on $m<c^{\prime\prime}n$, $c^{\prime\prime}<c_{r,k+1}$ implies $\chi(G)\leq k+1$ a.a.s., by Theorem 1.2 and Observation 1.2. Thus $\chi(G)\in\left\{k,\,k+1\right\}$ a.a.s. ∎

We have shown the equivalence of various models for our problem when $\max\{k,r\}\geq 3$. We note that this equivalence does not hold for the case $k=r=2$, where the non-existence of a $2$-colouring is equivalent to the appearance of an odd cycle in a random graph. This is due to the absence of a sharp threshold for this appearance [9, Corollary 7]. Fortunately, this has little impact on our results.

Moment calculations

Let $r\geq 2$, $k\geq 1$ and recall that $u_{r,k}=k^{r-1}\ln k$. Suppose that $c\geq u_{r,k}$ is a positive constant and let $G\in\mathcal{G}^{*}(n,r,cn)$. Then a.a.s. $\chi(G)>k$.

First suppose that $k=1$. Since $c>0$, the hypergraph $G$ has at least one edge, so $\chi(G)>1$ with probability 1.

For the rest of the proof, assume that $k\geq 2$. Consider any $k$-partition $\sigma\in\Pi_{k}$ with block sizes $n_{i}$ $(i\in[k])$. Given $\sigma$, a random edge $e\in\mathcal{E}$ is monochromatic with probability

using Jensen’s inequality with the convex function $x^{r}$. Since the edges in $\mathcal{E}$ are chosen independently, the probability that $\sigma$ is a $k$-colouring of $G$ is at most $(1-1/k^{r-1})^{cn}$. Let $X$ be the number of $k$-colourings of $G$. Using (5) and the fact that $|\Pi_{k}|=k^{n}$, we conclude that $\Pr(X>0)\leq\mathbf{E}[X]\leq\left(k\,(1-1/k^{r-1})^{c}\right)^{n}$. If $c\geq u_{r,k}$ then $c>(k^{r-1}-\nicefrac{{1}}{{2}})\ln k$, and hence

where we have used Lemma 4.7 in the penultimate inequality. It follows that $\Pr(X>0)\to 0$ as $n\to\infty$ when $c>u_{r,k}$. ∎

We have proved the slightly stronger bound $(k^{r-1}-\nicefrac{{1}}{{2}})\ln k$. This is used in , and noted, but not used, in . Since the difference is small, we mainly use the simpler bound $k^{r-1}\ln k$.

In the remainder of the paper, we will assume that $k$ divides $n$, unless stated otherwise. Recall that $Z$ is the number of balanced colourings of $G\in\mathcal{G}^{*}(n,r,cn)$. Let $\Xi_{k}$ denote the set of all balanced $k$-partitions of $[n]$. For any balanced partition $\sigma\in\Xi_{k}$ and any $e\subseteq[n]$, let $M_{e}(\sigma)$ be the event that $|\sigma(e)|=1$. If $e$ is an edge of $G\in\mathcal{G}^{*}(n,r,cn)$ then clearly $\Pr(\overline{M_{e}(\sigma)})=1-1/k^{r-1}$, and these events are independent for $e\in\mathcal{E}$. Thus, since $|\Xi_{k}|=n!/\big((n/k)!\big)^{k}$,

We have suppressed the discretisation error $cn-\lfloor cn\rfloor$. This would apparently give an additional $O(1)$ factor in $\mathbf{E}[Z]$ here, and in $\mathbf{E}[Z^{2}]$ below. This is of no consequence for two reasons:

We need only prove that $\liminf_{n\to\infty}\mathbf{E}[Z^{2}]/\mathbf{E}[Z]=\Omega(1)$, so the correction is unimportant.

The asymptotic value for $\mathbf{E}[Z^{2}]/\mathbf{E}[Z]$ we obtain is independent of $n$, so using the sequence $c_{n}=\lfloor cn\rfloor/n$ gives the same asymptotic approximation as that given by using $c$.

2 Second moment

Using the notation of Section 2.1, let $\sigma,\tau\in\Xi_{k}$ be balanced partitions. Then $\overline{M_{e}(\sigma)}\cap\overline{M_{e}(\tau)}$ is the event that the edge $e$ is not monochromatic in either $\sigma$ or $\tau$. For $i,j\in[k]$, define

Now $\Pr(M_{e}(\sigma))=\Pr(M_{e}(\tau))=1/k^{r-1}$, and

We now apply Stirling’s inequality in the form

Let $\boldsymbol{J}_{0}$ be the $k\times k$ matrix with all entries equal to $1/k^{2}$. Then

Hence the term of (10) corresponding to $\boldsymbol{L}=n\boldsymbol{J}_{0}$ is asymptotically equal to

Observe from (8) that this term is smaller than $\mathbf{E}[Z]^{2}$ by a factor which is polynomial in $n$. We will find a positive constant $c_{r,k}$ such that when $c\in(0,c_{r,k})$, the function $F(\boldsymbol{X})$ has a unique maximum at $\boldsymbol{X}=\boldsymbol{J}_{0}$. This will allow us to apply the following theorem of Greenhill, Janson and Ruciński to estimate $\mathbf{E}[Z^{2}]$ in the region where $c<c_{r,k}$. (See that paper for background and definitions.)

$\phi$ is twice continuously differentiable in a neighbourhood of $x_{0}$ and $H:=D^{2}\phi(x_{0})$ is its Hessian at $x_{0}$.

Then provided $\det(-H|_{V})\neq 0$, as $n\to\infty$,

and the affine subspace $\eu{W}$ will consist of the matrices $\boldsymbol{X}$ such that all row and column sums are $1/k$, i.e.

The point $\eu{w}\in\eu{W}$ will be $\boldsymbol{J}_{0}$.

We wish to calculate $\mathbf{E}[Z^{2}]$, which by (10) equals

In Section 3 we will prove the following result.

Recall that $u_{r,k}=k^{r-1}\ln k$ for $r\geq 2,k\geq 1$. Now fix $r,k\geq 2$. There exists a positive constant $c_{r,k}\in(u_{r,k-1},\,u_{r,k})$ which satisfies

such that $F$ has a unique maximum in $\eu{K\cap W}$ at the point $\boldsymbol{J}_{0}\in\eu{K_{0}\cap W}$ whenever $c\in(0,c_{r,k})$.

Throughout this section we assume that Lemma 2.2 holds. Then $\boldsymbol{J}_{0}$ is the unique maximum of $F$ within $\eu{K\cap W}$, so we set $\euetahi:=F$ and $\eu{x_{0}}:=\boldsymbol{J}_{0}$. Note that $F$ is analytic in a neighbourhood of $\boldsymbol{J}_{0}$.

for any $k^{2}\times(k-1)^{2}$ matrix $U$ whose columns form a basis of $\mathcal{M}$.

Suppose that $r,k\geq 2$ and $0<c<c_{r,k}$, where $c_{r,k}$ satisfies Lemma 2.2. Then the determinant of $\mathcal{L}$ is $\det\mathcal{L}=k^{k-1}$ and the determinant of $-H|_{\mathcal{M}}$ is $(k^{2}\eualfa)^{(k-1)^{2}}$, where

It follows that $M$ is a $(k-1)\times(k-1)$ block matrix, with blocks of size $(k-1)\times(k-1)$, such that

We compute the determinant of matrices of this form in Lemma 4.2. Taking $p=q=k-1$ in Lemma 4.2, we have $\det M=k^{k-1}k^{k-1}=k^{2(k-1)}$. In particular, since the determinant is nonzero, it follows that the $\boldsymbol{U}_{ij}$ $(i,j\in[k-1])$ give a basis for $\mathcal{M}$. Also note that, after permuting its rows,

We also require the determinant of $-H|_{\mathcal{M}}$. For $\boldsymbol{X}\in\mathcal{M}$, let

Then $H=\big(h_{ij,i^{\prime}j^{\prime}}\big)$ has entries

Here we have used the fact that $F_{2}(\boldsymbol{J}_{0})=(1-1/k^{r-1})^{2}$.

where $I_{k}$ is the $k^{2}\times k^{2}$ identity matrix, $J$ is the $k^{2}\times k^{2}$ matrix with all entries equal to 1,

By (16), the determinant of $-H|_{\mathcal{M}}$ equals

Here we have used the fact that $JU=0$, which follows since every column of $U$ is an element of $\mathcal{M}$ and hence has zero sum. This completes the proof. ∎

Note that $\euetasi(\boldsymbol{J}_{0})=k^{k^{2}}$, while (13) gives $\euetahi(\boldsymbol{J}_{0})=F(\boldsymbol{J}_{0})=2\ln\big(k(1-1/k^{r-1})^{c}\big)$. Now $\eualfa$ is positive when $c\in(0,c_{r,k})$, using Lemma 2.2. Hence Lemma 2.3 guarantees that $\det(-H|_{\mathcal{M}})\neq 0$. Therefore we can apply Theorem 2.1 to (10), giving

Thus, from (8), for all $r,\,k\geq 2$ we have

which is a positive constant. So $\liminf_{n\to\infty}\Pr(Z>0)>0$ and we have established part (b′′) of Theorem 1.1, under the assumption that Lemma 2.2 holds.

It remains to prove Lemma 2.2, which is the focus of the next section.

Optimisation

We now consider maximising the function $F$ in (11), and develop conditions under which this function has a unique maximum at $\boldsymbol{J}_{0}$. In doing so, we will determine suitable constants $c_{r,k}$ and prove that Lemma 2.2 holds. This will complete the proof of Theorem 1.1.

Our initial goal will be to reduce the maximisation of $F$ to a univariate optimisation problem. This reduction is performed in several stages, presented in Sections 3.2–3.4. We analyse the resulting univariate problem in Sections 3.5–3.8. For more detail on our optimisation strategy, see Section 3.1. Finally, we consider a simplified asymptotic treatment of the univariate optimisation problem in Section 3.9.

As is common when working with convex functions, we define $x\ln x=+\infty$ for all $x<0$.

It will be convenient to rescale the variables, letting $\boldsymbol{A}=(a_{ij})$ be the $k\times k$ matrix defined by $\boldsymbol{A}=k\boldsymbol{X}$, so $a_{ij}=kx_{ij}$ for all $i,j\in[k]$. Substituting into (11), we can write

Letting $z=F(\boldsymbol{X})-\ln k$, we consider the optimisation problem

where we have used Hölder’s inequality in (21). Hence the system (19b)–(19e) is infeasible if $\rho\not\in[1,k^{r-1}]$, in which case we set $\max z=-\infty$. Conversely, it is easy to show that the system (19b)–(19e) is feasible for all $\rho\in[1,k^{r-1}]$. A formal proof of this is given in Lemma 4.3.

We wish to determine the structure of the maximising solutions in the optimisation problem (19). Following , we will relax the constraints (19d), and write (19b) as

By the same method as for Lemma 4.3, we can show that the system given by (19c), (19e) and (22) is feasible if and only if $\sum_{j=1}^{k}\varrho_{i}=\rho$ and $\varrho_{i}\in[1/k,k^{r-2}]$ for $i\in[k]$. Note that (20) and (21) assume $a_{ij}\geq 0$, but the relaxation of (19e) will be unimportant. Since $z=-\infty$ whenever some $a_{ij}<0$, these conditions must be satisfied automatically at any finite optimum.

Having dropped the constraints (19d), we can break (19) up into $k$ independent simpler one-row subproblems, if we specify the values $(\varrho_{1},\varrho_{2},\ldots,\varrho_{k})$ such that $\rho=\varrho_{1}+\varrho_{2}+\cdots+\varrho_{k}$. This is done in Section 3.2. Later in Section 3.3 we will determine the optimal values of $\varrho_{1},\varrho_{2},\ldots,\varrho_{k}$ for a fixed value of $\rho$. Then in Section 3.4 we will allow $\rho$ to vary.

Section 3.2 reduces the one-row problem (23) to an essentially one-variable problem (30). For this problem there is a unique optimum value of $\beta=\beta(\varrho)$ that is given in (29). This value of $\beta$ maximises the objective function, now expressed as $-\eu{f}(\beta)$: see (32). The nonlinear constraint (23b) will now have been replaced by an equation $\eu{g}(\beta)=k^{2-r}\varrho-k^{1-r}$, see (32).