A topological dynamical system with two different positive sofic entropies

Abstract

A sofic approximation to a countable group is a sequence of partial actions on finite sets that asymptotically approximates the action of the group on itself by left-translations. A group is sofic if it admits a sofic approximation. Sofic entropy theory is a generalization of classical entropy theory in dynamics to actions by sofic groups. However, the sofic entropy of an action may depend on a choice of sofic approximation. All previously known examples showing this dependence rely on degenerate behavior. This paper exhibits an explicit example of a mixing subshift of finite type with two different positive sofic entropies. The example is inspired by statistical physics literature on 2-colorings of random hyper-graphs.

1. Introduction

The topological entropy of a homeomorphism $T:X\to X$ of a compact Hausdorff space $X$ was introduced in 1. It was generalized to actions of amenable groups via Følner sequences in the 1970s 2 and to certain non-amenable groups via sofic approximations more recently 3. It plays a major role in the classification and structure theory of topological dynamical systems.

To explain further, suppose $\Gamma$ is a countable group with identity $1_\Gamma$ and $\sigma :\Gamma \to \operatorname {Sym}(V)$ is a map where $V$ is a finite set and $\operatorname {Sym}(V)$ is the group of permutations of $V$. It is not required that $\sigma$ is a homomorphism. Let $D \Subset \Gamma$ (the symbol $\Subset$ denotes a finite subset) and $\delta >0$. Then $\sigma$ is called

•

$(D,\delta )$-multiplicative if$$\begin{equation*} \#\{v\in V:\nobreakspace \sigma (gh)v = \sigma (g)\sigma (h)v\nobreakspace \forall g,h \in D\} > (1- \delta )|V|, \end{equation*}$$

•

$(D,\delta )$-trace preserving if$$\begin{equation*} \#\{v\in V:\nobreakspace \sigma (f)v\ne v\nobreakspace \forall f\in D\setminus \{1_\Gamma \} \} >(1- \delta ) |V|, \end{equation*}$$

•

$(D,\delta )$-sofic if it is both $(D,\delta )$-multiplicative and $(D,\delta )$-trace preserving.

A sofic approximation to $\Gamma$ consists of a sequence $\Sigma = \{\sigma _i\}_{i\in {\mathbb{N}}}$ of maps $\sigma _i:\Gamma \to \operatorname {Sym}(V_i)$ such that for all finite $D\subset \Gamma$, $\delta >0$ and all but finitely many $i$, $\sigma _i$ is $(D,\delta )$-sofic. A group is sofic if it admits a sofic approximation. In this paper we will usually assume $|V_i| = i$.

If $\Gamma$ acts by homeomorphisms on a compact Hausdorff space $X$ and a sofic approximation $\Sigma$ to $\Gamma$ is given then the $\Sigma$-entropy of the action is a topological conjugacy invariant, denoted by $h_\Sigma (\Gamma {\curvearrowright } X) \in \{-\infty \} \cup [0,\infty ]$. It is also called sofic entropy if $\Sigma$ is understood. It was first defined in 3 where the authors obtain a variational principle connecting it with the previously introduced notion of sofic measure entropy 4. It is monotone under embeddings and additive under direct products but not monotone under factor maps. See 5 for a survey.

A curious feature of this new entropy is that it may depend on the choice of sofic approximation. This is not always the case; for example, if $\Gamma$ is amenable then sofic entropy and classical entropy always agree. However, there are examples of actions $\Gamma {\curvearrowright } X$ by non-amenable groups $\Gamma$ with sofic approximations $\Sigma _1,\Sigma _2$ satisfying

$$\begin{equation*} h_{\Sigma _1}(\Gamma {\curvearrowright } X) = -\infty < h_{\Sigma _2}(\Gamma {\curvearrowright } X). \end{equation*}$$

See 5, Theorem 4.1. The case $h_{\Sigma _1}(\Gamma {\curvearrowright } X) = -\infty$ is considered degenerate: it implies that there are no good models for the action with respect to the given sofic approximation. Until this paper, it was an open problem whether a mixing action could have two different non-negative values of sofic entropy. Our main result is:

Theorem 1.1.

There exists a countable group $\Gamma$, a mixing action $\Gamma {\curvearrowright } X$ by homeomorphisms on a compact metrizable space $X$ and two sofic approximations $\Sigma _1,\Sigma _2$ to $\Gamma$ such that

$$\begin{equation*} 0< h_{\Sigma _1}(\Gamma {\curvearrowright } X) < h_{\Sigma _2}(\Gamma {\curvearrowright } X) <\infty . \end{equation*}$$

Remark 1.

The range of sofic entropies for an action $\Gamma {\curvearrowright } X$ is the set of all non-negative numbers of the form $h_\Sigma (\Gamma {\curvearrowright } X)$ as $\Sigma$ varies over all sofic approximations to $\Gamma$. By taking disjoint unions of copies of sofic approximations, it is possible to show the range of sofic entropies is an interval (which may be empty or a singleton). So for the example of Theorem 1.1, the range of sofic entropies is uncountable.

Remark 2.

It remains an open problem whether there is a measure-preserving action $\Gamma {\curvearrowright } (X,\mu )$ with two different non-negative sofic entropies. Theorem 1.1 does not settle this problem because it is entirely possible that any invariant measure $\mu$ on $X$ with $h_{\Sigma _2}(\Gamma {\curvearrowright } (X,\mu )) > h_{\Sigma _1}(\Gamma {\curvearrowright } X)$ satisfies $h_{\Sigma _1}(\Gamma {\curvearrowright } (X,\mu )) = -\infty$.

In this paper we often assume $V_n = [n] \coloneq \{1$, $2$, …, $n\}$.

1.1. Random sofic approximations

We do not know of any explicit sofic approximations to $\Gamma$ which are amenable to analysis. Instead, we study random sofic approximations. For the purposes of this paper, these are sequences $\{{\mathbb{P}}_n\}_n$ of probability measures ${\mathbb{P}}_n$ on spaces of homomorphisms ${\operatorname {Hom}}(\Gamma , \operatorname {Sym}(n))$ such that, for any finite $D\subset \Gamma$ and $\delta >0$ there is an $\epsilon >0$ such that

$$\begin{equation*} {\mathbb{P}}_n(\sigma \text{ is $(D,\delta )$-sofic}) > 1-n^{-\epsilon n} \end{equation*}$$

for all sufficiently large $n$. Because $n^{-\epsilon n}$ decays super-exponentially, if $\Omega _n \subset {\operatorname {Hom}}(\Gamma ,\operatorname {Sym}(n))$ is any sequence with an exponential lower bound of the form ${\mathbb{P}}_n(\Omega _n)>e^{-cn}$ (for some constant $c>0$) then there exists a sofic approximation $\Sigma =\{\sigma _n\}$ with $\sigma _n \in \Omega _n$ for all $n$.

It is this non-constructive existence result that enables us to use random sofic approximations to prove Theorem 1.1.

1.2. Proper colorings of random hyper-graphs from a statistical physics viewpoint

The idea for our main construction comes from studies of proper colorings of random hyper-graphs. Although these studies have very different motivations than those that inspired this paper, the examples that they provide are roughly the same as the examples used to prove Theorem 1.1. The relevant literature and an outline is presented next.

A hyper-graph is a pair $G=(V,E)$ where $E$ is a collection of subsets of $V$. Elements of $E$ are called hyper-edges but we will call them edges for brevity’s sake. $G$ is $k$-uniform if every edge $e\in E$ has cardinality $k$.

A 2-coloring of $G$ is a map $\chi :V \to \{0,1\}$. An edge $e \in E$ is monochromatic for $\chi$ if $|\chi (e)|=1$. A coloring is proper if it has no monochromatic edges.

Let $H_k(n,m)$ denote a hyper-graph chosen uniformly among all ${ { n \choose k} \choose m}$ $k$-uniform hyper-graphs with $n$ vertices and $m$ edges. We will consider the number of proper 2-colorings of $H_k(n,m)$ when $k$ is large but fixed, and the ratio of edges to vertices $r\coloneq m/n$ is bounded above and below by constants.

This random hyper-graph model was studied in 678. These works are motivated by the satisfiability conjecture. To explain, the lower satisfiability threshold $r^-_{\mathrm{sat}}=r^-_{\mathrm{sat}}(k)$ is the supremum over all $r$ such that

$$\begin{equation*} \lim _{n\to \infty } \operatorname {Pr}[H_k(n, \lceil r n \rceil )\text{ is properly 2-colorable}] = 1. \end{equation*}$$

The upper satisfiability threshold $r^+_{\mathrm{sat}}=r^+_{\mathrm{sat}}(k)$ is the infimum over all $r$ such that

$$\begin{equation*} \lim _{n\to \infty } \operatorname {Pr}[H_k(n, \lceil r n \rceil )\text{ is properly 2-colorable}] = 0. \end{equation*}$$

The satisfiability conjecture posits that $r^-_{\mathrm{sat}} = r^+_{\mathrm{sat}}$. It is still open.

Bounds on these thresholds were first obtained in 6 as follows. Let $Z(G)$ be the number of proper 2-colorings of a hyper-graph $G$. A first moment computation shows that

$$\begin{equation*} f_k(r) = \lim _{n\to \infty } n^{-1} \log {\mathbb{E}}[Z(H_k(n, \lceil rn \rceil ))], \end{equation*}$$

where $f_k(r)\coloneq \log (2) + r \log (1-2^{1-k})$. Let $r_{\mathrm{first}} = r_{\mathrm{first}} (k)$ be such that $f_k(r_{\mathrm{first}})=0$. If $r>r_{\mathrm{first}}$ then $f_k(r)<0$. Therefore $r^+_{\mathrm{sat}} \le r_{\mathrm{first}}$.

Let $r_{\mathrm{second}}$ be the supremum over numbers $r\ge 0$ such that the second moment ${\mathbb{E}}[Z(H_k(n, \lceil rn \rceil ))^2]$ is equal to ${\mathbb{E}}[Z(H_k(n, \lceil rn \rceil ))]^2$ up to sub-exponential factors. The Paley-Zygmund inequality gives the bound $r_{\mathrm{second}} \le r^-_{\mathrm{sat}}$.

In 6, it is shown that

$$\begin{align*} r_{\mathrm{first}} &= \frac{\log (2)}{2} 2^k - \frac{\log (2)}{2} + O(2^{-k}),\\ r_{\mathrm{second}} &= \frac{\log (2)}{2} 2^k - \frac{\log (2)+1}{2} + O(2^{-k}). \end{align*}$$

So there is a constant-sized gap between the two thresholds.

A more detailed view of the second moment is illuminating. But before explaining, we need some terminology. Let $[n]$ be the set of natural numbers $\{1,2,..,n\}$. A coloring $\chi$ of $[n]$ is equitable if $|\chi ^{-1}(0)|=|\chi ^{-1}(1)|$. We will assume from now on that $n$ is even so that equitable colorings of $[n]$ exist. Let $Z_e(G)$ be the number of equitable proper colorings of a hyper-graph $G$. A computation shows that ${\mathbb{E}}[Z(H_k(n, \lceil rn \rceil ))]$ equals ${\mathbb{E}}[Z_e(H_k(n, \lceil rn \rceil ))]$ up to sub-exponential factors. This enables us to work with equitable proper colorings in place of all proper colorings. This reduces the computations because there is only one equitable coloring up to the action of the symmetric group $\operatorname {Sym}(n)$.

A computation shows that the second moment factorizes as

$$\begin{equation*} {\mathbb{E}}[Z_e(H_k(n, m))^2] = {\mathbb{E}}[Z_e(H_k(n, m))]{\mathbb{E}}[Z_e(H_k(n,m)) | \chi \text{ is proper}], \end{equation*}$$

where $\chi :[n] \to \{0,1\}$ is any equitable 2-coloring. Let $H^\chi _k(n, m)$ be the random hyper-graph chosen by conditioning $H_k(n,m)$ on the event that $\chi$ is a proper 2-coloring. This is called the planted model and $\chi$ is the planted coloring. So computing the second moment of $Z_e(H_k(n, m))$ reduces to computing the first moment of $Z_e(H^\chi _k(n,m))$.

The normalized Hamming distance between colorings $\chi ,\chi ': [n] \to \{0,1\}$ is

$$\begin{equation*} d_n(\chi ,\chi ') = n^{-1} \#\{v\in [n]:\nobreakspace \chi (v) \ne \chi '(v)\}. \end{equation*}$$

Let $Z^\chi (\delta )$ be the number of equitable proper colorings $\chi '$ with $d_n(\chi ,\chi ')=\delta$. Then

$$\begin{equation*} Z_e(H^\chi _k(n,m)) = \sum _\delta Z^\chi (\delta ). \end{equation*}$$

In 6, it is shown that ${\mathbb{E}}[Z^\chi (\delta )| \chi \text{ is proper}]$ is equal to $\exp (n \psi (\delta ))$ (up to sub-exponential factors) where $\psi$ is an explicit function.

Note that $\psi (\delta )=\psi (1-\delta )$ (since if $\chi '$ is a proper equitable coloring then so is $1-\chi '$ and $d_n(\chi ,1-\chi ')=1-d_n(\chi ,\chi ')$). A computation shows $\psi (1/2)=f_k(r)$. If $r<r_{\mathrm{second}}$ then $\psi (\delta )$ is uniquely maximized at $\delta =1/2$. However, if $r>r_{\mathrm{second}}$ then the maximum of $\psi$ is attained in the interval $\delta \in [0,2^{-k/2}]$. In fact, $\psi (\delta )$ is negative for $\delta \in [2^{-k/2}, 1/2 - 2^{-k/2}]$. So with high probability, there are no proper equitable colorings $\chi '$ with $d_n(\chi ,\chi ') \in [2^{-k/2}, 1/2 - 2^{-k/2}]$. This motivates defining the local cluster, denoted ${\mathcal{C}}(\chi )$, to be the set of all proper equitable 2-colorings $\chi '$ with $d_n(\chi ,\chi ') \le 2^{-k/2}$.

The papers 78 obtain a stronger lower bound on the lower satisfiability threshold using an argument they call the enhanced second moment method. To explain, we need some terminology. We say a proper equitable coloring $\chi$ is good if the size of the local cluster $|{\mathcal{C}}(\chi )|$ is bounded by ${\mathbb{E}}[Z_e(H_k(n,m))]$. One of the main results of 78 is that $\Pr [ \chi \text{ is good} | \chi \text{ is proper}]$ tends to 1 as $n\to \infty$ with $m = rn + O(1)$ and $r < r_{\mathrm{second}} + \frac{1-\log (2)}{2} + o_k(1)$. An application of the Paley-Zygmund inequality to the number of good colorings yields the improved lower bound

$$\begin{equation*} r_{\mathrm{second}} + \frac{1-\log (2)}{2} + o_k(1) \le r^-_{\mathrm{sat}}. \end{equation*}$$

The argument showing $\Pr [ \chi \text{ is good} | \chi \text{ is proper}]\to 1$ is combinatorial. It is shown that (with high probability) there is a set $R \subset [n]$ with cardinality $|R| \approx (1-2^{-k})n$ which is rigid in the following sense: if $\chi ':[n] \to \{0,1\}$ is any proper equitable 2-coloring then either: the restriction of $\chi '$ to $R$ is the same as the restriction of $\chi$ to $R$ or $d_n(\chi ',\chi )$ is at least $cn/k^t$ for some constants $c,t>0$. This rigid set is constructed explicitly in terms of local combinatorial data of the coloring $\chi$ on $H^\chi _k(n,m)$.

In summary, these papers study two random models $H_k(n,m)$ and $H^\chi _k(n,m)$. When $r=m/n$ is in the interval $(r_{\mathrm{second}}, r_{\mathrm{second}} + \frac{1-\log (2)}{2})$, the typical number of proper colorings of $H_k(n, m)$ grows exponentially in $n$ but is smaller (by an exponential factor) than the expected number of proper colorings of $H^\chi _k(n,m)$. It is these facts that we will generalize, by replacing $H_k(n,m), H^\chi (n,m)$ with random sofic approximations to a group $\Gamma$ so that the exponential growth rate of the number of proper colorings roughly corresponds with sofic entropy.

Although the models that we study in this paper are similar to the models in 678, they are different enough that we develop all results from scratch. Moreover, although the strategies we employ are roughly same, the proof details differ substantially. The reader need not be familiar with these papers to read this paper.

1.3. The action

In the rest of this introduction, we introduce the action $\Gamma {\curvearrowright } X$ in Theorem 1.1 and outline the first steps of its proof. So fix positive integers $k,d$. Let

$$\begin{equation*} \Gamma =\langle s_1,\ldots , s_d:\nobreakspace s_1^k = s_2^k =\cdots = s_d^k =1 \rangle \end{equation*}$$

be the free product of $d$ copies of ${\mathbb{Z}}/k{\mathbb{Z}}$.

The Cayley hyper-tree of $\Gamma$, denoted $G=(V,E)$, has vertex set $V=\Gamma$. The edges are the left-cosets of the generator subgroups. That is, each edge $e\in E$ has the form $e=\{gs_i^j:\nobreakspace 0\le j \le k-1\}$ for some $g \in \Gamma$ and $1\le i \le d$.

Remark 3.

It can be shown by considering each element of $\Gamma$ as a reduced word in the generators $s_1$, …, $s_d$ that $G$ is a hyper-tree in the sense that there exists a unique “hyper-path” between any two vertices. More precisely, for any $v,w \in V$, there exists a unique sequence of edges $e_1,..,e_l$ such that $v \in e_1$, $w \in e_l$, $|e_i \cap e_{i+1}| = 1$, $e_i \neq e_j$ for any $i \neq j$, and $v \notin e_{2}$, $w \notin e_{l-1}$. More intuitively, there are no “hyper-loops” in $G$.

The group $\Gamma$ acts on $\{0,1\}^\Gamma$ by $(gx)_f = x_{g^{-1}f}$ for $g,f \in \Gamma , x \in \{0,1\}^\Gamma$. Let $X\subset \{0,1\}^\Gamma$ be the subset of proper 2-colorings. It is a closed $\Gamma$-invariant subspace. Furthermore, $\Gamma {\curvearrowright } X$ is topologically mixing:

Claim 1.

For any nonempty open sets $A$, $B$ in $X$, there exists $N$ such that for any $g \in \Gamma$ with $|g| > N$, $gA \cap B \neq \emptyset$. Here $|g|$ denotes the shortest word length of representations of $g$ by generators $s_1$, …, $s_d$.

Proof.

It suffices to show the claim for $A$,$B$ being cylinder sets. We make a further simplification by assuming each $A$, $B$ is a cylinder set on a union of hyper-edges, and a yet further simplification that each $A$, $B$ is a cylinder set on a connected union of hyper-edges. Informally, by shifting the “coordinates” on which $A$ depends so that they are far enough separated from the coordinates on which $B$ depends, we can always fill in the rest of the graph to get a proper coloring.

More precisely, suppose $A = \{x \in X: x \upharpoonright F_A = \chi _A \}$, where ${\mathcal{F}}_A \subset E$ such that for any $e_1$, $e_2 \in {\mathcal{F}}_A$ there is a finite sequence of $f_1$, $\cdots$, $f_{\ell } \in {\mathcal{F}}_A$ such that $e_1 \cap f_1 \neq \emptyset$, $f_i \cap f_{i+1} \neq \emptyset$, and $f_\ell \cap e_2 \neq \emptyset$, $F_A =\cup _{e\in {\mathcal{F}}_A}e$, and $\chi _A : F_A \to \{0,1\}$ and similarly $B = \{x \in X: x \upharpoonright F_B = \chi _B \}$. $\chi _A$ and $\chi _B$ must be bichromatic on each edge in their respective domains since $A$ and $B$ are nonempty.

Let $N = \max \{|h|: h \in F_A\} + \max \{|h|: h \in F_B\} + k$. Then it can be shown for any $g$ with $|g| > N$ that $g^{-1}F_A \cap F_B = \emptyset$. It follows from our earlier remark that there exists a unique hyper-path connecting $g^{-1}F_A$ to $F_B$ (otherwise there would be a hyperloop in $G$). Thus for example one can recursively fill in a coloring on the rest of $\Gamma$ by levels of hyperedges - first the hyperedges adjacent to $g^{-1}F_A$ and $F_B$, then the next layer of adjacent hyperedges, and so on. At each step, most hyperedges only have one vertex whose color is determined, so it is always possible to color another vertex of an edge to make it bichromatic. Only along the hyper-path connecting $g^{-1}F_A$ to $F_B$ at some step there will be a hyperedge with two vertices whose colors are already determined, but since $k$ is large there is still another vertex to color to make the edge bichromatic.

■

We will show that for certain values of $k,d$, the action $\Gamma {\curvearrowright } X$ satisfies the conclusion of Theorem 1.1.

1.4. Sofic entropy of the shift action on proper colorings

Given a homomorphism $\sigma :\Gamma \to \operatorname {Sym}(V)$, let $G_\sigma =(V,E_\sigma )$ be the hyper-graph with vertices $V$ and edges equal to the orbits of the generator subgroups. That is, a subset $e \subset V$ is an edge if and only if $e = \{\sigma (s^j_i)v\}_{j=0}^{k-1}$ for some $1\le i \le d$ and $v \in V$.

Recall that a hyper-graph is $k$-uniform if every edge has cardinality $k$. We will say that a homomorphism $\sigma :\Gamma \to \operatorname {Sym}(V)$ is uniform if $G_\sigma$ is $k$-uniform. Equivalently, this occurs if for all $1\le i \le d$, $\sigma (s_i)$ decomposes into a disjoint union of $k$-cycles.

A 2-coloring $\chi :V \to \{0,1\}$ of a hyper-graph $G$ is $\epsilon$-proper if the number of monochromatic edges is $\le \epsilon |V|$. Using the formulation of sofic entropy in 5 (which was inspired by 9), we show in §2 that if $\Sigma =\{\sigma _n\}_{n\ge 1}$ is a sofic approximation to $\Gamma$ by uniform homomorphisms then the $\Sigma$-entropy of $\Gamma {\curvearrowright } X$ is:

$$\begin{equation*} h_\Sigma (\Gamma {\curvearrowright } X)\coloneq \inf _{\epsilon >0} \limsup _{i\to \infty } |V_i|^{-1} \log \#\{\epsilon \text{-proper $2$-colorings of $G_{\sigma _i}$}\}. \end{equation*}$$

1.5. Random hyper-graph models

Definition 1.

Let ${\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ denote the set of all uniform homomorphisms from $\Gamma$ to $\operatorname {Sym}(n)$. Let ${\mathbb{P}}^u_n$ be the uniform probability measure on ${\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ and let ${\mathbb{E}}^u_n$ be its expectation operator. The measure ${\mathbb{P}}^u_n$ is called the uniform model. We will always assume $n \in k{\mathbb{Z}}$ so that ${\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ is non-empty. In §3 we show that $\{{\mathbb{P}}^u_n\}_{n\ge 1}$ is a random sofic approximation. We will use the uniform model to obtain the sofic approximation $\Sigma _1$ which appears in Theorem 1.1.

Recall that if $V$ is a finite set, then a 2-coloring $\chi :V \to \{0,1\}$ is equitable if $|\chi ^{-1}(0)|=|\chi ^{-1}(1)|$. We assume from now on that $n$ is even so that equitable colorings of $[n]$ exist.

Definition 2.

Fix an equitable coloring $\chi :[n] \to \{0,1\}$. Let ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ be the set of all uniform homomorphisms $\sigma :\Gamma \to \operatorname {Sym}(n)$ such that $\chi$ is proper as a coloring on $G_\sigma$. Let ${\mathbb{P}}^\chi _n$ be the uniform probability measure on ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ and let ${\mathbb{E}}^\chi _n$ be its expectation operator. The measure ${\mathbb{P}}^\chi _n$ is called the planted model and $\chi$ is the planted coloring. When $\chi$ is understood, we will write ${\mathbb{P}}^p_n$ and ${\mathbb{E}}^p_n$ instead of ${\mathbb{P}}^\chi _n$ and ${\mathbb{E}}^\chi _n$. In §3 we show that $\{{\mathbb{P}}^p_n\}_{n\ge 1}$ is a random sofic approximation. We will use the planted model to obtain the sofic approximation $\Sigma _2$ which appears in Theorem 1.1.

Remark 4.

If $\chi$ and $\chi '$ are both equitable $2$-colorings then there are natural bijections from ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ to ${\operatorname {Hom}}_{\chi '}(\Gamma ,\operatorname {Sym}(n))$ as follows. Given a permutation $\pi \in \operatorname {Sym}(n)$ and $\sigma :\Gamma \to \operatorname {Sym}(n)$, define $\sigma ^\pi : \Gamma \to \operatorname {Sym}(n)$ by $\sigma ^\pi (g) = \pi \sigma (g) \pi ^{-1}$. Because $\chi$ and $\chi '$ are equitable, there exists $\pi \in \operatorname {Sym}(n)$ such that $\chi = \chi ' \circ \pi$. The map $\sigma \mapsto \sigma ^\pi$ defines a bijection from ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ to ${\operatorname {Hom}}_{\chi '}(\Gamma ,\operatorname {Sym}(n))$. Moreover $\pi$ defines a hyper-graph-isomorphism from $G_\sigma$ to $G_{\sigma ^\pi }$. Therefore, any random variable on ${\operatorname {Hom}}(\Gamma ,\operatorname {Sym}(n))$ that depends only on the hyper-graph $G_\sigma$ up to hyper-graph-isomorphism has the same distribution under ${\mathbb{P}}^\chi _n$ as under ${\mathbb{P}}^{\chi '}_n$. This justifies calling ${\mathbb{P}}^\chi _n$ the planted model.

1.6. The strategy and a key lemma

The idea behind the proof of Theorem 1.1 is to show that for some choices of $(k,d)$, the uniform model admits an exponential number of proper 2-colorings, but it has exponentially fewer proper 2-colorings than the expected number of proper colorings of the planted model (with probability that decays at most sub-exponentially in $n$).

To make this strategy more precise, we introduce the following notation. Let $Z(\epsilon ;\sigma )$ denote the number of $\epsilon$-proper 2-colorings of $G_\sigma$. A coloring is $\sigma$-proper if it is $(0,\sigma )$-proper. Let $Z(\sigma )=Z(0;\sigma )$ be the number of $\sigma$-proper 2-colorings.

In §3, the proof of Theorem 1.1 is reduced to the Key Lemma:

Lemma 1.2 (Key Lemma).

Let $f(d,k)\coloneq \log (2) + \frac{d}{k} \log (1-2^{1-k})$. Also let $r=d/k$. Then

$$\begin{equation} f(d,k)= \lim _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{u}[ Z(\sigma )] = \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{u}[ Z(\epsilon ;\sigma )] . {\tag{1}} \end{equation}$$

Moreover, for any

$$\begin{equation*} 0<\eta _0 < \eta _1 < (1-\log 2)/2, \end{equation*}$$

there exists $k_0$ (depending on $\eta _0,\eta _1$) such that for all $k\ge k_0$ if

$$\begin{equation*} r=d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta \in [\eta _0,\eta _1]$ then

$$\begin{equation} f(d,k) < \liminf _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )] . {\tag{2}} \end{equation}$$

Also,

$$\begin{equation} 0= \inf _{\epsilon >0} \liminf _{n\to \infty } n^{-1} \log \left({\mathbb{P}}_n^{u}\left( \left| n^{-1}\log Z(\sigma ) - f(d,k) \right| < \epsilon \right)\right). {\tag{3}} \end{equation}$$

In all cases above, the limits are over $n \in 2{\mathbb{Z}} \cap k{\mathbb{Z}}$.

Equations 1 and 2 are proven in §4 and §5 using first and second moment arguments respectively. This part of the paper is similar to the arguments used in 6.

Given $\sigma : \Gamma \to \operatorname {Sym}(n)$ and $\chi : [n] \to \{0,1\}$, let ${\mathcal{C}}_\sigma (\chi )$ be the set of all proper equitable colorings $\chi ':[n]\to \{0,1\}$ with $d_n(\chi ,\chi ')\le 2^{-k/2}$. In section §5.2, second moment arguments are used to reduce equation 3 to the following:

Proposition 5.9.

Let $0<\eta _0 < (1-\log 2)/2$. Then for all sufficiently large $k$ (depending on $\eta _0$), if

$$\begin{equation*} r \coloneq d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta$ with $\eta _0\le \eta < (1-\log 2)/2$ then with high probability in the planted model, $|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)$. In symbols,

$$\begin{equation*} \lim _{n\to \infty } {\mathbb{P}}^\chi _n\big (|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)\big )=1. \end{equation*}$$

In §6, Proposition 5.9 is reduced as follows. First, certain subsets of vertices are defined through local combinatorial constraints. There are two main lemmas concerning these subsets; one of which bounds their density and the other proves they are ‘rigid’. Proposition 5.9 is proven in §6 assuming these lemmas.

The density lemma is proven in §7 using a natural Markov model on the space of proper colorings that is the local-on-average limit of the planted model. Rigidity is proven in §8 using an expansivity argument similar to the way random regular graphs are proven to be good expanders. This completes the last step of the proof of Theorem 1.1.

2. Topological sofic entropy

This section defines topological sofic entropy for subshifts using the formulation from 9. The main result is:

Lemma 2.1.

For any sofic approximation $\Sigma \!=\!\{\sigma _n\}$ with $\sigma _n \!\in \! {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$,

$$\begin{equation*} h_\Sigma (\Gamma {\curvearrowright } X) = \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log Z(\epsilon ;\sigma _n). \end{equation*}$$

Let $\Gamma$ denote a countable group, ${\mathcal{A}}$ a finite set (called the alphabet). Let $T = (T^g)_{g\in \Gamma }$ be the shift action on ${\mathcal{A}}^\Gamma$ defined by $T^gx(f)= x(g^{-1}f)$ for $x \in A^\Gamma$. Let $X \subset {\mathcal{A}}^\Gamma$ be a closed $\Gamma$-invariant subspace. We denote the restriction of the action to $X$ by $\Gamma {\curvearrowright } X$. Also let $\Sigma =\{\sigma _i:\Gamma \to {\operatorname {Sym}}(V_i)\}_{i \in {\mathbb{N}}}$ be a sofic approximation to $\Gamma$.

Given $\sigma :\Gamma \to {\operatorname {Sym}}(V)$, $v \in V$ and $x:V \to {\mathcal{A}}$ the pullback name of $x$ at $v$ is defined by

$$\begin{equation*} \Pi ^\sigma _v(x) \in {\mathcal{A}}^\Gamma ,\quad \Pi ^\sigma _v(x)(g) = x_{\sigma (g^{-1})v} \quad \forall g \in \Gamma . \end{equation*}$$

For the sake of building some intuition, note that when $\sigma$ is a homomorphism, the map $v \mapsto \Pi ^\sigma _{v}(x)$ is $\Gamma$-equivariant (in the sense that $\Pi ^\sigma _{\sigma (g)v}(x) = g \Pi ^\sigma _{v}(x)$). In particular $\Pi ^\sigma _{v}(x) \in {\mathcal{A}}^\Gamma$ is periodic. In general, we think of $\Pi ^\sigma _v(x)$ as an approximate periodic point.

Given an open set ${\mathcal{O}} \subset {\mathcal{A}}^\Gamma$ containing $X$ and an $\epsilon >0$, a map $x:V \to {\mathcal{A}}$ is called an $({\mathcal{O}},\epsilon ,\sigma )$-microstate if

$$\begin{equation*} \#\{ v \in V:\nobreakspace \Pi ^\sigma _v(x) \in {\mathcal{O}}\} \ge (1-\epsilon )|V|. \end{equation*}$$

Let $\Omega ({\mathcal{O}},\epsilon ,\sigma ) \subset {\mathcal{A}}^V$ denote the set of all $({\mathcal{O}},\epsilon ,\sigma )$-microstates. Finally, the $\Sigma$-entropy of the action is defined by

$$\begin{equation*} h_\Sigma (\Gamma {\curvearrowright } X)\coloneq \inf _{\mathcal{O}} \inf _{\epsilon >0} \limsup _{i\to \infty } |V_i|^{-1} \log \#\Omega ({\mathcal{O}},\epsilon ,\sigma _i), \end{equation*}$$

where the infimum is over all open neighborhoods of $X$ in ${\mathcal{A}}^\Gamma$. This number depends on the action $\Gamma {\curvearrowright } X$ only up to topological conjugacy. It is an exercise in 5 to show that this definition agrees with the definition in 10. We include a proof in Appendix A for completeness.

Proof of Lemma 2.1.

Let $\epsilon >0$ be given. Let $S(\epsilon ;\sigma _n) \subset 2^{V_n}$ be the set of $(\epsilon ,\sigma _n)$-proper 2-colorings. Let ${\mathcal{O}}_0 \subset 2^\Gamma$ be the set of all 2-colorings $\chi :\Gamma \to \{0,1\}$ such that for each generator hyper-edge $e \subset \Gamma$, $\chi (e) = \{0,1\}$. A generator hyper-edge is a subgroup of the form $\{s_i^j:\nobreakspace 0\le j <k\}$ for some $i$. Note ${\mathcal{O}}_0$ is an open superset of $X$.

We claim that $\Omega ({\mathcal{O}}_0, k\epsilon /d, \sigma _n) \subset S(\epsilon ;\sigma _n)$. To see this, let $\chi \in \Omega ({\mathcal{O}}_0, k\epsilon /d, \sigma _n)$. Then $\Pi ^{\sigma _n}_v(\chi ) \in {\mathcal{O}}_0$ if and only if all hyper-edges of $G_\sigma$ containing $v$ are bi-chromatic (with respect to $\chi$). So if $\Pi _v^{\sigma _n} \notin {\mathcal{O}}_0$, then $v$ is contained in up to $d$ monochromatic hyperedges. On the other hand, each monochromatic hyperedge contains exactly $k$ vertices whose pullback name is not in ${\mathcal{O}}_0$. It follows that $\chi \in S(\epsilon ; \sigma _n)$. This implies $h_\Sigma (\Gamma {\curvearrowright } X) \le \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log Z(\epsilon ;\sigma _n)$.

Given a finite subset ${\mathcal{F}}$ of hyper-edges of the Cayley hyper-tree, let ${\mathcal{O}}_{\mathcal{F}}$ be the set of all $\chi \in 2^\Gamma$ with the property that $\chi (e) = \{0,1\}$ for all $e \in {\mathcal{F}}$. If ${\mathcal{O}}'$ is any open neighborhood of $X$ in $2^\Gamma$ then ${\mathcal{O}}'$ contains ${\mathcal{O}}_{\mathcal{F}}$ for some ${\mathcal{F}}$. To see this, suppose that there exist elements $\chi _{\mathcal{F}} \in {\mathcal{O}}_{\mathcal{F}}\setminus {\mathcal{O}}'$ for every finite ${\mathcal{F}}$. Let $\chi$ be a cluster point of $\{\chi _{\mathcal{F}}\}$ as ${\mathcal{F}}$ increases to the set $E$ of all hyper-edges. Then $\chi \in X \setminus {\mathcal{O}}'$, a contradiction. It follows that

$$\begin{equation*} h_\Sigma (\Gamma {\curvearrowright } X)= \inf _{\mathcal{F}} \inf _{\epsilon >0} \limsup _{i\to \infty } |V_i|^{-1} \log \#\Omega ({\mathcal{O}}_{\mathcal{F}},\epsilon ,\sigma _i). \end{equation*}$$

Next, fix a finite subset ${\mathcal{F}}$ of hyper-edges of the Cayley hyper-tree. We claim that $S\left(\frac{\epsilon }{k|{\mathcal{F}}|}; \sigma _n\right) \subset \Omega ({\mathcal{O}}_{\mathcal{F}},\epsilon ,\sigma _n)$. To see this, let $\chi \in S\left(\frac{\epsilon }{k|{\mathcal{F}}|}; \sigma _n\right)$ and $B(\chi ,\sigma _n) \subset V_n$ be the set of vertices contained in a monochromatic edge of $\chi$. Now for $v \in V_n$, $\Pi _v^{\sigma _n}(\chi ) \notin {\mathcal{O}}_{\mathcal{F}}$ if and only if $\Pi _v^{\sigma _n}(\chi )$ is monochromatic on some edge in ${\mathcal{F}}$. This occurs if and only if there is an element $f \in \Gamma$ in the union of ${\mathcal{F}}$ such that $\sigma _n(f^{-1})v \in B(\chi ,\sigma _n)$. There are at most $k |{\mathcal{F}}| |B(\chi ,\sigma _n)|$ such vertices. But $|B(\chi ,\sigma _n)| \leq (\frac{\epsilon }{|{\mathcal{F}}|})n$, so there are at most $k \epsilon n$ such vertices. It follows that $\chi \in \Omega ({\mathcal{O}}_{\mathcal{F}}, \epsilon , \sigma _n)$. Therefore,

$$\begin{equation*} \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log Z(\epsilon ;\sigma _n) \le \inf _{\mathcal{F}} \inf _{\epsilon >0} \limsup _{i\to \infty } |V_i|^{-1} \log \#\Omega ({\mathcal{O}}_{\mathcal{F}},\epsilon ,\sigma _i)= h_\Sigma (\Gamma {\curvearrowright } X). \end{equation*}$$■

3. Reduction to the key lemma

The purpose of this section is to show how Lemma 1.2 implies Theorem 1.1. This requires replacing the (random) uniform and planted models with (deterministic) sofic approximations. The next lemma facilitates this replacement.

Lemma 3.1.

Let $D \subset \Gamma$ be finite and $\delta >0$. Then there are constants $\epsilon ,N_0>0$ such that for all $n > N_0$ with $n \in 2{\mathbb{Z}} \cap k{\mathbb{Z}}$,

$$\begin{equation*} {\mathbb{P}}^u_n\{\sigma :\nobreakspace \sigma \text{ is not $(D,\delta )$-sofic} \} \le n^{-\epsilon n}, \end{equation*}$$

$$\begin{equation*} {\mathbb{P}}^p_n\{\sigma :\nobreakspace \sigma \text{ is not $(D,\delta )$-sofic} \} \le n^{-\epsilon n}. \end{equation*}$$

Proof.

The proof given here is for the uniform model. The planted model is similar.

The proof begins with a series of four reductions. By taking a union bound, it suffices to prove the special case in which $D=\{w\}$ for $w \in \Gamma$ nontrivial. (This is the first reduction).

Let $w = s_{i_l}^{r_l}\cdots s_{i_1}^{r_1}$ be the reduced form of $w$. This means that $i_j \in \{1$,…, $d\}$, $i_j \ne i_{j+1}$ for all $j$ with indices mod $l$ and $1\le r_j <k$ for all $j$. Let $|w|=r_1+\cdots + r_l$ be the length of $w$.

For any $g \in \Gamma$, the fixed point sets of $\sigma (gwg^{-1})$ and $\sigma (w)$ have the same size. So after conjugating if necessary, we may assume that either $l=1$ or $i_1 \ne i_l$.

For $1\le j\le l$, the $j$-th beginning subword of $w$ is the element $w_j = s_{i_j}^{r_j}\cdots s_{i_1}^{r_1}$. Given a vertex $v \in V_n$ and $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$, let $p(v,\sigma )=(e_1$, …, $e_l)$ be the path defined by: for each $j$, $e_j$ is the unique hyper-edge of $G_\sigma$ labeled $i_j$ containing $\sigma (w_j)v$. A vertex $v \in V_n$ represents a $(\sigma ,w)$-simple cycle if $\sigma (w)v=v$ and for every $1\le a<b \le l$, either

•

$e_a \cap e_b =\emptyset$,

•

$b=a+1$ and $|e_a \cap e_b| = 1$,

•

or $(a,b)=(1,l)$ and $|e_a \cap e_b|=1$.

We say that $v$ represents a $(\sigma ,w)$-simple degenerate cycle if $\sigma (w)v = v$ and $l = 2$ and $|e_1 \cap e_2| \ge 2$.

If $\sigma (w)v = v$ then either

•

$v$ represents a $(\sigma ,w)$-simple cycle,

•

there exists nontrivial $w' \in \Gamma$ with $|w'| \le |w|+k$ such that some vertex $v_0 \in \cup _j e_j$ represents a $(\sigma ,w')$-simple cycle,

•

or there exists nontrivial $w' \in \Gamma$ with $|w'| \le |w|+k$ such that some vertex $v_0 \in \cup _j e_j$ represents a $(\sigma ,w')$-simple degenerate cycle.

So it suffices to prove there are constants $\epsilon ,N_0>0$ such that for all $n > N_0$,

$$\begin{equation*} {\mathbb{P}}^u_n\big \{\sigma :\nobreakspace \#\{v \in [n]:\nobreakspace v \text{ represents a $(\sigma ,w)$-simple cycle} \}\ge \delta n \big \} \le n^{-\epsilon n} \end{equation*}$$

and

$$\begin{equation*} {\mathbb{P}}^u_n\big \{\sigma :\nobreakspace \#\{v \in [n]:\nobreakspace v \text{ represents a $(\sigma ,w)$-simple degenerate cycle} \}\ge \delta n \big \} \le n^{-\epsilon n}. \end{equation*}$$

(This is the second reduction).

Two vertices $v,v' \in V_n$ represent vertex-disjoint $(\sigma ,w)$-cycles if $p(v,\sigma )=(e_1$, …, $e_l), p(v',\sigma )=(e'_1$, …, $e'_l)$ and $e_i \cap e'_j =\emptyset$ for all $i,j$.

Let $G_n(\delta ,w)$ be the set of all $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ such that there exists a subset $S \subset [n]$ satisfying

(1)

$|S| \ge \delta n$,

(2)

every $v \in S$ represents a $(\sigma ,w)$-simple cycle,

(3)

the cycles $p(v,\sigma )$ for $v \in S$ are pairwise vertex-disjoint.

If $v$ represents a simple $(\sigma ,w)$-cycle then there are at most $(kl)^2$ vertices $v'$ such that $v'$ also represents a simple $(\sigma ,w)$-cycle but the two cycles are not vertex-disjoint. Since this bound does not depend on $n$, it suffices to prove there exist $\epsilon >0$ and $N_0$ such that

$$\begin{equation*} {\mathbb{P}}^u_n(G_n(\delta ,w)) \le n^{-\epsilon n} \end{equation*}$$

for all $n \ge N_0$. (This is the third reduction. The argument is similar for simple degenerate cycles).

Let $m=\lceil \delta n \rceil$ and $v_1$, …, $v_m$ be distinct vertices in $[n]=V_n$. For $1\le i \le m$, let $F_i$ be the set of all $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ such that for all $1\le j \le i$

(1)

$v_j$ represents a $(\sigma ,w)$-simple cycle,

(2)

the cycles $p(v_1,\sigma )$, …, $p(v_i,\sigma )$ are pairwise vertex-disjoint.

By summing over all subsets of size $m$, we obtain

$$\begin{equation*} {\mathbb{P}}^u_n(G_n(\delta ,w)) \le {n \choose m } {\mathbb{P}}^u_n(F_m). \end{equation*}$$

Since ${n \choose m} \approx e^{H(\delta ,1-\delta )n}$ grows at most exponentially, it suffices to show there exist $\epsilon >0$ and $N_0$ such that ${\mathbb{P}}^u_n(F_m) \le n^{-\epsilon n}$ for all $n \ge N_0$. (This is the fourth reduction. The argument is similar for simple degenerate cycles).

Set $F_0= {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$. By the chain rule

$$\begin{equation*} {\mathbb{P}}^u_n(F_m) = \prod _{i=0}^{m-1} {\mathbb{P}}^u_n(F_{i+1} | F_i ). \end{equation*}$$

In order to estimate ${\mathbb{P}}^u_n(F_{i+1} | F_i )$, $F_i$ can be expressed a disjoint union over the cycles involved in its definition. To be precise, define an equivalence relation ${\mathcal{R}}_i$ on $F_i$ by: $\sigma ,\sigma '$ are ${\mathcal{R}}_i$-equivalent if for every $1\le j \le i$, $1\le q \le l$ and $r>0$

$$\begin{equation*} \sigma (s_{i_q}^rw_q)v_j = \sigma '(s_{i_q}^rw_q)v_j. \end{equation*}$$

In other words, $\sigma ,\sigma '$ are ${\mathcal{R}}_i$-equivalent if they define the same paths according to all vertices up to $v_i$ (so $p(v_j,\sigma )=p(v_j,\sigma ')$) and their restrictions to every edge in these paths agree. Of course, $F_i$ is the disjoint union of the ${\mathcal{R}}_i$-classes. Note that ${\mathcal{R}}_0$ is trivial (everything is equivalent).

In general, if $A$, $B_1$, …, $B_m$ are measurable sets and the $B_i$’s are pairwise disjoint then ${\mathbb{P}}(A| \cup _i B_i)$ is a convex combination of ${\mathbb{P}}(A | B_i)$ (for any probability measure ${\mathbb{P}}$). Therefore, ${\mathbb{P}}^u_n(F_{i+1} | F_i)$ is a convex combination of probabilities of the form ${\mathbb{P}}^u_n(F_{i+1} | B_i)$ where $B_i$ is an ${\mathcal{R}}_i$-class.

Now fix an ${\mathcal{R}}_i$-class $B_i$ (for some $i$ with $0\le i < m$). Let $K$ be the set of all vertices covered by the cycles defining $B_i$. To be precise, this means $K$ is the set of all $u \in [n]=V_n$ such that there exists an edge $e$ with $u\in e$ such that $e$ is contained in a path $p(v_j,\sigma )$ with $1\le j \le i$ and $\sigma \in B_i$. Since each path covers at most $kl$ vertices, $|K| \le ikl$.

If $l > 1$ (the case $l=1$ is similar), fix subsets $e_1$, …, $e_{l-1} \subset [n]$ of size $k$. Conditioned on $B_i$ and the event that the first $(l-1)$ edges of $p(v_{i+1},\sigma )$ are $e_1$, …, $e_{l-1}$, the ${\mathbb{P}}^u_n$-probability that $v_{i+1}$ represents a simple $(\sigma ,w)$-cycle vertex-disjoint from $K$ is bounded by the probability that a uniformly random $k-1$-element subset of

$$\begin{equation*} [n] \setminus \left(\bigcup _{2\le j \le l-1} e_j \cup K\right) \end{equation*}$$

contains $v_{i+1}$. Since

$$\begin{equation*} \left|\bigcup _{2\le j \le l-1} e_j \cup K\right| \le (i+1)kl \le m kl = kl \lceil \delta n \rceil , \end{equation*}$$

this probability is bounded by $C/n$ where $C=C(w,d,k,\delta )$ is a constant not depending on $n$ or the choice of $B_i$. It follows that ${\mathbb{P}}^u_n(F_{i+1}|F_i) \le C/n$ for all $0\le i \le m-1$ and therefore

$$\begin{equation*} {\mathbb{P}}^u_n(F_m) \le (C/n)^m \le (C/n)^{\delta n}. \end{equation*}$$

This implies the lemma (the argument is similar for simple degenerate cycles).

■

Proof of Theorem 1.1 from Lemma 1.2.

Choose $d,k,\eta _0, \eta _1, \eta$ according to the hypotheses of Lemma 1.2 so that $\eta \in [\eta _0,\eta _1]$, $k\ge k_0$ and all of the conclusions to Lemma 1.2 hold. Construct $\Gamma {\curvearrowright } X$ according to §1.3. We will always take $n \in 2{\mathbb{Z}} \cap k{\mathbb{Z}}$. We will first show the existence of a sofic approximation $\Sigma _1 = \{\sigma _n\}$ to $\Gamma$ such that

$$\begin{equation*} \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log Z(\epsilon ;\sigma _n) = f(d,k). \end{equation*}$$

Then by Lemma 2.1, we will have $h_{\Sigma _1}(\Gamma {\curvearrowright } X) = f(d,k) > 0$.

Observe that Lemma 1.21 implies the following: for every $\beta >0$ there exists $\epsilon (\beta )>0$ (with $\epsilon$ decreasing as $\beta$ decreases), $N$, and $\xi (\beta ,\epsilon ,N) > 0$ such that for $n > N$, ${\mathbb{P}}^u_n(n^{-1} \log (Z(\epsilon ;\sigma _n)) - f(d,k)\geq \beta ) < e^{-\xi n}$. In other words, the number of $\epsilon$-proper colorings can only exponentially exceed $f(d,k)$ with exponentially small probability. This is because the negation of the above would imply that $\inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{u}[ Z(\epsilon ;\sigma )] > f(d,k)$, contradicting 1. Let $F_{n,\beta ,\epsilon }$ be the event that $n^{-1}\log [Z(\epsilon ;\sigma _n)] - f(d,k)\geq \beta$.

Let $H_{n,\beta }$ be the event that $|n^{-1}\log Z(\sigma _n) - f(d,k)|<\beta$. Lemma 1.23 implies ${\mathbb{P}}_n^{u}(H_{n,\beta })$ decays at most subexponentially in $n$. Precisely, for any $c>0$ there exists $N=N(c,\beta )$ such that $n>N$ implies ${\mathbb{P}}_n^{u}(H_{n,\beta }) > e^{-cn}$.

Let $I_{n,\beta ,\epsilon }$ be the event that $|n^{-1}\log Z(\epsilon ;\sigma _n) - f(d,k)| < \beta$. Notice that since $Z(\epsilon ;\sigma _n) \geq Z(\sigma _n)$ for any $\epsilon$, $F_{n,\beta ,\epsilon }^c \cap H_{n,\beta } \subset I_{n,\beta ,\epsilon }$.

Consider a decreasing sequence $\beta _m \to 0$, and $\epsilon _m$ and $\xi _m$ depending on $\beta _m$ as discussed above. Since ${\mathbb{P}}_n^{u}(H_{n,\beta })$ is decaying only subexponentially, we can choose an increasing sequence $K_m$ satisfying $K_m \geq \max _{1 \leq j \leq m} N_j$, and for each $m$, ${\mathbb{P}}_n^{u}(H_{n,\beta _m}) > 2\sum _{i=1}^m e^{-\xi _in}$ for all $n > K_m$. Now it follows that $n>K_m$ implies ${\mathbb{P}}^u_n(\cap _{j=1}^m F^c_{n,\beta _j,\epsilon _j} \cap H_{n,\beta _j}) \geq {\mathbb{P}}_n^{u}(H_{n,\beta _m}) - \sum _{i=1}^m e^{-\xi _in} \geq e^{-\xi _1 n}$. By the observation in the preceding paragraph, ${\mathbb{P}}^u_n(\cap _{j=1}^m I_{n,\beta _j,\epsilon _j}) \geq e^{-\xi _1 n}$.

Given $\delta >0$ and $D \subset \Gamma$ finite, let $J_{D,\delta ,n}$ be the event that $\sigma _n$ is $(D,\delta )$-sofic. Let $\delta _m \to 0$ be a decreasing sequence and $D_m \subset \Gamma$ be an increasing sequence of finite subsets of $\Gamma$.

Lemma 3.1 implies that ${\mathbb{P}}^u_n(J_{D,\delta ,n}^c)$ decays super-exponentially in $n$ for any $D$ and $\delta$, so there exists an increasing sequence $N_m$ such that for $n>N_m$, ${\mathbb{P}}^u_n(\cap _{j=1}^m I_{n,\beta _j,\epsilon _j} \cap J_{D_m,\delta _m,n}) \geq 0.5e^{-\xi _1 n}$. It follows that we can choose a deterministic sofic approximation sequence $\Sigma _1 = \{\sigma _n\}$ such that

$$\begin{equation*} \inf _{\epsilon >0} \limsup _{n\to \infty } n^{-1}\log Z(\epsilon ;\sigma _n) = f(d,k). \end{equation*}$$

We next show the existence of $\Sigma _2$. Equation 2 of Lemma 1.2 implies the existence of a number $f_p$ with

$$\begin{equation*} f(d,k) < f_p < \liminf _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )]. \end{equation*}$$

Since $Z(\sigma ) \le 2^n$ for every $\sigma$, there exist constants $c,N_0>0$ such that

$$\begin{equation} {\mathbb{P}}^p_n\{\sigma :\nobreakspace Z(\sigma ) \ge \exp (n f_p)\} \ge \exp ( -cn) {\tag{4}} \end{equation}$$

for all $n \ge N_0$.

Now let $\delta >0$ and $D \subset \Gamma$ be finite. Then there exists $N_2$ such that if $n>N_2$ and $\sigma _{n}$ is chosen at random with law ${\mathbb{P}}^p_{n}$, then with positive probability,

(1)

$\sigma _{n}$ is $(D,\delta )$-sofic,

(2)

$n^{-1} \log Z(\sigma _n) \ge f_p$.

This is implied by Lemma 3.1 and equation 4. So there exists a sofic approximation $\Sigma _2=\{\sigma '_n\}$ to $\Gamma$ such that

$$\begin{equation*} \limsup _{n\to \infty } n^{-1}\log Z(\sigma '_n) \ge f_p. \end{equation*}$$

Since $Z(\sigma '_n) \!\le \! Z(\beta ; \sigma '_n)$, Lemma 2.1 implies $h_{\Sigma _2}(\Gamma {\curvearrowright } X) \!\ge \! f_p \!>\! f(d,k) \!=\! h_{\Sigma _1}(\Gamma {\curvearrowright } X)$.

■

4. The first moment

To simplify notation, we assume throughout the paper that $n \in 2{\mathbb{Z}} \cap k{\mathbb{Z}}$ without further mention. This section proves 1 of Lemma 1.2. The proof is in two parts. Part 1, in Section 4.1, establishes:

Theorem 4.1.

$$\begin{equation*} \lim _{\epsilon \searrow 0} \limsup _{n\to \infty } (1/n) \log {\mathbb{E}}^u_n[Z(\epsilon ;\sigma )] = \limsup _{n\to \infty } (1/n) \log {\mathbb{E}}^u_n[Z(\sigma )]. \end{equation*}$$

Part 2 has to do with equitable colorings, where a 2-coloring $\chi :[n] \to \{0,1\}$ is equitable if

$$\begin{equation*} |\chi ^{-1}(0)| = |\chi ^{-1}(1)| = n/2. \end{equation*}$$

Let $Z_e(\sigma )$ be the number of proper equitable colorings of $G_\sigma$. Section 4.2 establishes

Theorem 4.2.

$$\begin{equation*} \lim _{n\to \infty } \frac{1}{n} \log {\mathbb{E}}^u_n[ Z(\sigma ) ] = \lim _{n\to \infty } \frac{1}{n} \log {\mathbb{E}}^u_n[ Z_e(\sigma ) ]. \end{equation*}$$

Moreover,

$$\begin{equation*} \frac{1}{n} \log {\mathbb{E}}^u_n[ Z_e(\sigma ) ] = f(d,k) +O(n^{-1}\log (n)), \end{equation*}$$

where $f(d,k)= \log (2) + \frac{d}{k} \log (1-2^{1-k})$.

Combined, Theorems 4.1 and 4.2 imply 1 of Lemma 1.2.

Remark 5.

If $r\coloneq (d/k)$ then the formula for $\lim _{n\to \infty } \frac{1}{n} \log {\mathbb{E}}^u_n[ Z(\sigma ) ]$ above is the same as the formula found in 678 for the exponential growth rate of the number of proper 2-colorings of $H_k(n,m)$.

Remark 6.

When we write an error term, such as $O(n^{-1}\log (n))$, we always assume that $n \ge 2$ and the implicit constant is allowed to depend on $k$ or $d$.

4.1. Almost proper 2-colorings

For $0 < x \le 1$, let $\eta (x)=-x\log (x)$. Also let $\eta (0)=0$. If ${\vec{T}}=(T_i)_{i\in I}$ is a collection of numbers with $0 \le T_i\le 1$, then let

$$\begin{equation*} H({\vec{T}}) \coloneq \sum _{i \in I} \eta (T_i) \end{equation*}$$

be the Shannon entropy of ${\vec{T}}$.

Definition 3.

A $k$-partition of $[n]$ is an unordered partition of $[n]$ into sets of size $k$. Of course, such a partition exists if and only if $n/k \in {\mathbb{N}}$ in which case there are

$$\begin{equation} \frac{n!}{k!^{n/k} (n/k)!} {\tag{5}} \end{equation}$$

such partitions. By Stirling’s formula,

$$\begin{align} & \frac{1}{n} \log (\# \{\text{$k$-partitions} \}) {\tag{6}}\\ & \qquad = (1-1/k)(\log (n) -1) -(1/k)\log (k-1)! + O(n^{-1}\log (n)). \end{align}$$

Definition 4.

The orbit-partition of a permutation $\rho \in \operatorname {Sym}(n)$ is the partition of $[n]$ into orbits of $\rho$. Fix a $k$-partition $\pi$. Then the number of permutations $\rho$ whose orbit partition is $\pi$ equals $(k-1)!^{n/k}$.

Given $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$, define the $d$-tuple $(\pi ^\sigma _1$, …, $\pi ^\sigma _d)$ of $k$-partitions by: $\pi ^\sigma _i$ is the orbit-partition of $\sigma (s_i)$. Fix a $d$-tuple of $k$-partitions $(\pi _1$, …, $\pi _d)$. Then the number of uniform homomorphisms $\sigma$ such that $\pi ^\sigma _i = \pi _i$ for all $i$ is $[(k-1)!^{n/k}]^d$. Combined with 5, this shows the number of uniform homomorphisms into $\operatorname {Sym}(n)$ is

$$\begin{equation*} \left[\frac{n!(k-1)!^{n/k}}{k!^{n/k} (n/k)!} \right]^d. \end{equation*}$$

By Stirling’s formula,

$$\begin{equation} \frac{1}{n} \log \# {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))= d(1-1/k)(\log n -1) + O(n^{-1}\log (n)). {\tag{7}} \end{equation}$$

Definition 5.

Let $\pi$ be a $k$-partition, $\chi :[n] \to \{0,1\}$ a 2-coloring and ${\vec{t}} = (t_j)_{j=0}^k \in [0,1]^{k+1}$ a vector with $\sum _j t_j = 1/k$. The pair $(\pi ,\chi )$ has type ${\vec{t}}$ if for all $j$,

$$\begin{equation*} \#\left\{e\in \pi :\nobreakspace |e \cap \chi ^{-1}(1)| = j\right\} = n t_j. \end{equation*}$$

Lemma 4.3.

Let $\vec{t}=(t_0$, $t_1$, …, $t_k) \in [0,1]^{k+1}$ be such that $\sum _j t_j=1/k$ and $nt_j \in {\mathbb{Z}}$. Let $p=\sum _j j t_j$. Let $\chi : [n] \to \{0,1\}$ be a map such that $|\chi ^{-1}(1)|=pn$. Let $f( \vec{t})$ be the number of $k$-partitions $\pi$ of $[n]$ such that $(\pi ,\chi )$ has type ${\vec{t}}$. Then

$$\begin{multline*} (1/n)\log f(\vec{t}) = (1-1/k)(\log (n)-1) -H(p,1-p)+H(\vec{t})\\ -\sum _{j=0}^k t_j \log (j!(k-j)!) + O(n^{-1}\log (n)). \end{multline*}$$

Proof.

The following algorithm constructs all such partitions with no duplications:

Step 1.

Choose an unordered partition of the set $\chi ^{-1}(1)$ into $t_j n$ sets of size $j$ ($j=0$, …, $k$).

Step 2.

Choose an unordered partition of the set $\chi ^{-1}(0)$ into $t_j n$ sets of size $k-j$ ($j=0$, …, $k$).

Step 3.

Choose a bijection between the collection of subsets of size $j$ constructed in part 1 with the collection of subsets of size $k-j$ constructed in part 2.

Step 4.

The partition consists of all sets of the form $\alpha \cup \beta$ where $\alpha \subset \chi ^{-1}(1)$ is a set of size $j$ constructed in Step 1 and $\beta \subset \chi ^{-1}(0)$ is a set of size $(k-j)$ constructed in Step 2 that it is paired with under Step 3.

The number of choices in Step 1 is $\frac{(pn)!}{ \prod _{j=1}^k (j)!^{t_jn}(t_jn)!}$. The number of choices in Step 2 is $\frac{((1-p)n)!}{ \prod _{j=0}^{k-1} (k-j)!^{t_jn}(t_jn)!}$. The number of choices in Step 3 is $\prod _{j=1}^{k-1} (t_jn)!$. So

$$\begin{equation} f(\vec{t}) = \frac{(pn)!((1-p)n)!}{ \prod _{j=0}^{k} j!^{t_jn}(k-j)!^{t_jn} (t_jn)!}. {\tag{8}} \end{equation}$$

The lemma follows from this and Stirling’s formula.

■

Let ${\mathscr{M}}$ be the set of all matrices ${\vec{T}}=(T_{ij})_{1\le i \le d, 0\le j \le k}$ such that

(1)

$T_{ij} \ge 0$ for all $i,j$,

(2)

$\sum _{j=0}^k T_{ij}=1/k$ for all $i$,

(3)

there exists a number, denoted $p({\vec{T}})$, such that $p({\vec{T}}) = \sum _{j=0}^k j T_{ij}$ for all $i$.

Let ${\mathscr{M}}_n$ be the set of all ${\vec{T}} \in {\mathscr{M}}$ such that $n{\vec{T}}$ is integer-valued.

Lemma 4.4.

Let $A$ be an integer-valued $q\times p$ matrix (for some $p,q \in {\mathbb{N}}$), $b \in {\mathbb{R}}^q$ and ${\mathscr{K}} \subset {\mathbb{R}}^p$ the set of all $x\in {\mathbb{R}}^p$ such that $Ax = b$ and $x_i \ge 0$ for all $i$. For $n\in {\mathbb{N}}$, let ${\mathscr{K}}_n$ be the set of all $x \in {\mathscr{K}}$ such that $nx$ is integer-valued.

Assume ${\mathscr{K}}$ is compact and there exists $x \in {\mathscr{K}}$ with $x_i>0$ for all $i$. Then there is a constant $C>0$ such that if ${\mathscr{K}}_n$ is non-empty then it is $C/n$-dense in ${\mathscr{K}}$ in the following sense. For any $x \in {\mathscr{K}}$ there exists $x' \in {\mathscr{K}}_n$ such that $\|x - x'\|_\infty < C/n$. Moreover, the constant $C$ can be chosen to depend continuously on the vector $b \in {\mathbb{R}}^q$.

Proof.

To begin, we will define several constants which will enable us to choose $C>0$. Because $A$ is integer-valued, its kernel, denoted $\ker (A) \subset {\mathbb{R}}^p$, is such that $\ker (A) \cap {\mathbb{Z}}^{p}$ has rank equal to the dimension of $\ker (A)$. Therefore, $\ker (A)\cap {\mathbb{Z}}^{p}$ is cocompact in $\ker (A)$. So there is a constant $C_1>0$ such that for any $z \in \ker (A)$ there is an element $z' \in \ker (A) \cap {\mathbb{Z}}^{p}$ with $\|z - z'\|_\infty < C_1$.

By hypothesis, there is a constant $C_2>0$ and an element $y \in {\mathscr{K}}$ such that $y_i > C_2$ for all $i$. Because ${\mathscr{K}}$ is compact there is another constant $C_3>0$ such that $\|x-y\|_\infty <C_3$ for all $x\in {\mathscr{K}}$. Let $C=\frac{C_1C_3}{C_2} + C_1$. Now let $x \in {\mathscr{K}}$ be arbitrary and suppose ${\mathscr{K}}_n$ is non-empty. We will show there exists $x'' \in {\mathscr{K}}_n$ such that $\|x-x''\|_\infty \le C/n$.

Let

$$\begin{equation*} x'=\left(1-\frac{C_1}{C_2n}\right)x + \frac{C_1}{C_2n}y. \end{equation*}$$

Then $x'_i \ge (C_1/C_2n)y_i > C_1/n$ for all $i$. Also $\|x-x'\|_\infty = (C_1/C_2n)\|x-y\|_\infty < \frac{C_1C_3}{C_2n}$.

Because ${\mathscr{K}}_n$ is non-empty, there exists $x_n \in {\mathscr{K}}_n$. By linearity, ${\mathscr{K}}$ is the intersection of the hyperplane $x_n + \ker (A)$ with the positive orthant. Thus we can write $x'=x_n+(1/n)z' + z''$ where $z' \in \ker (A) \cap {\mathbb{Z}}^{p}$ and $z'' \in \ker (A)$ satisfies $\|z''\|_\infty < C_1/n$. Let $x''=x_n + (1/n)z'$. Note $\|x''-x'\|_\infty =\|z''\|_\infty < C_1/n$. Since $x'_{i}>C_1/n$ this implies $x''_{i}>0$ for all $i$. It is now straightforward to check that $x'' \in {\mathscr{K}}_n$. By the triangle inequality

$$\begin{equation*} \|x - x''\|_\infty \le \|x - x'\|_\infty + \|x' - x''\|_\infty < \frac{C_1C_3}{C_2n} + C_1/n = C/n. \end{equation*}$$

Because $x$ and $n$ are arbitrary, this implies the Lemma with $C=\frac{C_1C_3}{C_2} + C_1$. Moreover $C_1$ does not depend on the vector $b$; while $C_2,C_3$ can be chosen to depend continuously on $b$.

■

Lemma 4.5.

Given a matrix ${\vec{T}} \in {\mathscr{M}}$ define

$$\begin{equation*} F({\vec{T}})\coloneq H({\vec{T}}) + (1-d)H(p,1-p) - (d/k)\log k +\sum _{i=1}^d \sum _{j=0}^k T_{ij} \log {k \choose j}, \end{equation*}$$

where $p=p({\vec{T}})$. Then for any $\epsilon \ge 0$,

$$\begin{align*} & (1/n) \log {\mathbb{E}}^u_n[Z(\epsilon ;\sigma )] \\ & \qquad = \sup \left\{ F({\vec{T}}):\nobreakspace {\vec{T}} \in {\mathscr{M}}_n \text{ and } \sum _{i=1}^d \sum _{j=0,k} T_{ij} \le \epsilon \right\} + O(n^{-1}\log (n)), \end{align*}$$

where the constant implicit in the error term does not depend on $\epsilon$.

Proof.

Given $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ and $1\le i \le d$, let $\pi ^\sigma _i$ be the orbit-partition of $\sigma (s_i)$. For ${\vec{T}}$ as above, let $Z_\sigma ({\vec{T}})$ be the number of $\epsilon$-proper colorings $\chi :[n] \to \{0,1\}$ such that $(\pi ^\sigma _i,\chi )$ has type ${\vec{T}}_i = (T_{i,0}$, …, $T_{i,k})$. It suffices to show that

$$\begin{equation*} (1/n) \log {\mathbb{E}}^u_n[Z_\sigma ({\vec{T}})] = F({\vec{T}}) + O(n^{-1}\log (n)) \end{equation*}$$

for all $n\ge 2$ such that ${\vec{T}} \in {\mathscr{M}}_n$. This is because the size of ${\mathscr{M}}_n$ is a polynomial (depending on $k,d$) in $n$ so the supremum above determines the exponential growth rate of ${\mathbb{E}}^u_n[Z(\epsilon ;\sigma )]$.

To prove this, fix a ${\vec{T}}$ as above and let $n$ be such that $n {\vec{T}}$ is integer-valued. Fix a coloring $\chi :[n] \to \{0,1\}$ such that $|\chi ^{-1}(1)|=pn$. By symmetry,

$$\begin{equation*} {\mathbb{E}}^u_n[Z_\sigma ({\vec{T}})] = {n \choose pn} {\mathbb{P}}^u_n[ (\pi ^\sigma _i,\chi ) \text{ has type } {\vec{T}}_i\nobreakspace \forall i ]. \end{equation*}$$

The events $\{(\pi ^\sigma _i,\chi ) \text{ has type } {\vec{T}}_i\}_{i=1}^d$ are jointly independent. So

$$\begin{equation} {\mathbb{E}}^u_n[Z_\sigma ({\vec{T}})] = {n \choose pn} \prod _{i=1}^d {\mathbb{P}}^u_n[ (\pi ^\sigma _i,\chi ) \text{ has type } {\vec{T}}_i ]. {\tag{9}} \end{equation}$$

By symmetry, ${\mathbb{P}}^u_n[ (\pi ^\sigma _i,\chi ) \text{ has type } {\vec{T}}_i ]$ is the number of $k$-partitions $\pi$ such that $(\pi ,\chi )$ has type ${\vec{T}}_i$ divided by the number of $k$-partitions. By Lemma 4.3 and 6,

$$\begin{align*} & \frac{1}{n} \log {\mathbb{P}}^u_n[ (\pi ^\sigma _i,\chi ) \text{ has type } {\vec{T}}_i ] \\ & \qquad = -H(p,1-p)+H(\vec{T}_i)\\ & \qquad \quad -\sum _{j=0}^k T_{ij} \log (j!(k-j)!) +(1/k) \log (k-1)! + O(n^{-1}\log (n)). \end{align*}$$

Combine this with 9 to obtain

$$\begin{align*} &(1/n) \log {\mathbb{E}}^u_n[Z_\sigma ({\vec{T}})]\\ & \qquad = (1-d) H(p,1-p) +H(\vec{T})\\ & \qquad \quad - \sum _{i=1}^d \sum _{j=0}^k T_{ij}\log (j!(k-j)!) +(d/k) \log (k-1)! + O(n^{-1}\log (n)). \end{align*}$$

This simplifies to the formula for $F({\vec{T}})$ using the assumption that $\sum _{j=0}^k T_{ij}=1/k$ for all $i$.

■

Proof of Theorem 4.1.

By Lemma 4.4 applied to ${\mathscr{M}}$, continuity of $F$ and compactness of ${\mathscr{M}}$,

$$\begin{align*} &\lim _{n\to \infty } \sup \left\{ F({\vec{T}}):\nobreakspace {\vec{T}} \in {\mathscr{M}}_n \text{ and } \sum _{i=1}^d \sum _{j=0,k} T_{ij} \le \epsilon \right\} \\ &\qquad =\sup \left\{ F({\vec{T}}):\nobreakspace {\vec{T}} \in {\mathscr{M}} \text{ and } \sum _{i=1}^d \sum _{j=0,k} T_{ij} \le \epsilon \right\}. \end{align*}$$

Theorem 4.1 now follows from Lemma 4.5 by continuity of $F$ and compactness of ${\mathscr{M}}$.

■

4.2. Equitable colorings

Proof of Theorem 4.2.

Let ${\mathscr{M}}_0$ be the set of all ${\vec{T}} \in {\mathscr{M}}$ such that $T_{ij}=0$ whenever $j \in \{0,k\}$. By Lemma 4.5, it suffices to show that $F$ admits a unique global maximum on ${\mathscr{M}}_0$ and moreover if ${\vec{T}}\in {\mathscr{M}}_0$ is the global maximum then $p({\vec{T}})=1/2$ and $F({\vec{T}})=f(d,k)$.

The function $F$ is symmetric in the index $i$. To exploit this, let ${\mathscr{M}}'$ be the set of all vectors ${\vec{t}}=(t_j)_{j=1}^{k-1}$ such that $t_{j} \ge 0$ for all $j$ and $\sum _{j=1}^{k-1} t_{j}=1/k$. Let

$$\begin{align*} p({\vec{t}}) &= \sum _{j=1}^{k-1} j t_{j} \\ F({\vec{t}}) &= dH({\vec{t}}) + (1-d)H(p,1-p) - (d/k)\log k + d \sum _{j=1}^{k-1} t_{j} \log {k \choose j}. \end{align*}$$

Note that $F({\vec{t}})=F({\vec{T}})$ if ${\vec{T}}$ is defined by ${\vec{T}}_{ij}={\vec{t}}_j$ for all $i,j$. Moreover, since Shannon entropy is strictly concave, for any ${\vec{T}} \in {\mathscr{M}}_0$, if ${\vec{t}}$ is defined to be the average: ${\vec{t}}_j = d^{-1} \sum _{i=1}^d {\vec{T}}_{ij}$ then $F({\vec{t}}) \ge F({\vec{T}})$ with equality if and only if ${\vec{t}}_j = {\vec{T}}_{ij}$ for all $i,j$. So it suffices to show that $F$ admits a unique global maximum on ${\mathscr{M}}'$ and moreover if ${\vec{t}} \in {\mathscr{M}}'$ is the global maximum then $p({\vec{t}})=1/2$ and $F({\vec{t}})=f(d,k)$.

Because $\frac{\partial H({\vec{t}})}{\partial t_j} = -[\log (t_j)+1]$, $\frac{\partial p}{\partial t_j} = j$, and $\frac{\partial H(p,1-p)}{\partial t_j} = j \log \left( \frac{1-p}{p}\right)$,

$$\begin{equation*} \frac{\partial F}{\partial t_j}= -d[\log (t_j)+1] + (1-d)j \log \left( \frac{1-p}{p}\right) + d \log {k \choose j}. \end{equation*}$$

Since this is positive infinity whenever $t_j = 0$, it follows that every maximum of $F$ occurs in the interior of ${\mathscr{M}}'$. The method of Lagrange multipliers implies that, at a critical point, there exists $\lambda \in {\mathbb{R}}$ such that

$$\begin{equation*} \nabla F = \lambda \nabla \left( {\vec{t}} \mapsto \sum _j t_j\right) = (\lambda ,\lambda ,\ldots ,\lambda ). \end{equation*}$$

So at a critical point,

$$\begin{equation*} \frac{\partial F}{\partial t_j} = -d[\log (t_j)+1] + (1-d)j \log \left( \frac{1-p}{p}\right) + d \log {k \choose j} = \lambda . \end{equation*}$$

Solve for $t_j$ to obtain

$$\begin{equation*} t_j = \exp (-\lambda /d - 1){k \choose j} \left( \frac{1-p}{p}\right)^{j(1-d)/d}. \end{equation*}$$

Note

$$\begin{equation*} 1 = k \sum _{j=1}^{k-1} t_j \end{equation*}$$

$$\begin{equation*} 1 = 1/p \sum _{j=1}^{k-1} jt_j \end{equation*}$$ implies

$$\begin{equation*} 0 =\sum _{j=1}^{k-1} (k-j/p) t_j =\sum _{j=1}^{k-1} (pk-j){k \choose j} \left( \frac{1-p}{p}\right)^{j(1-d)/d}. \end{equation*}$$

So define

$$\begin{equation*} g(x)\coloneq \sum _{j=1}^{k-1} (kx-j){k \choose j} \left( \frac{1-x}{x}\right)^{j(1-d)/d}. \end{equation*}$$

It follows from the above that $g(p({\vec{t}}))=0$ whenever ${\vec{t}}$ is a critical point.

We claim that $g(x)=0$ if and only if $x =1/2$ (for $x \in (0,1)$). The change of variables $j\mapsto k-j$ in the formula for $g$ shows that $g(1-x)=-\left( \frac{x}{1-x}\right)^{k(1-d)/d}g(x)$. So it is enough to prove that $g(x)<0$ for $x \in (0,1/2)$.

To obtain a simpler formula for $g$, set $y(x) = \left( \frac{1-x}{x}\right)^{(1-d)/d}$. The binomial formula implies

$$\begin{align*} g(x)&=\sum _{j=1}^{k-1} (kx-j){k \choose j} y^j \\ &= kx[ (1+y)^k - 1 - y^k] - ky[ (1+y)^{k-1}-y^{k-1}] \\ &= k[ (x(1+y) - y)(1+y)^{k-1} -x + (-x+1)y^k]. \end{align*}$$

Because $0<x<1/2$, $y > \left( \frac{x}{1-x}\right)$ which implies that the middle coefficient $(x(1+y) - y) = x - y(1-x) < 0$. So

$$\begin{equation*} g(x)/k < (1-x)y^k - x<0, \end{equation*}$$

where the last inequality holds because

$$\begin{equation*} y^k=\left( \frac{x}{1-x}\right)^{k(d-1)/d} < \frac{x}{1-x} \end{equation*}$$

assuming $k(d-1)/d >1$. This proves the claim.

So if ${\vec{t}}$ is a critical point then $p({\vec{t}})=1/2$. Put this into the equation above for $t_j$ to obtain

$$\begin{equation*} t_j = C {k \choose j}, \end{equation*}$$

where $C=\exp (-\lambda /d - 1)$. Because

$$\begin{equation*} 1/k = \sum _{j=1}^{k-1} t_j = C \sum _{j=1}^{k-1} {k \choose j} = C(2^k - 2), \end{equation*}$$

it must be that

$$\begin{equation} t_j = \frac{1}{k(2^k-2)}{k \choose j}. {\tag{10}} \end{equation}$$

The formula $F({\vec{t}})=f(d,k)$ now follows from a straightforward computation.

■

5. The second moment

This section gives an estimate on the expected number of proper colorings at a given Hamming distance from the planted coloring. This computation yields 2 of Lemma 1.2 as a corollary. It also reduces the proof of 3 to obtaining an estimate on the typical number of proper colorings near the planted coloring.

Before stating the main result, it seems worthwhile to review notation. Fix $n>0$ with $n \in 2{\mathbb{Z}} \cap k{\mathbb{Z}}$. Fix an equitable 2-coloring $\chi :[n] \to \{0,1\}$. This is the planted coloring. The planted model ${\mathbb{P}}^p_n$ is the uniform probability measure on the set ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ of all uniform homomorphisms $\sigma$ such that $\chi$ is $\sigma$-proper. Also let $Z_e:{\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n)) \to {\mathbb{N}}$ be the number of equitable proper 2-colorings. For $\delta \in [0,1]$, let $Z_\chi (\delta ;\cdot ): {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n)) \to {\mathbb{N}}$ be the number of equitable proper 2-colorings ${\widetilde{\chi }}$ such that $|d_n(\chi ,{\widetilde{\chi }}) -\delta |<1/2n$ where $d_n$ is the normalized Hamming distance defined by

$$\begin{equation*} d_n(\chi ,{\widetilde{\chi }}) = n^{-1} \#\{ v\in [n]:\nobreakspace \chi (v) \ne {\widetilde{\chi }}(v)\}. \end{equation*}$$

We will also write $Z_\chi (\delta ;\sigma )=Z_\chi (\delta )=Z(\delta )$ when $\chi$ and/or $\sigma$ are understood.

The main result of this section is:

Theorem 5.1.

With notation as above, for any $0\le \delta \le 1$ such that $\delta n/2$ is an integer,

$$\begin{equation*} \frac{1}{n} \log {\mathbb{E}}^p_n[Z(\delta )] = \psi _0(\delta ) + O_\delta (n^{-1}) + O(n^{-1}\log (n)) \end{equation*}$$

(for $n\ge 2$) where

$$\begin{equation*} \psi _0(\delta ) = (1-d)H(\delta ,1-\delta ) + dH_0(\delta ,1-\delta ) + \frac{d}{k} \log \left( 1 - \frac{1-\delta _0^k -(1-\delta _0)^k }{2^{k-1}-1} \right), \end{equation*}$$

$\delta _0$ is defined to be the unique solution to

$$\begin{equation*} \delta _0 \frac{ 1-2^{2-k} + (\delta _0/2)^{k-1} }{ 1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k } = \delta \end{equation*}$$

and

$$\begin{align*} H(\delta ,1-\delta ) &\coloneq -\delta \log \delta - (1-\delta )\log (1-\delta ),\\ H_0(\delta ,1-\delta ) &\coloneq -\delta \log \delta _0 - (1-\delta )\log (1-\delta _0). \end{align*}$$

Moreover, the constant implicit in the error term $O(n^{-1}\log (n))$ may depend on $k$ but not on $\delta$. The constant implicit in the $O_\delta (n^{-1})$ term depends continuously on $\delta$ for $\delta \in (0,1/2]$.

Remark 7.

If $\delta _0=\delta$ then $\delta =1/2$. In the general case, $\delta _0 = \delta +O(2^{-k})$. Theorem 5.1 parallels similar results in 67 for the random hyper-graph $H_k(n,m)$. This is explained in more detail in the next subsection.

The strategy behind the proof of Theorem 5.1 is as follows. We need to estimate the expected number of equitable colorings at distance $\delta$ from the planted coloring. By symmetry, it suffices to fix another coloring ${\widetilde{\chi }}$ that is at distance $\delta$ from the planted coloring and count the number of uniform homomorphisms $\sigma$ such that both $\chi$ and ${\widetilde{\chi }}$ are proper with respect to $G_\sigma$. This can be handled one generator at a time. Moreover, only the orbit-partition induced by a generator is used in this computation. So, for fixed $\chi ,{\widetilde{\chi }}$, we need to estimate the number of $k$-partitions of $[n]$ that are bi-chromatic under both $\chi$ and ${\widetilde{\chi }}$. To make this strategy precise, we need the next definitions.

Definition 6.

Let ${\widetilde{\chi }}$ be an equitable 2-coloring of $[n]$. An edge $P \subset [n]$ is $(\chi ,{\widetilde{\chi }})$-bichromatic if $\chi (P) = {\widetilde{\chi }}(P) = \{0,1\}$. Recall that a $k$-partition is a partition $\pi =\{P_1$, …, $P_{n/k}\}$ of $[n]$ such that every part $P \in \pi$ has cardinality $k$. A $k$-partition $\pi$ is $(\chi ,{\widetilde{\chi }})$-bichromatic if every part $P \in \pi$ is $(\chi ,{\widetilde{\chi }})$-bichromatic.

Given a $(\chi ,{\widetilde{\chi }})$-bichromatic edge $P \subset [n]$ of size $k$, there is a $2\times 2$ matrix ${\vec{e}}({\widetilde{\chi }},P)$ defined by

$$\begin{equation*} {\vec{e}}_{i,j}({\widetilde{\chi }},P) = |P \cap \chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|. \end{equation*}$$

Let ${\mathcal{E}}$ denote the set of all such matrices (over all $P,{\widetilde{\chi }}$). This is a finite set. To be precise, ${\mathcal{E}}$ is the set of all $2\times 2$ matrices ${\vec{e}}=(e_{ij})_{i,j=0,1}$ such that

•

$e_{ij} \in \{0$, $1$, $\ldots$, $k\}$ for all $i,j$

•

$0<e_{10} + e_{11} < k$

•

$0<e_{01}+e_{11}<k$

•

$\sum _{i,j} e_{ij} = k$.

If $\pi$ is a $(\chi ,{\widetilde{\chi }})$-bichromatic $k$-partition then it induces a function $t_{{\widetilde{\chi }},\pi }:{\mathcal{E}} \to [0,1]$ by

$$\begin{equation*} t_{{\widetilde{\chi }},\pi }({\vec{e}}) = n^{-1}\#\left\{P \in \pi :\nobreakspace {\vec{e}}={\vec{e}}({\widetilde{\chi }},P) \right\}. \end{equation*}$$

Let ${\mathcal{T}}$ be the set of all functions $t:{\mathcal{E}} \to [0,1]$ satisfying

•

$\sum _{{\vec{e}}\in {\mathcal{E}}} t({\vec{e}})=1/k$,

•

$\sum _{{\vec{e}} \in {\mathcal{E}}} (e_{10} + e_{11})t({\vec{e}}) = 1/2$,

•

$\sum _{{\vec{e}} \in {\mathcal{E}}} (e_{01} + e_{11})t({\vec{e}}) = 1/2$.

Also let ${\mathcal{T}}_n$ be the set of $t \in {\mathcal{T}}$ such that $nt({\vec{e}})$ is integer-valued for each ${\vec{e}} \in {\mathcal{E}}$. A $k$-partition $\pi$ has type $(\chi ,{\widetilde{\chi }},t)$ if $t=t_{{\widetilde{\chi }},\pi }$.

Lemma 5.2.

Given an equitable 2-coloring ${\widetilde{\chi }}:[n] \to \{0,1\}$, let $p^{\widetilde{\chi }}=(p^{\widetilde{\chi }}_{ij})$ be the $2\times 2$ matrix

$$\begin{equation*} p^{\widetilde{\chi }}_{ij} = (1/n)| \chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|. \end{equation*}$$

Then

$$\begin{equation*} p^{\widetilde{\chi }} = \left[\begin{array}{cc} 1/2 - d_n(\chi ,{\widetilde{\chi }})/2 & d_n(\chi ,{\widetilde{\chi }})/2 \\d_n(\chi ,{\widetilde{\chi }})/2 & 1/2- d_n(\chi ,{\widetilde{\chi }})/2 \end{array}\right]. \end{equation*}$$

In particular, $p^{\widetilde{\chi }}$ is determined by the Hamming distance $d_n(\chi ,{\widetilde{\chi }})$.

Proof.

Let $p=p^{\widetilde{\chi }}$. The lemma follows from this system of linear equations:

$$\begin{align*} 1/2 &= p_{01} + p_{11} \\ 1/2 &= p_{10} + p_{11} \\ d_n(\chi ,{\widetilde{\chi }}) &= p_{01} + p_{10}\\ 1 &= p_{00} + p_{01} + p_{10} + p_{11}. \end{align*}$$

The first two occur because both $\chi$ and ${\widetilde{\chi }}$ are equitable. The third follows from the definition of normalized Hamming distance and the last holds because $\{\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)\}_{i,j \in \{0,1\}}$ partitions $[n]$.

■

For $t \in {\mathcal{T}}$, define the $2\times 2$ matrix $p^t=(p^t_{ij})$ by

$$\begin{equation*} p^t_{ij} \coloneq \sum _{{\vec{e}} \in {\mathcal{E}}} e_{ij} t({\vec{e}}). \end{equation*}$$

If $\pi$ is a $k$-partition that has type $(\chi ,{\widetilde{\chi }},t)$ (for some equitable ${\widetilde{\chi }}$) then $p^{\widetilde{\chi }} = p^t$. This motivates the definition.

The main combinatorial estimate we will need is:

Lemma 5.3.

Let $t\in {\mathcal{T}}_n$ and ${\widetilde{\chi }}:[n]\to \{0,1\}$ be equitable. Suppose $p^t=p^{\widetilde{\chi }}$. Let $g({\widetilde{\chi }},t)$ be the number of $k$-partitions of type $(\chi ,{\widetilde{\chi }},t)$. Also let

$$\begin{equation*} G(t)\coloneq (1-1/k)(\log (n)-1) - H(p^t) -(1/k)\log (k!) + H(t) + \sum _{{\vec{e}}} t({\vec{e}}) \log {k \choose {\vec{e}}}, \end{equation*}$$

where ${k \choose {\vec{e}}}$ is the multinomial $\frac{k!}{e_{00}!e_{01}!e_{10}!e_{11}!}$. Then

$$\begin{equation*} (1/n)\log g({\widetilde{\chi }},t) = G(t) + O(n^{-1}\log (n)) \end{equation*}$$

(for $n\ge 2$) where the constant implicit in the error term depends on $k$ but not on ${\widetilde{\chi }}$ or $t$.

Proof.

The following algorithm constructs all such partitions with no duplications:

Step 1.

Choose a partition $\{Q_{ij}^{\vec{e}}:\nobreakspace i,j \in \{0,1\}, {\vec{e}} \in {\mathcal{E}}\}$ of $\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)$ such that$$\begin{equation*} |Q_{ij}^{\vec{e}}| = e_{ij}t({\vec{e}}) n. \end{equation*}$$

Step 2.

For $i,j\in \{0,1\}$ and ${\vec{e}} \in {\mathcal{E}}$, choose an unordered partition $\pi ^{\vec{e}}_{ij}$ of $Q_{ij}^{\vec{e}}$ into $t({\vec{e}}) n$ sets of size $e_{ij}$.

Step 3.

For $i,j\in \{0,1\}$ with $(i,j) \ne (0,0)$ and ${\vec{e}} \in {\mathcal{E}}$, choose a bijection $\alpha ^{\vec{e}}_{ij}: \pi ^{\vec{e}}_{00} \to \pi ^{\vec{e}}_{ij}$.

Step 4.

The $k$-partition consists of all sets of the form $P \cup \bigcup _{i,j\in \{0,1\}, (i,j) \ne (0,0)} \alpha ^{{\vec{e}}}_{ij}(P)$ over all $P \in \pi ^{\vec{e}}_{00}$ and ${\vec{e}} \in {\mathcal{E}}$.

The number of choices in Step 1 is

$$\begin{equation*} \prod _{i,j \in \{0,1\} } |\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|! \prod _{{\vec{e}} \in {\mathcal{E}}} (e_{ij} t({\vec{e}})n)!^{-1}. \end{equation*}$$

The combined number of choices in Steps 1 and 2 is

$$\begin{align*} & \prod _{i,j \in \{0,1\} } |\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|! \prod _{{\vec{e}} \in {\mathcal{E}}} e_{ij}!^{-t({\vec{e}})n} (t({\vec{e}})n)!^{-1} \\ & \qquad = \left( \prod _{{\vec{e}} \in {\mathcal{E}}} (t({\vec{e}})n)! \right)^{-4} \prod _{i,j \in \{0,1\} } |\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|! \prod _{{\vec{e}} \in {\mathcal{E}}} e_{ij}!^{-t({\vec{e}})n}. \end{align*}$$

The number of choices in Step 3 is $\prod _{{\vec{e}} \in {\mathcal{E}}} (t({\vec{e}})n)!^3$. So

$$\begin{equation*} g({\widetilde{\chi }},t) = \left(\prod _{i,j \in \{0,1\}} |\chi ^{-1}(i) \cap {\widetilde{\chi }}^{-1}(j)|! \right) \left( \prod _{{\vec{e}} \in {\mathcal{E}}} (t({\vec{e}})n)! \right)^{-1} \left(\prod _{i,j\in \{0,1\}} \prod _{{\vec{e}} \in {\mathcal{E}}} e_{ij}!^{-t({\vec{e}})n} \right). \end{equation*}$$

An application of Stirling’s formula gives

$$\begin{align*} & (1/n)\log g({\widetilde{\chi }},t) \\ & \qquad =(1-1/k)(\log (n)-1) - H(p^t) + H(t) - \sum _{{\vec{e}},i,j} t({\vec{e}}) \log (e_{ij}!) + O(n^{-1}\log (n)) \end{align*}$$

(for $n\ge 2$) where the constant implicit in the error term depends on $k$ but not on ${\widetilde{\chi }}$ or $t$.

Since $\sum _{\vec{e}} t({\vec{e}})=1/k$,

$$\begin{equation*} \sum _{{\vec{e}}} t({\vec{e}}) \log {k \choose {\vec{e}}} = (1/k)\log (k!) - \sum _{{\vec{e}},i,j} t({\vec{e}}) \log (e_{ij}!). \end{equation*}$$

Substitute this into the formula above to finish the lemma.

■

Next we use Lagrange multipliers to maximize $G(t)$. To be precise, for $\delta \in [0,1]$, let ${\mathcal{T}}(\delta )$ be the set of all $t \in {\mathcal{T}}$ such that $p^t_{01} = \delta /2$. Define ${\mathcal{T}}_n(\delta ) = {\mathcal{T}}(\delta ) \cap {\mathcal{T}}_n$. To motivate this definition, observe that if ${\widetilde{\chi }}$ is an equitable 2-coloring and $\delta =d_n(\chi ,{\widetilde{\chi }})$ then $p^{\widetilde{\chi }}_{01}=\delta /2$. So if $\pi$ is a $k$-partition with type $(\chi ,{\widetilde{\chi }},t)$ then $p^t_{01}=\delta /2$.

Lemma 5.4.

Let $\delta \in [0,1]$. Then there exists a unique $s_\delta \in {\mathcal{T}}(\delta )$ such that

$$\begin{equation*} \max _{t\in {\mathcal{T}}(\delta )} G(t) = G(s_\delta ). \end{equation*}$$

Moreover, if $\delta _0$, $C>0$ and $t_\delta \in {\mathcal{T}}(\delta )$ are defined by

$$\begin{align*} \frac{\delta }{2} &= \frac{\delta _0}{2} \frac{ 1-2^{2-k} + (\delta _0/2)^{k-1} }{ 1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k }\\ C &= \frac{1}{k[1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k] }\\ t_\delta ({\vec{e}}) &= C \left(\frac{1-\delta _0}{2} \right)^{e_{00}+e_{11}} \left(\frac{\delta _0}{2} \right)^{e_{01}+e_{10}} {k\choose {\vec{e}}} \end{align*}$$

then $s_\delta =t_\delta$.

Proof.

Define $F:{\mathcal{T}} \to {\mathbb{R}}$ by

$$\begin{equation*} F(t)=H(t) + \sum _{{\vec{e}}} t({\vec{e}}) \log {k \choose {\vec{e}}}. \end{equation*}$$

For all $t \in {\mathcal{T}}(\delta )$, $G(t)-F(t)$ is constant in $t$. Therefore, it suffices to prove the lemma with $F$ in place of $G$.

The function $F$ is concave over $t \in {\mathcal{T}}(\delta )$. This implies the existence of a unique $s_\delta \in {\mathcal{T}}(\delta )$ such that

$$\begin{equation*} \max _{t\in {\mathcal{T}}(\delta )} F(t) = F(s_\delta ). \end{equation*}$$

By definition, ${\mathcal{T}}(\delta )$ is the set of all functions $t:{\mathcal{E}} \to [0,1]$ satisfying

$$\begin{align*} 1/k &= \sum _{{\vec{e}}\in {\mathcal{E}}} t({\vec{e}}) \\ p_{ij} &= \sum _{{\vec{e}}\in {\mathcal{E}}} e_{ij} t({\vec{e}}), \end{align*}$$

where $p=(p_{ij})$ is the matrix

$$\begin{equation*} p = \left[\begin{array}{cc} 1/2 - \delta /2 & \delta /2 \\\delta /2 & 1/2- \delta /2 \end{array}\right]. \end{equation*}$$

For any ${\vec{e}} \in {\mathcal{E}}$,

$$\begin{equation} \frac{\partial F}{\partial t({\vec{e}})} = -\log t({\vec{e}}) - 1 + \log {k \choose {\vec{e}}}. {\tag{11}} \end{equation}$$

Since this is positive infinity when $t({\vec{e}})=0$, $s_\delta$ must lie in the interior of ${\mathcal{T}}(\delta )$. By the method of Lagrange multipliers there exists $\lambda \in {\mathbb{R}}$ and a $2\times 2$ matrix $\vec{\mu }$ such that

$$\begin{equation} \frac{\partial F}{\partial t({\vec{e}})}(s_\delta ) = \lambda + \vec{\mu } \cdot {\vec{e}}. {\tag{12}} \end{equation}$$

Evaluate 11 at $s_\delta$, use 12 and solve for $s_\delta ({\vec{e}})$ to obtain

$$\begin{equation*} s_\delta ({\vec{e}}) = C_0 {k \choose {\vec{e}}} x_{00}^{e_{00}} x_{01}^{e_{01}} x_{10}^{e_{10}}x_{11}^{e_{11}} \end{equation*}$$

for some constants $C_0, x_{ij}$. In fact, since $F$ is concave, $s_\delta$ is the unique critical point and so it is the only element of ${\mathcal{T}}(\delta )$ of this form. So it suffices to check that the purported $t_\delta$ given in the statement of the lemma has this form and that it is in ${\mathcal{T}}(\delta )$ as claimed. The former is immediate while the latter is a tedious but straightforward computation. For example, to check that $\sum _{\vec{e}} t_\delta ({\vec{e}})=1/k$, observe that, by the multinomial formula for any $(x_{ij})_{i,j\in \{0,1\}}$,

$$\begin{align*} &\sum _{{\vec{e}} \in {\mathcal{E}}} {k \choose {\vec{e}}} x_{00}^{e_{00}} x_{01}^{e_{01}} x_{10}^{e_{10}}x_{11}^{e_{11}} \\ & \qquad = \Big [ (x_{00} + x_{01} + x_{10} + x_{11})^k - (x_{00} + x_{01})^k - (x_{00} + x_{10})^k - (x_{11} + x_{01})^k\\ & \qquad \kern 2pc - (x_{11} + x_{10})^k + x_{00}^k + x_{01}^k + x_{10}^k + x_{11}^k \Big ]. \end{align*}$$

Substitute $x_{00}=x_{11}=\frac{1-\delta _0}{2}$ and $x_{01}=x_{10}=\delta _0/2$ to obtain

$$\begin{equation*} \sum _{{\vec{e}} \in {\mathcal{E}}} t_\delta ({\vec{e}}) = C\left[ 1 - 4(1/2)^k + 2\left(\frac{1-\delta _0}{2}\right)^k + 2\left(\frac{\delta _0}{2}\right)^k \right] = 1/k. \end{equation*}$$

The rest of the verification that $t_\delta \in {\mathcal{T}}(\delta )$ is left to the reader.

■

Proof of Theorem 5.1.

Let ${\mathscr{E}}(\delta )$ be the set of all equitable 2-colorings ${\widetilde{\chi }}:[n] \to \{0,1\}$ such that $d_n({\widetilde{\chi }},\chi )=\delta$. Also let $F_{{\widetilde{\chi }}} \subset {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,\operatorname {Sym}(n))$ be the set of all $\sigma$ such that ${\widetilde{\chi }}$ is a proper 2-coloring of the hyper-graph $G_\sigma$. By linearity of expectation,

$$\begin{equation*} {\mathbb{E}}^p_n[Z_\chi (\delta )] = \sum _{{\widetilde{\chi }} \in {\mathscr{E}}(\delta )} {\mathbb{P}}^u_n(F_{{\widetilde{\chi }}} | F_{\chi }). \end{equation*}$$

The cardinality of ${\mathscr{E}}(\delta )$ is ${ n/2 \choose \delta n/2}^2$. By Stirling’s formula

$$\begin{equation} n^{-1} \log { n/2 \choose \delta n/2}^2 = H(\delta , 1-\delta ) + O(n^{-1}\log (n)). {\tag{13}} \end{equation}$$

We have ${\mathbb{P}}^u_n(F_{{\widetilde{\chi }}} | F_{\chi })$ is the same for all ${\widetilde{\chi }} \in {\mathscr{E}}(\delta )$. This follows by noting that the distribution of hyper-graphs in the planted model is invariant under any permutation which fixes $\chi$. If $\eta , \eta '$ are two configurations with $d_n(\eta , \chi ) = d_n(\eta ', \chi ) = \delta$ then there is a permutation $\pi \in \operatorname {Sym}(n)$ which fixes $\chi$ and such that $\eta \circ \pi = \eta '$. To see this note that we simply need to find a $\pi \in \operatorname {Sym}(n)$ which maps the sets $\chi ^{-1}(i) \cap \eta ^{-1}(j)$ to $\chi ^{-1}(i) \cap \eta '^{-1}(j)$ for each $i,j \in \{0,1\}$. Such a map exists since for each $i,j$ the two sets have the same size. It follows that

$$\begin{equation} n^{-1} \log {\mathbb{E}}^p_n[Z_\chi (\delta )] = H(\delta , 1-\delta ) + n^{-1} \log {\mathbb{P}}^u_n(F_{{\widetilde{\chi }}} | F_{\chi }) + O(n^{-1}\log (n)) {\tag{14}} \end{equation}$$

for any fixed ${\widetilde{\chi }} \in {\mathscr{E}}(\delta )$.

For $1\le i \le d$, let $F_{\chi , i}$ be the set of uniform homomorphisms $\sigma$ such that the orbit-partition of $\sigma (s_i)$ is $\chi$-bichromatic in the sense that $\chi (P) = \{0,1\}$ for every $P$ in the orbit-partition of $\sigma (s_i)$. Then the events $\{F_{\chi ,i} \cap F_{{\widetilde{\chi }},i} \}_{i=1}^d$ are i.i.d. and

$$\begin{equation*} F_{\chi } \cap F_{{\widetilde{\chi }}} = \bigcap _{i=1}^d F_{\chi ,i} \cap F_{{\widetilde{\chi }},i}. \end{equation*}$$

Therefore,

$$\begin{equation} {\mathbb{P}}^u_n(F_{{\widetilde{\chi }}} | F_{\chi }) = \frac{{\mathbb{P}}^u_n(F_{{\widetilde{\chi }},1} \cap F_{\chi ,1})^d }{ {\mathbb{P}}^u_n(F_{\chi })}. {\tag{15}} \end{equation}$$

Note ${\mathbb{P}}^u_n(F_{\chi ,1} \cap F_{{\widetilde{\chi }},1})$ is, up to sub-exponential factors, equal to the maximum of $g({\widetilde{\chi }},t)$ over $t \in {\mathcal{T}}_n(\delta )$ divided by the number of $k$-partitions of $[n]$. So equation 6 implies

$$\begin{align*} & \frac{1}{n} \log {\mathbb{P}}^u_n(F_{{\widetilde{\chi }},1} \cap F_{\chi ,1}) \\ & \qquad = \max _{t\in {\mathcal{T}}_n(\delta )} \frac{1}{n} \log g({\widetilde{\chi }},t) - (1-1/k)(\log (n)-1) \\ & \qquad \kern 2pc +(1/k)\log ((k-1)!) + O(n^{-1}\log n). \end{align*}$$

So Lemma 5.3 implies

$$\begin{align*} & \frac{1}{n} \log {\mathbb{P}}^u_n(F_{{\widetilde{\chi }},1} \cap F_{\chi ,1}) \\ & \qquad = \max _{t\in {\mathcal{T}}_n(\delta )} G(t) - (1-1/k)(\log (n)-1) +(1/k)\log ((k-1)!) + O(n^{-1}\log n). \end{align*}$$

We apply Lemma 4.4 to ${\mathcal{T}}(\delta )$ to obtain the existence of $s^{(n)}_\delta \in {\mathcal{T}}_n(\delta )$ with $\|s^{(n)}_\delta - t_\delta \|_\infty < O_\delta (n^{-1})$ where the constant implicit in the $O_\delta (n^{-1})$ term depends continuously on $\delta$ for $\delta \in (0,1/2]$. Since $G$ is differentiable in a neighborhood of $t_\delta$, we have

$$\begin{equation*} \max _{t\in {\mathcal{T}}_n(\delta )} G(t)= G(t_\delta ) + O_\delta (n^{-1}). \end{equation*}$$

So Lemma 5.4 implies

$$\begin{align*} \frac{1}{n} \log {\mathbb{P}}^u_n(F_{{\widetilde{\chi }},1} \cap F_{\chi ,1}) =& -H({\vec{p}}) + H(t_\delta ) - \sum _{i,j,{\vec{e}}} t_\delta ({\vec{e}}) \log (e_{ij}!) + (1/k)\log (k-1)! \\ & + O_\delta (n^{-1}) + O(n^{-1}\log (n)). \end{align*}$$

Since ${\vec{p}}=(\delta /2,\delta /2,(1-\delta )/2,(1-\delta )/2)$, $H({\vec{p}}) = H(\delta ,1-\delta ) + \log (2)$. So

$$\begin{align} \frac{1}{n} \log {\mathbb{P}}^u_n(F_{{\widetilde{\chi }},1} \cap F_{\chi ,1}) =& -H(\delta ,1-\delta ) - \log (2) + H(t_\delta ) - \sum _{i,j,{\vec{e}}} t_\delta ({\vec{e}}) \log (e_{ij}!) \\ & + (1/k)\log (k-1)! + O_\delta (n^{-1}) + O(n^{-1}\log (n)). {\tag{16}} \end{align}$$

On the other hand, Theorem 4.2 implies

$$\begin{align*} \frac{1}{n} \log {\mathbb{P}}^u_n(F_{\chi }) &= \frac{1}{n} \log \left( {n\choose n/2}^{-1} {\mathbb{E}}^u_n[Z_e(\sigma )]\right) \\ &= (d/k)\log (1-2^{1-k}) + O(n^{-1}\log (n)). \end{align*}$$

Combine this result with 14, 15 and 16 to obtain

$$\begin{align*} & n^{-1} \log {\mathbb{E}}^p_n[Z_\chi (\delta )]\\ & \qquad = (1-d)H(\delta ,1-\delta ) - d\log (2) + dH(t_\delta )- d\sum _{i,j,{\vec{e}}} t_\delta ({\vec{e}}) \log (e_{ij}!)\\ & \qquad \quad + (d/k)\log (k-1)! - (d/k)\log (1-2^{1-k}) + O_\delta (n^{-1}) + O(n^{-1}\log (n)). \end{align*}$$

Since $\sum _{{\vec{e}}} t_\delta ({\vec{e}}) =1/k$,

$$\begin{equation*} \sum _{{\vec{e}}} t_\delta ({\vec{e}}) \log {k \choose {\vec{e}} } = (1/k) \log k! - \sum _{i,j,{\vec{e}}} t_\delta ({\vec{e}}) \log (e_{ij}!). \end{equation*}$$

Substitute this into the previous equation to obtain

$$\begin{equation*} n^{-1} \log {\mathbb{E}}^p_n[Z_\chi (\delta )] = \psi _0(\delta ) + O_\delta (n^{-1}) + O(n^{-1}\log (n)), \end{equation*}$$

where

$$\begin{align*} \psi _0(\delta )=&(1-d)H(\delta ,1-\delta ) - d\log (2) + dH(t_\delta ) + d \sum _{{\vec{e}} \in {\mathcal{E}}} t_\delta ({\vec{e}}) \log {k \choose {\vec{e}} } \\ &- (d/k)\log k -(d/k)\log (1-2^{1-k}). \end{align*}$$

Observe that in every estimate above, the constant implicit in the error term does not depend on $\delta$. To finish the lemma, we need only simplify the expression for $\psi _0$.

By Lemma 5.4,

$$\begin{align*} H(t_\delta ) &= -\sum _{{\vec{e}}}t_\delta ({\vec{e}})\log t_\delta ({\vec{e}})\\ &= -\sum _{{\vec{e}}}t_\delta ({\vec{e}}) \left(\log C \!+\! (e_{00} \!+\! e_{11})\log \left(\frac{1-\delta _0}{2}\right) \!+\! (e_{01} \!+\! e_{10})\log \left(\frac{\delta _0}{2}\right) \!+\! \log {k \choose {\vec{e}}}\right)\\ &= -(1/k)(\log C) - (1-\delta )\log (1-\delta _0) - \delta \log (\delta _0) + \log 2 - \sum _{\vec{e}} t_\delta ({\vec{e}}) \log {k \choose {\vec{e}}} \\ &=-(1/k)(\log C) + H_0(\delta ,1-\delta ) + \log 2 - \sum _{\vec{e}} t_\delta ({\vec{e}}) \log {k \choose {\vec{e}}}. \end{align*}$$

Combined with the previous formula for $\psi _0$, this implies

$$\begin{equation*} \psi _0(\delta )\!=\!(1-d)H(\delta ,1-\delta ) -(d/k)\log C + dH_0(\delta ,1-\delta ) - (d/k)\log k -(d/k)\log (1-2^{1-k}). \end{equation*}$$

To simplify further, use the formula for $C$ in Lemma 5.4 to obtain

$$\begin{align*} & -(d/k)\left(\log C + \log k + \log (1-2^{1-k})\right) \\ & \qquad = (d/k)\log \frac{1 - 2^{2-k} + 2(\delta _0/2)^k + 2((1-\delta _0)/2)^k}{1-2^{1-k}} \\ & \qquad = (d/k) \log \left(1- \frac{1 - \delta _0^k - (1-\delta _0)^k}{2^{k-1}-1}\right). \end{align*}$$

Thus $\psi _0(\delta ) = (1-d)H(\delta ,1-\delta ) + dH_0(\delta ,1-\delta ) + \frac{d}{k}\log (1- \frac{1-\delta _0^k-(1-\delta _0)^k}{2^{k-1}-1})$.

■

5.1. Analysis of $\psi _0$ and the proof of Lemma 1.2 inequality 2

Theorem 5.1 reduces inequality 2 to analyzing the function $\psi _0$. A related function $\psi$, defined by

$$\begin{equation*} \psi (x)\coloneq H(x,1-x) + \frac{d}{k} \log \left( 1 - \frac{1 - x^k - (1-x)^k}{2^{k-1}-1}\right), \end{equation*}$$

has been analyzed in 67. It is shown there $\psi (x)$ is the exponential rate of growth of the number of proper colorings at normalized distance $x$ from the planted coloring in the model $H_k(n,m)$. Moreover, if $r=d/k$ is close to $\frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2$ then the global maximum of $\psi (x)$ is attained at some $x\in (0,2^{-k/2})$. Moreover, $\psi$ has a local maximum at $x=1/2$ and is symmetric around $x=1/2$. It is negative in the region $(2^{-k/2}, 1/2 - 2^{-k/2})$. We will not need these facts directly, and mention them only for context, especially because we will obtain similar results for $\psi _0$.

The relevance of $\psi$ to $\psi _0$ lies in the fact that

$$\begin{equation} \psi _0(\delta )=\psi (\delta _0) - (H(\delta _0,1-\delta _0) - H_0(\delta ,1-\delta )) + (d-1)\left[ H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )\right]. {\tag{17}} \end{equation}$$

As an aside, note that $H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )$ is the Kullback-Leibler divergence of the distribution $(\delta ,1-\delta )$ with respect to $(\delta _0,1-\delta _0)$.

To prove inequality 2, we first estimate the difference $\psi _0(\delta )-\psi (\delta _0)$ and then estimate $\psi (\delta _0)$. Because the estimates we obtain are useful in the next subsection, we prove more than what is required for just inequality 2.

Lemma 5.5.

Suppose $0 \leq \delta _0 \leq 1/2$. Define $\varepsilon \ge 0$ by $\delta = \delta _0(1-\varepsilon )$. Then

$$\begin{align*} H(\delta _0,1-\delta _0) - H_0(\delta ,1-\delta ) &= \delta _0\varepsilon \log \left(\frac{1-\delta _0}{\delta _0}\right) \ge 0, \\ H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )&= O(\delta _0\varepsilon ^2),\\ \varepsilon &= O(2^{-k}), \\ (1-\delta )_0 &= 1-\delta _0. \end{align*}$$

The last equation implies $\psi _0(1-\delta ) = \psi _0(\delta )$.

Proof.

The first equality follows from:

$$\begin{align*} & H(\delta _0,1-\delta _0) - H_0(\delta ,1-\delta ) \\ & \qquad = -\delta _0\log \delta _0 - (1-\delta _0)\log (1-\delta _0) + \delta \log \delta _0 + (1-\delta )\log (1-\delta _0) \\ & \qquad = (\delta _0 - \delta )\log (1/\delta _0) + (\delta _0 - \delta )\log (1-\delta _0)\\ & \qquad = \delta _0\varepsilon \log \left(\frac{1-\delta _0}{\delta _0}\right). \end{align*}$$

The second estimate follows from:

$$\begin{align*} H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )&= \delta \left(\log \delta - \log \delta _0 \right) + (1-\delta ) \left( \log (1-\delta ) - \log (1-\delta _0) \right)\\ &= \delta \log (1-\varepsilon ) + (1-\delta )\log \left(\frac{1-\delta }{1-\delta _0}\right)\\ &= -\delta \varepsilon + (1-\delta )\log \left(1+ \frac{\delta _0\varepsilon }{1-\delta _0}\right) + O(\delta _0\varepsilon ^2) \\ &= -\delta \varepsilon + \delta _0\varepsilon + O(\delta _0\varepsilon ^2) = O(\delta _0\varepsilon ^2). \end{align*}$$

The third estimate follows from:

$$\begin{align} \varepsilon &= 1- \frac{\delta }{\delta _0} \\ &= 1-\frac{1 - 2^{2-k} + (\delta _0/2)^{k-1}}{1 - 2^{2-k} + 2(\delta _0/2)^{k} + 2((1-\delta _0)/2)^k} \\ &= \frac{2(\delta _0/2)^{k} - (\delta _0/2)^{k-1}+ 2((1-\delta _0)/2)^k}{1 - 2^{2-k} + 2(\delta _0/2)^{k} + 2((1-\delta _0)/2)^k} \\ &= \frac{(\delta _0/2)^{k-1}(\delta _0-1)+ 2((1-\delta _0)/2)^k}{1 - 2^{2-k} + 2(\delta _0/2)^{k} + 2((1-\delta _0)/2)^k}\\ &= 2^{1-k}\cdot (1-\delta _0) \cdot \frac{(1-\delta _0)^{k-1} - \delta _0^{k-1} }{1 - 2^{2-k} + 2(\delta _0/2)^{k} + 2((1-\delta _0)/2)^k}. {\tag{18}} \end{align}$$

The denominator is $1+O(2^{-k})$ and the numerator is $O(2^{-k})$. The result follows.

The last equation follows from:

$$\begin{align*} 1-\delta &= 1 - \delta _0 \left(\frac{ 1-2^{2-k} + (\delta _0/2)^{k-1} }{ 1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k }\right) \\ &= \frac{1-2^{2-k} + 2(\delta _0/2)^k +2\left( (1-\delta _0)/2)^k - \delta _0(1-2^{2-k} + (\delta _0/2)^{k-1} \right)}{1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k} \\ &= \frac{(1-\delta _0)\left(1-2^{2-k}+((1-\delta _0)/2)^{k-1}\right)}{1-2^{2-k} + 2(\delta _0/2)^k +2( (1-\delta _0)/2)^k}. \end{align*}$$

The last expression shows that $(1-\delta )_0 = 1-\delta _0$.

■

Lemma 5.6.

Let $0 \le \eta$ be $O_k(1)$. If

$$\begin{equation*} r =d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta , \end{equation*}$$

then

$$\begin{align*} f(d,k) &= \psi (1/2)=\psi _0(1/2) = (1-2\eta )2^{-k} + O(2^{-2k}) \\ \psi (2^{-k}) &= 2^{-k} + O(k^2 2^{-2k}). \end{align*}$$

In particular, if $k$ is sufficiently large then $\psi (2^{-k}) > f(d,k)$.

Proof.

By direct inspection $f(d,k)=\psi (1/2)=\psi _0(1/2)$. By Taylor series expansion, $\log (1-2^{1-k}) = -2^{1-k} - 2^{1-2k} + O(2^{-3k})$. So

$$\begin{align*} f(d,k)&=\log (2) + r \log (1-2^{1-k}) \\ &= \log (2) + \left( \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \right) \left( - 2^{1-k} - 2^{1-2k} \right) + O(r 2^{-3k}) \\ &= (1-2\eta )2^{-k} + O(2^{-2k}). \end{align*}$$

Next we estimate $\psi (2^{-k})$. For convenience, let $x=2^{-k}$. Then

$$\begin{equation*} 1 - x^k - (1-x)^k = k\cdot 2^{-k} + O(k^2 2^{-2k}). \end{equation*}$$

Since $\log (1-x)=-x - x^2/2 + O(x^3)$,

$$\begin{equation*} \log \left( 1 - \frac{1 - x^k - (1-x)^k}{2^{k-1}-1}\right) = -2k \cdot 2^{-2k} + O(k^2 2^{-3k}). \end{equation*}$$

So

$$\begin{equation*} r \log \left( 1 - \frac{1 - x^k - (1-x)^k}{2^{k-1}-1}\right) = -k\log (2)\cdot 2^{-k} + O(k^2 2^{-2k}). \end{equation*}$$

Also,

$$\begin{equation*} H(x,1-x) = (k\log (2) + 1)\cdot 2^{-k} + O(2^{-2k}). \end{equation*}$$

Add these together to obtain

$$\begin{equation*} \psi (2^{-k}) = 2^{-k} + O(k^22^{-2k}). \end{equation*}$$■

Corollary 5.7.

Inequality 2 of Lemma 1.2 is true. To be precise, let $0<\eta _0$ be constant with respect to $k$. Then for all sufficiently large $k$ (depending on $\eta _0$), if

$$\begin{equation*} r =d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta \ge \eta _0$ with $\eta =O_k(1)$ then

$$\begin{equation*} f(d,k) < \liminf _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )]. \end{equation*}$$

Proof.

By definition,

$$\begin{equation*} n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )] \ge \max _{\delta \in [0,1/2]} n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\delta )]. \end{equation*}$$

By Theorem 5.1,

$$\begin{equation*} n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )] \ge \max _{\delta \in C_n} \psi _0(\delta ) + O_\delta (n^{-1}) + O(n^{-1}\log (n)), \end{equation*}$$

where $C_n$ is the set of $\delta \in [0,1/2]$ such that $\delta n/2$ is an integer. Because $\psi _0:[0,1/2] \to {\mathbb{R}}$ is continuous, $\lim _{n\to \infty } \max _{\delta \in C_n} \psi _0(\delta ) = \max _{\delta \in [0,1/2]} \psi _0(\delta )$. The constant implicit in the $O_\delta (n^{-1})$ depends continuously on $\delta$ for $\delta \in (0,1/2]$, while the constant implicit in the $O(n^{-1}\log (n))$ error term does not depend on $\delta$. So

$$\begin{equation*} \liminf _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )] \ge \max _{\delta \in [\upsilon ,1/2]} \psi _0(\delta ) \end{equation*}$$

for any $0<\upsilon <1/2$. Because $\psi _0$ is continuous,

$$\begin{equation} \liminf _{n\to \infty } n^{-1}\log {\mathbb{E}}_n^{p}[ Z(\sigma )] \ge \max _{\delta \in [0,1/2]} \psi _0(\delta ). {\tag{19}} \end{equation}$$

Because $H_0(\delta ,1-\delta ) - H(\delta ,1-\delta ) \ge 0$ (since it is a Kullback-Liebler divergence), the first equality of Lemma 5.5 implies

$$\begin{align*} \psi _0(\delta ) &= \psi (\delta _0) - (H(\delta _0,1-\delta _0) - H_0(\delta ,1-\delta )) \!+\! (d-1)\left[ H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )\right] \\ &\ge \psi (\delta _0) - \delta _0\varepsilon \log \left(\frac{1-\delta _0}{\delta _0}\right). \end{align*}$$

By Lemma 5.6, $\psi (2^{-k}) = f(d,k)+2\eta 2^{-k} + O(k^2 2^{-2k})$. By Lemma 5.5, $\varepsilon = O(2^{-k})$. As $\delta$ varies over $[0,1/2]$, $\delta _0$ also varies over $[0,1/2]$, so there exists $\delta$ such that $\delta _0=2^{-k}$. For this value of $\delta$,

$$\begin{equation*} \psi _0(\delta ) \ge \psi (2^{-k}) -2^{-k}\varepsilon \log \left(\frac{1-2^{-k}}{2^{-k}}\right) \ge f(d,k) + 2\eta 2^{-k} + O(k^2 2^{-2k}). \end{equation*}$$

Combined with 19 this implies the Corollary.

■

In the next subsection, we will need the following result.

Proposition 5.8.

Let

$$\begin{equation*} 0<\eta _0 < (1-\log 2)/2. \end{equation*}$$

Then there exists $k_0$ (depending on $\eta _0$) such that for all $k\ge k_0$ if

$$\begin{equation*} r=d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta \in [\eta _0,(1-\log 2)/2)$ then in the interval $[2^{-k/2},1-2^{-k/2}]$, $\psi _0$ attains its unique maximum at 1/2. That is,

$$\begin{equation*} \max \{\psi _0(\delta ):\nobreakspace 2^{-k/2} \le \delta \le 1-2^{-k/2}\} = \psi _0(1/2)=f(d,k) = \log (2) + r \log (1-2^{1-k}) \end{equation*}$$

and if $\delta \in [2^{-k/2},1-2^{-k/2}]$ and $\delta \ne 1/2$ then $\psi _0(\delta )<\psi _0(1/2)$.

Proof.

By Lemma 5.5, it suffices to restrict $\delta$ to the interval $[2^{-k/2},1/2]$ (because $\psi _0(\delta )=\psi _0(1-\delta )$). So we will assume $\delta \in [2^{-k/2},1/2]$ without further mention.

Define $\psi _1$ by

$$\begin{equation*} \psi _1(\delta _0)=\frac{d}{k} \log \left( 1 - \frac{1 - \delta _0^k - (1-\delta _0)^k}{2^{k-1}-1}\right). \end{equation*}$$

Observe

$$\begin{align*} \psi _1(\delta _0) &= r \left( - \frac{1 - \delta _0^k - (1-\delta _0)^k}{2^{k-1}-1} + O(4^{-k}) \right) \\ &= -\log (2)[1-(1-\delta _0)^k] + O(2^{-k}). \end{align*}$$

By 17 and the first inequality of Lemma 5.5,

$$\begin{align} \psi _0(\delta ) &\leq \psi (\delta _0) + (d-1)[H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )] \\ &= H(\delta _0,1-\delta _0) + \psi _1(\delta _0) + (d-1)[H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )]. {\tag{20}} \end{align}$$

Moreover, $(d-1)=O(k2^k)$ and, by Lemma 5.5, $H_0(\delta ,1-\delta ) - H(\delta ,1-\delta ) = O(\delta _04^{-k})$. Therefore,

$$\begin{align} \psi _0(\delta ) &\le H(\delta _0,1-\delta _0) + \psi _1(\delta _0) + O(\delta _0 k 2^{-k})\\ &\le H(\delta _0,1-\delta _0) -\log (2)[1-(1-\delta _0)^k] + O((\delta _0 k+1) 2^{-k}). {\tag{21}} \end{align}$$

Observe that $\delta _0 \ge \delta$. We divide the rest of the proof into five cases depending on where $\delta _0$ lies in the interval $[2^{-k/2},1/2]$.

Case 1.

Suppose $2^{-k/2} \leq \delta _0 \leq \frac{1}{2k}$. We claim that $\psi _0(\delta ) <0$. Note $-\log (\delta _0) \le (k/2)\log (2)$ and $-(1-\delta _0)\log (1-\delta _0) = \delta _0 + O(\delta _0^2)$. So

$$\begin{align*} H(\delta _0,1-\delta _0) &= -\delta _0 \log \delta _0 - (1-\delta _0)\log (1-\delta _0) \\ &\le \delta _0(k/2)\log (2) + \delta _0 + O(\delta _0^{2}). \end{align*}$$

By Taylor series expansion,

$$\begin{equation*} 1-(1-\delta _0)^k \ge k \delta _0 - {k \choose 2}\delta _0^2 \ge 3k\delta _0/4. \end{equation*}$$

So by 21

$$\begin{align*} \psi _0(\delta ) &\le \delta _0(k/2)\log (2) + \delta _0 - 3k\delta _0\log (2)/4+ O(\delta _0^{2}) \\ &= \delta _0[1-k\log (2)/4] + O(\delta _0^{2}). \end{align*}$$

Thus $\psi _0(\delta )<0$ if $k$ is sufficiently large.

Case 2.

Let $0<\xi _0<1/2$ be a constant such that $H(\xi _0,1-\xi _0) < \log (2)(1-e^{-1/2})$. Suppose $\frac{1}{2k} \leq \delta _0 \leq \xi _0$. We claim that $\psi _0(\delta )<0$ if $k$ is sufficiently large.

By monotonicity, $H(\delta _0,1-\delta _0) \le H(\xi _0,1-\xi _0)$. Since $1-x \le e^{-x}$ (for $x>0$),

$$\begin{equation*} [1-(1-\delta _0)^k] \ge 1- e^{-k\delta _0} \ge 1-e^{-1/2}. \end{equation*}$$

By 21,

$$\begin{equation*} \psi _0(\delta ) \le H(\xi _0,1-\xi _0) - \log (2)(1-e^{-1/2}) + O( k2^{-k}). \end{equation*}$$

This implies the claim.

Case 3.

Let $\xi _1$ be a constant such that $\max (\xi _0,1/3)<\xi _1<1/2$. Suppose $\xi _0 \leq \delta _0 \leq \xi _1$. We claim that $\psi _0(\delta )<0$ for all sufficiently large $k$ (depending on $\xi _1$).

By 21,

$$\begin{align*} \psi _0(\delta ) &\le H(\xi _1,1-\xi _1) - \log (2)[1-(1-\delta _0)^k] + O( k2^{-k}) \\ & \le H(\xi _1,1-\xi _1) - \log (2) + O( (1-\xi _0)^k). \end{align*}$$

This proves the claim.

Case 4.

We claim that if $\xi _1 \le \delta _0 \le 0.5-2^{-k}$ then $\psi _0(\delta )<f(d,k)$ for all sufficiently large $k$ (independent of the choice of $\xi _1$).

Recall that we define $\varepsilon$ by $\delta = \delta _0(1-\varepsilon )$. By 18,

$$\begin{align*} \varepsilon &= 2^{1-k}\cdot (1-\delta _0) \cdot \frac{(1-\delta _0)^{k-1} - \delta _0^{k-1} }{1 - 2^{2-k} + 2(\delta _0/2)^{k} + 2((1-\delta _0)/2)^k} \\ &\le 2^{1-k}(1-\xi _1)^{k} + O\left(4^{-k}\right) \le 2\cdot 3^{-k} \end{align*}$$

since $\xi _1 >1/3$, assuming $k$ is sufficiently large.

The assumption on $r$ implies $d=O\left(k2^k\right)$. So the second equality of Lemma 5.5 implies

$$\begin{equation*} (d-1)[H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )] = O\left(k 4.5^{-k}\right). \end{equation*}$$

Through elementary but messy calculus computations one may show using the fact that $r = O(2^k)$ that

$$\begin{align*} \psi '(1/2) &= 0 \\ \psi ''(1/2) &= -4 + O( k^2 2^{-k}) \\ \psi '''(x) &= \frac{1}{x^2} - \frac{1}{(1-x)^2} + O(k^3 (2/3)^k ) \text{ for any } x \in [1/3,2/3]. \end{align*}$$

By Taylor’s theorem,

$$\begin{equation} \psi (\delta _0)= \psi (1/2) - (2+o_k(1) )(\delta _0 - 1/2)^2 + \frac{1}{6} \left( \frac{1}{\upsilon ^2} - \frac{1}{(1-\upsilon )^2} + o_k(1) \right) (\delta _0-1/2)^3 {\tag{22}} \end{equation}$$

for some $\delta _0 \leq \upsilon \leq 1/2$. Since $\delta _0 \geq 1/3$, we have $1/2 - \delta _0 \leq 1/6$. Furthermore, since $x \mapsto \frac{1}{x^2} - \frac{1}{(1-x)^2}$ is monotone decreasing on $(0,1/2]$, we have $\frac{1}{\upsilon ^2} - \frac{1}{(1-\upsilon )^2} \leq \frac{1}{(1/3)^2} - \frac{1}{(2/3)^2} = \frac{27}{4}$. Thus

$$\begin{align*} \frac{ \frac{1}{6} \left( \frac{1}{\upsilon ^2} - \frac{1}{(1-\upsilon )^2} \right) (1/2 - \delta _0)^3}{ 2 (1/2-\delta _0)^2} & \leq \frac{1}{12} \cdot \frac{27}{4} \cdot \frac{1}{6} < 1 \end{align*}$$

and for sufficiently large $k$ we have $\frac{1}{6} \left( \frac{1}{\upsilon ^2} - \frac{1}{(1-\upsilon )^2} + o_k(1) \right) (1/2 - \delta _0)^3 < (2+o_k(1)) (1/2 - \delta _0)^2$. Since $\psi (1/2)=f(d,k)$, 20 implies

$$\begin{align*} \psi _0(\delta ) \le & f(d,k) - (2+o_k(1))(1/2-\delta _0)^2 \\ & + \frac{1}{6} \left( \frac{1}{\upsilon ^2} - \frac{1}{(1-\upsilon )^2} + o_k(1) \right) (1/2 - \delta _0)^3 + O\left(k 4.5^{-k}\right) \end{align*}$$

is strictly less than $f(d,k)$ if $k$ is sufficiently large.

Case 5.

Suppose $0.5-2^{-k} \le \delta _0 < 0.5$. Let $\gamma = 0.5 - \delta _0$. By 18,

$$\begin{equation*} \varepsilon = O\left( \left[(1/2 +\gamma )^{k-1} -(1/2 -\gamma )^{k-1}\right]2^{-k}\right). \end{equation*}$$

Define $L(x)\coloneq (1/2 +x)^{k-1} -(1/2 -x)^{k-1}$. We claim that $L(\gamma ) \le \gamma$. Since $L(0)=0$, it suffices to show that $L'(x)\le 1$ for all $x$ with $|x|\le 0.01$. An elementary calculation shows

$$\begin{equation*} L'(x) = (k-1)\left[ (1/2 +x)^{k-2} +(1/2 -x)^{k-2}\right]. \end{equation*}$$

So $L'(x) \le 1$ if $|x|\le 0.01$ and $k$ is sufficiently large. Altogether this proves $\varepsilon = O\left(\gamma 2^{-k}\right)$. So the second equality of Lemma 5.5 implies

$$\begin{equation*} (d-1)\left[H_0(\delta ,1-\delta ) - H(\delta ,1-\delta )\right] = O\left(k2^{-k} \gamma ^2\right). \end{equation*}$$

By 22 and 20,

$$\begin{equation*} \psi _0(\delta ) \le f(d,k) - (2+o_k(1))\gamma ^2 + O\left(k2^{-k} \gamma ^2\right). \end{equation*}$$

This is strictly less than $f(d,k)$ if $k$ is sufficiently large.■

5.2. Reducing Lemma 1.2 inequality 3 to estimating the local cluster

As in the previous section, fix an equitable coloring $\chi :V_n \to \{0,1\}$. Given a uniform homomorphism $\sigma \in {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,{\operatorname {Sym}}(n))$, the cluster around $\chi$ is the set

$$\begin{equation*} {\mathcal{C}}_{\sigma }(\chi ) \coloneq \left\{{\widetilde{\chi }} \in Z_e(\sigma ): d_n(\chi ,{\widetilde{\chi }}) \leq 2^{-k/2}\right\}. \end{equation*}$$

We also call this the local cluster if $\chi$ is understood.

In §6 we prove:

Proposition 5.9.

Let $0<\eta _0 <\eta _1< (1-\log 2)/2$. Then for all sufficiently large $k$ (depending on $\eta _0, \eta _1$), if

$$\begin{equation*} r \coloneq d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta$ with $\eta _0\le \eta \le \eta _1$ then with high probability in the planted model, $|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)$. In symbols,

$$\begin{equation*} \lim _{n\to \infty } {\mathbb{P}}^\chi _n\big (|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)\big )=1. \end{equation*}$$

The rest of this section proves Lemma 1.2 inequality 3 from Proposition 5.9 and the second moment estimates from earlier in this section. So we assume the hypotheses of Proposition 5.9 without further mention.

We say that a coloring $\chi$ is $\sigma$-good if it is equitable and $|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e(\sigma ))$. Let $S_g(\sigma )$ be the set of all $\sigma$-good proper colorings and let $Z_g(\sigma ) = |S_g(\sigma )|$ be the number of $\sigma$-good proper colorings.

We will say a positive function $G(n)$ is sub-exponential in $n$ if

$$\begin{equation*} \lim _{n \to \infty } n^{-1} \log G(n) = 0. \end{equation*}$$

Also we say functions $G$ and $H$ are asymptotic, denoted by $G(n) \sim H(n)$, if $\lim _{n \to \infty }G(n)/H(n) = 1$. Similarly, $G(n) \lesssim H(n)$ if $\limsup _{n \to \infty }G(n)/H(n) \le 1$.

Lemma 5.10.

${\mathbb{E}}^u_n(Z_g) \sim {\mathbb{E}}^u_n(Z_e) = F(n){\mathbb{E}}^u_n(Z)$ where $F(n)$ is sub-exponential in $n$.

Proof.

For brevity, let ${\mathcal{H}} = {\operatorname {Hom}}_{\mathrm{unif}}(\Gamma ,{\operatorname {Sym}}(n))$. Let ${\mathbb{P}}^\chi _n$ be the probability operator in the planted model of $\chi$. By definition,

$$\begin{align*} {\mathbb{E}}^u_n(Z_g) &= |{\mathcal{H}}|^{-1}\sum _{\sigma \in {\mathcal{H}}} Z_g(\sigma ) = |{\mathcal{H}}|^{-1}\sum _{\sigma \in {\mathcal{H}}} \sum _{\chi : V\to \{0,1\}} 1_{S_g(\sigma )}(\chi ) \\ &= \sum _{\chi }{\mathbb{P}}^u_n(\chi \in S_g(\sigma )) \\ &= \sum _{\chi \ \text{equitable}}{\mathbb{P}}^u_n\left(|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)|\chi \ \text{proper}\right){\mathbb{P}}^u_n(\chi \ \text{proper}) \\ &= \sum _{\chi \ \text{equitable}}{\mathbb{P}}^{\chi }_n\left(|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)){\mathbb{P}}^u_n(\chi \ \text{proper}\right) \\ &\sim \sum _{\chi \ \text{equitable}} {\mathbb{P}}^u_n\left(\chi \ \text{proper}\right)= {\mathbb{E}}^u_n(Z_e), \end{align*}$$

where the asymptotic equality $\sim$ follows from Proposition 5.9. The equality ${\mathbb{E}}^u_n(Z_e) = F(n){\mathbb{E}}^u_n(Z)$ holds by Theorem 4.2.

■

Lemma 5.11.

${\mathbb{E}}_n^u(Z_g^2) \leq C(n){\mathbb{E}}_n^u(Z_g)^2$, where $C(n) = C(n,k,r)$ is sub-exponential in $n$.

Proof.

$$\begin{align} {\mathbb{E}}^u_n(Z_g^2) &= |{\mathcal{H}}|^{-1}\sum _{\sigma \in {\mathcal{H}}} \left(\sum _\chi 1_{S_g(\sigma )}(\chi )\right)^2\\ &= |{\mathcal{H}}|^{-1}\sum _{\sigma \in {\mathcal{H}}} \sum _{\chi , {\widetilde{\chi }}}1_{S_g(\sigma )}(\chi )1_{S_g(\sigma )}({\widetilde{\chi }}) \\ &= \sum _{\chi ,{\widetilde{\chi }}}{\mathbb{P}}^u_n\left(\chi \in S_g \ \text{and } {\widetilde{\chi }} \in S_g\right) \\ &= \sum _{\chi ,{\widetilde{\chi }}}{\mathbb{P}}^u_n(\chi \in S_g){\mathbb{P}}^u_n({\widetilde{\chi }} \in S_g | \chi \in S_g) \\ &= \sum _{\chi }{\mathbb{P}}^u_n(\chi \in S_g) {\mathbb{E}}^u_n(Z_g|\chi \in S_g). {\tag{23}} \end{align}$$ For a fixed $\chi \in S_g(\sigma )$ we analyze ${\mathbb{E}}^u_n(Z_g|\chi \in S_g)$ by breaking the colorings into those that are close (i.e. in the local cluster) and those that are far. So let $Z_g(\delta ): {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n)) \to {\mathbb{N}}$ be the number of good proper colorings such that $d_n(\chi ,{\widetilde{\chi }}) = \delta$. (We will also use $Z_e(\delta ) = Z_\chi (\delta )$ for the analogous number of equitable proper colorings). Then

$$\begin{equation} {\mathbb{E}}^u_n(Z_g|\chi \!\in \! S_g) \leq 2{\mathbb{E}}^u_n\left(\sum _{0\leq \delta \leq 2^{-k/2}}\!\!Z_g(\delta ) \Big | \chi \!\in \! S_g\right) + 2{\mathbb{E}}^u_n\left(\sum _{2^{-k/2} < \delta \leq 1/2}\!\!Z_g(\delta )\Big | \chi \!\in \! S_g\right). {\tag{24}} \end{equation}$$

The coefficient $2$ above accounts for the following symmetry: if ${\widetilde{\chi }}$ is a good coloring with $d_n(\chi ,{\widetilde{\chi }})=\delta$ then $1-{\widetilde{\chi }}$ is a good coloring with $d_n(\chi ,1-{\widetilde{\chi }})=1-\delta$. Note that

$$\begin{equation} {\mathbb{E}}^u_n\left(\sum _{0\leq \delta \leq 2^{-k/2}}Z_g(\delta )\Big |\chi \in S_g\right)\leq {\mathbb{E}}^u_n\big (\#{\mathcal{C}}_\sigma (\chi ) |\chi \in S_g\big ) \le {\mathbb{E}}^u_n(Z_e), {\tag{25}} \end{equation}$$

where the last inequality holds by definition of $S_g$.

For colorings not in the local cluster,

$$\begin{align*} & {\mathbb{E}}^u_n\left(\sum _{2^{-k/2} < \delta \leq 1/2} Z_g(\delta )\Big |\chi \in S_g\right) \\ & \qquad \leq {\mathbb{E}}^u_n\left(\sum _{2^{-k/2} < \delta \leq 1/2}Z_e(\delta )\Big |\chi \in S_g\right) \\ & \qquad \leq {\mathbb{E}}^u_n\left(\sum _{2^{-k/2} < \delta \leq 1/2}Z_e(\delta )\Big |\chi \ \text{proper}\right) \frac{{\mathbb{P}}^u_n(\chi \ \text{proper})}{{\mathbb{P}}^u_n(\chi \in S_g)}, \end{align*}$$

where the sum is over all $\delta \in {\mathbb{Z}}[1/n]$ in the given range. By definition and Proposition 5.9,

$$\begin{equation*} \frac{{\mathbb{P}}^u_n(\chi \ \text{proper})}{{\mathbb{P}}^u_n(\chi \in S_g)} = \frac{1}{{\mathbb{P}}^u_n(\chi \in S_g |\chi \ \text{proper} )} = \frac{1}{{\mathbb{P}}^\chi _n\big (|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)\big )}\to 1 \end{equation*}$$

as $n\to \infty$. Since ${\mathbb{E}}^u_n(\cdot | \chi \ \text{proper})= {\mathbb{E}}^\chi _n(\cdot )$, the above inequality now implies

$$\begin{align} {\mathbb{E}}^u_n\left(\sum _{2^{-k/2} < \delta \leq 1/2} Z_g(\delta )\Big |\chi \in S_g\right) &\lesssim \sum _{2^{-k/2} < \delta \leq 1/2} {\mathbb{E}}^{\chi }_n(Z_e(\delta )) \leq C_1\sum _{2^{-k/2}< \delta \leq 1/2} e^{n\psi _0(\delta )}\\ &\le C_1 n e^{nf(d,k)}\le C_2 {\mathbb{E}}^u_n(Z_e), {\tag{26}} \end{align}$$

where the second inequality holds by Theorem 5.1 for some function $C_1 = C_1(n,k,r)$ which is sub-exponential in $n$. The second-to-last inequality holds because the number of summands is bounded by $n$ since $\delta$ is constrained to lie in ${\mathbb{Z}}[1/n]$ and by Proposition 5.8, $\psi _0(\delta ) \le f(d,k)$. The last inequality holds for some function $C_2=C_2(n,k,r)$ that is sub-exponential in $n$ since by Theorem 4.2, $n^{-1} \log {\mathbb{E}}^u_n(Z_e)$ converges to $f(d,k)$.

Combine 24, 25 and 26 to obtain

$$\begin{equation*} {\mathbb{E}}^u_n(Z_g|\chi \in S_g) \le 2(1+C_2) {\mathbb{E}}^u_n(Z_e). \end{equation*}$$

Plug this into 23 to obtain

$$\begin{equation*} {\mathbb{E}}^u_n(Z_g^2) \le 2(1+C_2) {\mathbb{E}}^u_n(Z_e)^2 \sim 2(1+C_2) {\mathbb{E}}^u_n(Z_g)^2, \end{equation*}$$

where the asymptotic $\sim$ holds by Lemma 5.10. This proves the lemma.

■

Corollary 5.12.

Lemma 1.2 inequality 3 is true. That is:

$$\begin{equation*} 0= \inf _{\epsilon >0} \liminf _{n\to \infty } n^{-1} \log \left({\mathbb{P}}_n^{u}\left( \left| n^{-1}\log Z(\sigma ) - f(d,k) \right| < \epsilon \right)\right). \end{equation*}$$

Proof.

By Theorem 4.2,

$$\begin{equation*} n^{-1} \log {\mathbb{E}}_n^{u}(Z(\sigma )) \to f(d,k) \end{equation*}$$

as $n\to \infty$. In particular, for every $\epsilon >0$, for large enough $n$, ${\mathbb{P}}^u_n\left(n^{-1}\log Z(\sigma ) >\right. \left.\vphantom {n^{-1}} f(d,k) + \epsilon \right) < \exp {\left( -\frac{\epsilon }{2} n \right)}$. So it suffices to prove

$$\begin{equation*} 0= \inf _{\epsilon >0} \liminf _{n\to \infty } n^{-1} \log \left({\mathbb{P}}_n^{u}\left( n^{-1}\log Z(\sigma ) \ge f(d,k) - \epsilon \right)\right). \end{equation*}$$

Since $Z(\sigma ) \ge Z_g(\sigma )$, it suffices to prove the same statement with $Z_g(\sigma )$ in place of $Z(\sigma )$. By Lemma 5.10 and Theorem 4.2, $n^{-1}\log \left({\mathbb{E}}_n^{u}[Z_g(\sigma )]\right)$ converges to $f(d,k)$ as $n\to \infty$. So we may replace $f(d,k)$ in the statement above with $n^{-1}\log \left({\mathbb{E}}_n^{u}[Z_g(\sigma )]\right)$. Then we may multiply by $n$ both sides and exponentiate inside the probability. So it suffices to prove

$$\begin{equation} 0= \inf _{\epsilon >0} \liminf _{n\to \infty } n^{-1} \log \left({\mathbb{P}}_n^{u}\left( Z_g(\sigma ) \ge {\mathbb{E}}_n^{u}[Z_g(\sigma )]e^{-n\epsilon } \right)\right). {\tag{27}} \end{equation}$$

By the Paley-Zygmund inequality and Lemma 5.11

$$\begin{equation*} {\mathbb{P}}_n^{u}\left(Z_g(\sigma ) > {\mathbb{E}}_n^{u}[Z_g(\sigma )]e^{-n\epsilon }\right) \ge (1-e^{-n\epsilon })^2 \frac{{\mathbb{E}}_n^{u}[Z_g(\sigma )]^2}{{\mathbb{E}}_n^{u}[Z_g(\sigma )^2]} \ge \frac{1}{C}, \end{equation*}$$

where $C=C(n)$ is sub-exponential in $n$. This implies 27.

■

6. The local cluster

To prove Proposition 5.9, we show that with high probability in the planted model, there is a ‘rigid’ set of vertices with density approximately $1-2^{-k}$. Rigidity here means that any proper coloring either mostly agrees with the planted coloring on the rigid set or it must disagree on a large density subset. Before making these notions precise, we introduce the various subsets, state precise lemmas about them and prove Proposition 5.9 from these lemmas which are proven in the next two sections.

So suppose $G=(V,E)$ is a $k$-uniform $d$-regular hyper-graph and $\chi :V \to \{0,1\}$ is a proper coloring. An edge $e \in E$ is $\chi$-critical if there is a vertex $v \in e$ such that $\chi (v) \notin \chi (e\setminus \{v\})$. If this is the case, then we say $v$ supports $e$ with respect to $\chi$. If $\chi$ is understood then we will omit mention of it. We will apply these notions both to the case when $G$ is the Cayley hyper-tree of $\Gamma$ and when $G=G_\sigma$ is a finite hyper-graph.

For $l \in \{0$, $1$, $2$, $\ldots \}$, define the depth $l$-core of $\chi$ to be the subset $C_l(\chi ) \subset V$ satisfying

$$\begin{equation*} C_0(\chi ) = V, \end{equation*}$$

$$\begin{equation*} C_{l+1}(\chi ) = \{v \in V:\nobreakspace v \text{ supports at least 3 edges } e \text{ such that } e \setminus \{v\} \subset C_l(\chi ) \}. \end{equation*}$$ By induction, $C_{l+1}(\chi ) \subset C_l(\chi )$ for all $l\ge 0$. Also let $C_\infty (\chi ) = \cap _l C_l(\chi )$.

The set $C_{l}(\chi )$ is defined to consist of vertices $v$ so that if $v$ is re-colored (in some proper coloring) then this re-coloring forces a sequence of re-colorings in the shape of an immersed hyper-tree of degree at least 3 and depth $l$. Re-coloring a vertex of $C_{\infty }(\chi )$ would force re-coloring an infinite immersed tree of degree at least 3.

Also define the attached vertices $A_l(\chi ) \subset V$ by: $v \in A_l(\chi )$ if $v \notin C_l(\chi )$ but there exists an edge $e$, supported by $v$ such that $e \setminus \{v\} \subset C_{l-1}(\chi )$. Thus if $v \in A_l(\chi )$ is re-colored then it forces a re-coloring of some vertex in $C_{l-1}(\chi )$. In this definition, we allow $l=\infty$ (letting $\infty - 1 = \infty )$.

In order to avoid over-counting, we also need to define the subset $A'_l(\chi )$ of vertices $v \in A_l(\chi )$ such that there exists a vertex $w \in A_l(\chi )$, with $w \ne v$, and edges $e_v$, $e_w$ supported by $v, w$ respectively such that

(1)

$e_v \setminus \{v\}, e_w \setminus \{w\} \subset C_{l-1}(\chi )$,

(2)

$e_v \cap e_w \ne \emptyset$.

In this definition, we allow $l=\infty$.

We will need the following constants:

$$\begin{equation*} \lambda _0=\frac{ 1 }{ 2^{k-1}-1}, \quad \lambda \coloneq d\lambda _0 =\frac{ d }{ 2^{k-1}-1}. \end{equation*}$$

The significance of $\lambda _0$ is: if $e$ is an edge and $v \in e$ a vertex then $\lambda _0$ is the probability $v$ supports $e$ in a uniformly random proper coloring of $e$. So $\lambda =d\lambda _0$ is the expected number of edges that $v$ supports. For the values of $d$ and $k$ used in the Key Lemma 1.2, $\lambda =\log (2)k + O(k2^{-k})$.

For the next two lemmas, we assume the hypotheses of Proposition 5.9.

Lemma 6.1.

For any $\delta >0$ there exists $k_0$ such that $k \ge k_0$ implies

$$\begin{equation*} \lim _{l \to \infty } \liminf _{n\to \infty } {\mathbb{P}}^\chi _n\left(\frac{|C_l(\chi ) \cup A_l(\chi ) \setminus A'_l(\chi )|}{n} > 1-e^{-\lambda }(1+\delta ) \right) = 1. \end{equation*}$$

Lemma 6.1 is proven in §7.

Definition 7.

Fix a proper 2-coloring $\chi :V \to \{0,1\}$. Let $\rho >0$. A subset $R \subset V$ is $\rho$-rigid (with respect to $\chi$) if for every proper coloring $\chi ': V \to \{0,1\}$, $|\{v\in R: \chi (v) \neq \chi '(v)\}|$ is either less than $\rho |V|$ or greater than $2^{-k/2}|V|$.

Lemma 6.2.

For any $\rho >0$,

$$\begin{equation*} \lim _{l \to \infty } \liminf _{n\to \infty } {\mathbb{P}}^\chi _n\left(C_l(\chi ) \cup A_l(\chi ) \setminus A'_l(\chi ) \text{ is $\rho $-rigid} \right) = 1. \end{equation*}$$

Lemma 6.2 is proven in §8. We can now prove Proposition 5.9:

Proposition 5.9.

Let $0<\eta _0 < \eta _1 < (1-\log 2)/2$. Then for all sufficiently large $k$ (depending on $\eta _0, \eta _1$), if

$$\begin{equation*} r \coloneq d/k= \frac{\log (2)}{2} \cdot 2^k - (1+\log (2))/2 +\eta \end{equation*}$$

for some $\eta$ with $\eta _0\le \eta \le \eta _1$ then with high probability in the planted model, $|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)$. In symbols,

$$\begin{equation*} \lim _{n\to \infty } {\mathbb{P}}^\chi _n\big (|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)\big )=1. \end{equation*}$$

Proof.

Let $0<\rho ,\delta$ be small constants satisfying

$$\begin{equation} \log (2)\delta +H(\rho ,1-\rho ) + \log (2)\rho <(1-2\eta - \log (2))2^{-k}. {\tag{28}} \end{equation}$$

Let $l$ be a natural number. Also let $\sigma :\Gamma \to \operatorname {Sym}(n)$ be a uniform homomorphism and $\chi :[n] \to \{0,1\}$ a proper coloring. To simplify notation, let

$$\begin{equation*} R= C_l(\chi ) \cup A_l(\chi ) \setminus A'_l(\chi ). \end{equation*}$$

By Lemmas 6.1 and 6.2 it suffices to show that if $|R|/n > 1-e^{-\lambda } - \delta$ and $R$ is $\rho$-rigid then $|{\mathcal{C}}_\sigma (\chi )| \leq {\mathbb{E}}^u_n(Z_e)$ (for all sufficiently large $n$). So assume $|R|/n > 1-e^{-\lambda } - \delta$ and $R$ is $\rho$-rigid.

Let $\chi ' \in {\mathcal{C}}_\sigma (\chi )$. By definition, this means $d_n(\chi ',\chi )\le 2^{-k/2}$. Since $R$ is $\rho$-rigid, this implies

$$\begin{equation*} |\{v\in R: \chi (v) \neq \chi '(v)\}| \le \rho n. \end{equation*}$$

Since this holds for all $\chi ' \in {\mathcal{C}}_\sigma (\chi )$, it follows that

$$\begin{equation*} |{\mathcal{C}}_\sigma (\chi )| \le {|R| \choose \rho n} 2^{\rho n} 2^{n - |R|}. \end{equation*}$$

By Stirling’s formula

$$\begin{equation*} n^{-1} \log {|R| \choose \rho n} \le n^{-1} \log {n \choose \rho n} \le H(\rho ,1-\rho ) + O(n^{-1}\log (n)). \end{equation*}$$

Since $|R|/n > 1-e^{-\lambda } - \delta = 1-2^{-k} -\delta + O(k2^{-2k})$,

$$\begin{equation*} n^{-1}\log (2^{n-|R|}) \le \log (2)[2^{-k}+\delta ] + O(k2^{-2k}). \end{equation*}$$

Thus,

$$\begin{equation*} n^{-1}\log |{\mathcal{C}}_\sigma (\chi )| \le \log (2)2^{-k}+\log (2)\delta +H(\rho ,1-\rho ) + \log (2)\rho + O(k2^{-2k} + n^{-1}\log (n)). \end{equation*}$$

On the other hand,

$$\begin{equation*} n^{-1}\log {\mathbb{E}}^u_n(Z_e) = f(d,k) + O(n^{-1}\log (n))= (1-2\eta )2^{-k} + O(2^{-2k})+O(n^{-1}\log (n)) \end{equation*}$$

by Lemma 5.6 and Theorem 4.2.

Therefore, the choice of $\rho ,\delta$ in 28 implies $|{\mathcal{C}}_\sigma (\chi )| \le {\mathbb{E}}^u_n(Z_e)$ for all sufficiently large $n$. This also depends on $k$ being sufficiently large, but the lower bound on $k$ is uniform in $n$.

■

7. A Markov process on the Cayley hyper-tree

Here we study a $\Gamma$-invariant measure $\mu$ on $X$ which is, in a sense, the limit of the planted model. We will define it by specifying its values on cylinder sets.

Let $D \subset \Gamma$ be a connected finite union of hyper-edges. Let $\xi \in \{0,1\}^{D}$ be a proper coloring. We define $C(\xi )\subset X$ to be the set of proper colorings $\xi ' \in X$ with $\xi ' \upharpoonright D = \xi$ (where $\upharpoonright$ means “restricted to”). We set $\mu (C(\xi ))$ equal to the reciprocal of the number of proper colorings of $D$. In particular, if $\xi ' \in \{0,1\}^D$ is another proper coloring of $D$, then $\mu (C(\xi ))=\mu (C(\xi '))$.

Because $X$ is totally disconnected, any Borel probability measure on $X$ is determined by its values on clopen subsets (since these generate the topology). Since every clopen subset is a finite union of cylinder sets of the form above, Kolmogorov’s Extension Theorem implies the existence of a unique Borel probability $\mu$ on $X$ satisfying the aforementioned equalities.

Note this measure has the following Markov property. Let $x = (x_g)_{g \in G}$ be a random element of $X$ with law $\mu$. Let $v \in \Gamma$ and let $e \subset \Gamma$ be a hyperedge containing $v$. Let $\operatorname {Past}(e,v)$ be the set of all $g \in \Gamma$ such that every path in the Cayley hyper-tree from $g$ to an element of $e$ passes through $v$. In particular, $e \cap \operatorname {Past}(e,v) = \{v\}$. Then the distribution of $(x_g)_{g \in e \setminus \{v\}}$ conditioned on $\{x_g:\nobreakspace g \in \operatorname {Past}(e,v)\}$ is uniformly distributed on the set of all colorings $y:(e\setminus \{v\}) \to \{0,1\}$ such that there exists some $h \in e \setminus \{v\}$ with $y(h) \ne x(v)$.

7.1. Local convergence

We will prove the following lemma.

Lemma 7.1.

Let $\chi : V \to \{0,1\}$ be an equitable coloring with $|V|=n$. If $B \subseteq X$ is clopen, then for every $\epsilon > 0$

$$\begin{align*} \lim _{n \to \infty } {\mathbb{P}}^\chi _n \left( \left| \frac{1}{n} \sum _{v \in V} \mathbb{1}_{B}(\Pi _v^{\sigma _n}(\chi )) - \mu (B) \right| > \epsilon \right) = 0. \end{align*}$$

To prove this lemma we will first show that if $f_n: {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n)) \to {\mathbb{R}}$ is the function

$$\begin{equation*} f_n(\sigma _n) : = \frac{1}{n} \sum _{v\in V} \mathbb{1}_{B}(\Pi _v^{\sigma _n}(\chi )), \end{equation*}$$

then $f_n$ concentrates about its expectation using Theorem B.1, and then we will show that this expectation is given by $\mu (B)$.

Proposition 7.2.

We have

$$\begin{align*} \lim _{n \to \infty } {\mathbb{P}}^\chi _n\left( |f_n - {\mathbb{E}}^\chi _n[f_n]| > \epsilon \right) = 0. \end{align*}$$

Proof.

For $g \in \Gamma$, let $\operatorname {pr}_g:X \to \{0,1\}$ be the projection map $\operatorname {pr}_g(x)=x_g$. For $D \subset \Gamma$, let ${\mathcal{F}}_D$ be the smallest Borel sigma-algebra such that $\operatorname {pr}_g$ is ${\mathcal{F}}_D$-measurable for every $g \in D$.

Since every clopen subset $B$ of $X$ is a finite union of cylinder sets, the function $\mathbb{1}_{B}$ is ${\mathcal{F}}_D$-measurable for some finite set $D \subset \Gamma$.

We will use the normalized Hamming metrics $d_{{\operatorname {Sym}}(n)}$ and $d_{{\operatorname {Hom}}}$ on ${\operatorname {Sym}}(n)$ and ${\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ respectively. These are defined in the beginning of Appendix B. We claim $f_n$ is $L$-Lipschitz for some $L < \infty$. Let $\sigma , \sigma ' \in {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$. Because $\mathbb{1}_{B}$ is ${\mathcal{F}}_D$-measurable,

$$\begin{align*} |f_n(\sigma ) - f_n(\sigma ')| &\leq n^{-1} \#\{v \in [n] : \chi (\sigma (\gamma ^{-1})(v)) \neq \chi (\sigma '(\gamma ^{-1})(v)) \text{ for some } \gamma \in D\} \\ & \leq n^{-1} \# \{ v \in [n] : \sigma (\gamma ^{-1})(v) \neq \sigma '(\gamma ^{-1})(v) \text{ for some } \gamma \in D\} \\ & \leq \sum _{\gamma \in D} d_{{\operatorname {Sym}}(n)}(\sigma (\gamma ^{-1}),\sigma '(\gamma ^{-1})). \end{align*}$$

Now $d_{{\operatorname {Sym}}(n)}$ is both left and right invariant. So

$$\begin{align*} d_{{\operatorname {Sym}}(n)}(gh,g'h') & \leq d_{{\operatorname {Sym}}(n)}(gh,gh') + d_{{\operatorname {Sym}}(n)}(gh',g'h') \\ & = d_{{\operatorname {Sym}}(n)}(h,h') + d_{{\operatorname {Sym}}(n)}(g,g') \end{align*}$$

for any $g,g',h,h' \in {\operatorname {Sym}}(n)$. Furthermore we immediately have for any $1 \leq i \leq d$ that $d_{{\operatorname {Sym}}(n)}(\sigma (s_i),\sigma '(s_i)) \leq d_{{\operatorname {Hom}}}(\sigma ,\sigma ')$. Together these imply $d_{{\operatorname {Sym}}(n)}(\sigma (\gamma ),\sigma '(\gamma )) \le |\gamma | d_{{\operatorname {Hom}}}(\sigma ,\sigma ')$ for any $\gamma \in \Gamma$ where $|\gamma |$ is the distance from $\gamma$ to the identity in the word metric on $\Gamma$. Thus if we take $L = \sum _{\gamma \in D} |\gamma | < \infty$ we see that $|f_n(\sigma ) - f_n(\sigma ')|\le L d_{{\operatorname {Hom}}}(\sigma ,\sigma ')$ as desired.

The Proposition now follows from Theorem B.1.

■

To finish the proof of Lemma 7.1, it now suffices to show the expectation of $f_n$ with respect to the planted model converges to $\mu (B)$ as $n\to \infty$. We will prove this by an inductive argument, the inductive step of which is covered in the next lemma.

Lemma 7.3.

Let $D \subset \Gamma$ be either a singleton or a connected finite union of hyperedges containing the identity. Let $\xi \in \{0,1\}^{D}$ be a proper coloring. Let $F_{D,\xi ,v}\subset {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ be the event that $\Pi _{v}^{\sigma _n}(\chi ) \upharpoonright D = \xi \upharpoonright D$. Let $Q(D)$ be the number of proper colorings of $D$. Then

$$\begin{align} \lim _{n \to \infty } \sup _{v \in \chi ^{-1}(\xi (1_\Gamma ))} \left| {\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right) - \frac{2}{Q(D)} \right| = 0. {\tag{29}} \end{align}$$

Remark 8.

The factor of $2$ in $\frac{2}{Q(D)}$ is there to account for the fact that we are requiring $v \in \chi ^{-1}(\xi (1_\Gamma ))$.

Proof.

The statement is immediate if $D=\{1_\Gamma \}$ is a singleton. For induction we assume that the statement is true for some finite $D \subset \Gamma$. Let $D' \supset D$ be a connected union of hyper-edges such that there exists a unique hyper-edge $e$ with $D' = D \cup e$. By induction, it suffices to prove the statement for $D'$.

Note by symmetry that ${\mathbb{P}}^\chi _n(F_{D,\xi ,v})$ is the same for all $v \in \chi ^{-1}(\xi (1_\Gamma ))$. Let us denote this common value by $c_{D,\xi }$. Define $A_{D,\xi } = \{ (v,\sigma ) : v \in V, \sigma \in F_{D,\xi ,v}\}$. If $g \in D$ then $(v,\sigma ) \mapsto (\sigma (g^{-1}) v,\sigma )$ is a bijection from $A_{D,\xi }$ to $A_{g^{-1}D,g^{-1}\xi }$. This implies

$$\begin{align*} \frac{n}{2} c_{D,\xi } \left| {\operatorname {Hom}}_\chi (\Gamma ,{\operatorname {Sym}}(n)) \right| &= \left| A_{D,\xi } \right| \\ & = \left| A_{g^{-1}D,g^{-1}\xi } \right| \\ & = \frac{n}{2} c_{g^{-1} D, g^{-1} \xi } \left| {\operatorname {Hom}}_\chi (\Gamma ,{\operatorname {Sym}}(n)) \right|. \end{align*}$$

Thus $c_{g^{-1} D, g^{-1} \xi } = c_{D,\xi }$. After replacing $D'$ with $\gamma ^{-1} D'$ where $\gamma \in e \cap D$ is the unique element in $e \cap D$, we may therefore assume without loss of generality that $e \cap D = \{1_\Gamma \}$. By symmetry we may also assume $\xi (1_\Gamma )=1$ and $e = \{s_1^i:\nobreakspace i=0$, $\cdots$, $k-1\}$ is the hyper-edge generated by $s_1$.

For any subset $W \subset \Gamma$, let $E_{{W, v}}$ be the event that $\sigma _n(g^{-1})({v}) \neq \sigma _n(g'^{-1})({v})$ for any $g, g' \in W$ with $g \neq g'$. Since the planted model is a random sofic approximation, by Lemma 3.1 we have ${\mathbb{P}}^\chi _n(E_{D \cup e, v}) = 1 - o_n(1)$ uniformly in $v$. We will show that

$$\begin{align} \lim _{n \to \infty } \sup _{v \in \chi ^{-1}(1)} \left| {\mathbb{P}}^\chi _n\left( F_{e,\xi ,v} \bigg | F_{D,\xi ,v}, E_{D \cup e, v} \right) - \frac{1}{2^{k-1}-1} \right| = 0. {\tag{30}} \end{align}$$

Next we show how to finish the lemma assuming 30. We claim that $Q(D\cup e)=Q(D)(2^{k-1}-1)$. To see this, observe that if $\xi '$ is a proper coloring of $D$ and $\xi ''$ is any coloring of $e \setminus \{1_\Gamma \}$ then the concatenation $\xi ' \sqcup \xi ''$ is a proper coloring of $D \cup e$ unless $\xi ''(g)=\xi '(1_\Gamma )$ for all $g \in e \setminus \{1_\Gamma \}$. Since $|e \setminus \{1_\Gamma \}|=k-1$, this implies that every proper coloring of $D$ admits $2^{k-1}-1$ proper extensions to $D \cup e$. So $Q(D\cup e)=Q(D)(2^{k-1}-1)$ as claimed.

Since $F_{D\cup e,\xi ,v} = F_{e,\xi ,v} \cap F_{D,\xi ,v}$,

$$\begin{align*} {\mathbb{P}}^\chi _n\left( F_{D\cup e,\xi ,v} \right) &= {\mathbb{P}}^\chi _n\left( F_{e,\xi ,v} \bigg | F_{D,\xi ,v} \right) {\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right) \\ &= {\mathbb{P}}^\chi _n\left( F_{e,\xi ,v} \bigg | F_{D,\xi ,v}, E_{D \cup e, v} \right) {\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right) + o_n(1). \end{align*}$$

The lemma now follows from the inductive hypothesis, 30 and $Q(D \cup e) = Q(D)(2^{k-1}-1)$.

It now suffices to prove 30. Let $D_j$ denote the union of all subsets $\{g s_j^i : i = 0$, $\cdots$, $k-1\}$ over all $g \in D$ such that $\{g s_j^i : i = 0$, $\cdots$, $k-1\} \subseteq D$. That is, $D_j$ is the union of all hyperedges generated by $s_j$ which lie completely within $D$. Because $e = \{s_1^i:\nobreakspace i=0$, $\cdots$, $k-1\}$, $e \cap D_1 = \emptyset$. Multiplication by $s_j$ on the right preserves $D_j$.

Fix $v \in V=\{1$, …, $n\}$ and consider an injective function $h : D \to V$ such that $h(1_\Gamma ) = v$ and $\chi \left( h\left( e' \right) \right) = \{0,1\}$ for all hyper-edges $e' \in D$. Let $N(\chi ,h)$ be the set of $\sigma \in {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ such that $\sigma (g^{-1})v = h(g)$ for all $g \in D$. By definition,

$$\begin{align*} {\mathbb{P}}^\chi _n \left( \sigma _n(g^{-1})(v) = h(g)\nobreakspace \forall g \in D \right) & =\frac{|N(\chi ,h)|}{|{\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))|}. \end{align*}$$

For each $j \in \{1$, …, $d\}$, let $N_j(\chi ,h)$ be the set of permutations $\pi _j \in {\operatorname {Sym}}(n)$ such that

(1)

the orbit-partition of $\pi _j$ is a $k$-partition which is properly colored by $\chi$,

(2)

$h(gs_j) = \pi _j^{-1} h(g)$ for all $g \in D \cap Ds_j^{-1}$.

We claim that the map

$$\begin{equation*} N(\chi ,h) \mapsto N_1(\chi ,h) \times \cdots \times N_d(\chi ,h) \end{equation*}$$

that sends $\sigma$ to $(\sigma (s_1)$, …, $\sigma (s_d))$ is a bijection.

The fact that it is injective is immediate since $\Gamma$ is generated by $s_1$, …, $s_d$. In order to prove that it is surjective, fix elements $\pi _j \in N_j(\chi ,h)$ for all $j$. Define $\sigma \in {\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))$ by $\sigma (s_j) = \pi _j$. It suffices to check that $\sigma (g^{-1})(v) = h(g)\nobreakspace \forall g \in D$. By induction on the number of edges in $D$, it suffices to assume that the equation $\sigma (g^{-1})(v) = h(g)$ holds for some $g \in D \cap Ds_j^{-1}$ and prove $\sigma ((gs_j)^{-1})(v) = h(gs_j)$. This follows from:

$$\begin{equation*} \sigma ((gs_j)^{-1})(v) =\sigma (s_j^{-1}) \sigma (g^{-1})(v) = \pi _j^{-1} h(g) = h(gs_j). \end{equation*}$$

This proves the claim. Therefore,

$$\begin{align} {\mathbb{P}}^\chi _n \left( \sigma _n(\cdot )^{-1}(v) \upharpoonright D = h \right) & = \frac{ \prod _{j =1 }^d |N_j(\chi ,h)|}{|{\operatorname {Hom}}_{\chi }(\Gamma ,\operatorname {Sym}(n))|}. {\tag{31}} \end{align}$$

Let $H_D = \{ h : D \to V : h \text{ is injective, } \chi (h(g)) = \xi (g)\nobreakspace \forall g\in D\text{, and } h(1_\Gamma ) = v\}$. We have

$$\begin{align*} {\mathbb{P}}^\chi _n(F_{D,\xi ,v}, E_{D, v}) & = \sum _{h \in H_D} {\mathbb{P}}^\chi _n(\sigma _n(\cdot )^{-1}(v) \upharpoonright D = h). \end{align*}$$

Similarly

$$\begin{align*} {\mathbb{P}}^\chi _n(F_{D\cup e,\xi ,v}, E_{D \cup e, v}) & = \sum _{h' \in H_{D \cup e}} {\mathbb{P}}^\chi _n(\sigma _n(\cdot )^{-1}(v) \upharpoonright D \cup e = h'). \end{align*}$$

Each $h \in H_D$ is the restriction to $D$ of

$$\begin{align} (m-1)! \binom{n/2 - \# \xi ^{-1}(1) \cap D}{m-1}(k-m)! \binom{n/2 - \#\xi ^{-1}(0) \cap D}{k-m} {\tag{32}} \end{align}$$

distinct $h' \in H_{D\cup e}$ where $m=|\xi ^{-1}(1) \cap e|$. We can express

$$\begin{align*} {\mathbb{P}}^\chi _n(F_{e,\xi ,v} | F_{D,\xi ,v}, E_{D \cup e, v}) & = \frac{{\mathbb{P}}^\chi _n(F_{D \cup e, \xi ,v}, E_{D \cup e, v})}{{\mathbb{P}}^\chi _n(F_{D,\xi ,v}, E_{D \cup e, v})} \\ & = \frac{{\mathbb{P}}^\chi _n(F_{D \cup e, \xi ,v}, E_{D \cup e, v})}{{\mathbb{P}}^\chi _n(F_{D,\xi ,v}, E_{D, v})} +o_n(1)\\ & = \frac{\sum _{h' \in H_{D\cup e}} {\mathbb{P}}^\chi _n(\sigma _n(\cdot )^{-1}(v) \upharpoonright D \cup e = h')}{\sum _{h \in H_D} {\mathbb{P}}^\chi _n(\sigma _n(\cdot )^{-1}(v)\upharpoonright D = h)} +o_n(1) \\ & = \frac{\sum _{h' \in H_{D\cup e}} \prod _{j=1}^d |N_j(\chi ,h')|}{\sum _{h \in H_D} \prod _{j=1}^d |N_j(\chi ,h)|} + o_n(1), \end{align*}$$

where the $o_n(1)$ term follows from the inductive hypothesis and the fact that ${\mathbb{P}}^\chi _n(E_{D,v}) \ge {\mathbb{P}}^\chi _n(E_{D\cup e,v}) = 1-o_n(1)$.

If $h_1, h_2 \in H_D$ then $\chi (h_1(g)) = \xi (g) = \chi (h_2(g))$ for all $g\in D$. Observe that $|N_j(\chi ,h_1)| = |N_j(\chi ,h_2)|$. This follows by conjugating by a permutation in ${\operatorname {Sym}}(n,k)$ which preserves the color classes of $\chi$ and which maps $h_1(g)$ to $h_2(g)$ for each $g \in D$. Similarly, if $h'_1, h'_2 \in H_{D\cup e}$ then $|N_j(\chi ,h'_1)| = |N_j(\chi ,h'_2)|$. Therefore,

$$\begin{align*} {\mathbb{P}}^\chi _n(F_{e,\xi ,v} | F_{D,\xi ,v}, E_{D \cup e, v}) &= \frac{|H_{D\cup e}| \prod _{j=1}^d |N_j(\chi ,h')|}{| H_D | \prod _{j=1}^d |N_j(\chi ,h)|} + o_n(1) \end{align*}$$

for any $h\in H_D$ and $h' \in H_{D \cup e}$.

Next we choose $h' \in H_{D\cup e}$ and $h \in H_D$ so that $h'$ extends $h$. Note $|N_j(\chi ,h')| = |N_j(\chi ,h)|$ for all $j \ne 1$ because $D_j = (D \cup e)_j$. Therefore,

$$\begin{align} & {\mathbb{P}}^\chi _n(F_{e,\xi ,v} | F_{D,\xi ,v}, E_{D \cup e, v}) \\ &\quad = \frac{|H_{D\cup e}| |N_1(\chi ,h')|}{| H_D | |N_1(\chi ,h)|} + o_n(1) \\ & \quad = \frac{|N_1(\chi ,h')|}{ |N_1(\chi ,h)|} (m-1)! \binom{n/2 - \# \xi ^{-1}(1) \cap D}{m-1}(k-m)! \binom{n/2 - \#\xi ^{-1}(0) \cap D}{k-m} + o_n(1) \\ & \quad \sim \frac{|N_1(\chi ,h')|}{ |N_1(\chi ,h)|} (n/2)^{k-1}, {\tag{33}} \end{align}$$

where the second equality uses 32. Here we are using the notation $f(n) \sim g(n)$ to mean $\lim _{n\to \infty } \frac{f(n)}{g(n)}=1$.

To compute $|N_1(\chi ,h)|$, let

$$\begin{equation*} T_{D,n} \!=\!\left\{ \vec{t} \in [0,1]^{k+1} \!:\! t_0 \!=\! t_k \!=\! 0, \sum _i t_i \!=\! \frac{1}{k} , \sum _i i t_i \!=\! \frac{\# \chi ^{-1}(1) \setminus h(D_1)}{\# V \setminus h(D_1)}, (n - \# D_1) t_i \in {\mathbb{Z}}\right\} \end{equation*}$$

be the set of possible types of orbit-partitions of permutations of $V \setminus h(D_1)$ that contribute to the count $|N_1(\chi ,h)|$. To be precise, if $\vec{t} \in T_{D,n}$ then there is a $k$-partition of $V \setminus h(D_1)$ such that the number of parts $P$ of the partition with $|P \cap \chi ^{-1}(1)|=i$ is $t_i (n- \#D_1)$.

If we fix ${\vec{t}} \in T_{D,n}$ then the number of permutations whose orbit partition has type ${\vec{t}}$ is

$$\begin{equation*} (k-1)!^{ (n-\#D_1)/k}\frac{(n/2-\#\xi ^{-1}(1)\cap D_1)!(n/2-\#\xi ^{-1}(0)\cap D_1)!}{ \prod _{j=0}^{k} j!^{t_j(n-\#D_1)}(k-j)!^{t_j(n-\#D_1)} (t_j(n-\#D_1))!}, \end{equation*}$$

where we have used 8. It follows that

$$\begin{align*} |N_1(\chi ,h)| = {} & (k-1)!^{(n-\#D_1)/k} \frac{(n/2 - \#\xi ^{-1}(1) \cap D_1 )! (n/2 - \#\xi ^{-1}(0) \cap D_1)!}{\left( \frac{n - \#D_1}{k} \right)!} \\ & \times \sum _{\vec{t} \in T_{D,n}} S_{D,n}({\vec{t}}), \end{align*}$$

where

$$\begin{align} S_{D,n}({\vec{t}}) &= \frac{((n-\#D_1)/k)!}{\prod _{i=1}^{k-1} i!^{t_i (n - \# D_1)} (k-i)!^{t_i (n - \# D_1)} (t_i (n - \# D_1))!}. {\tag{34}} \end{align}$$

So

$$\begin{align*} \frac{|N_1(\chi ,h')|}{ |N_1(\chi ,h)|} &\sim \frac{(n/k)}{(k-1)!(n/2)^{k} } \frac{\sum _{\vec{t} \in T_{D\cup e,n}} S_{D \cup e,n}({\vec{t}})}{\sum _{\vec{t} \in T_{D,n}} S_{D,n}({\vec{t}})}. \end{align*}$$

We plug this into 33 to obtain

$$\begin{align} \lim _{n \to \infty } {\mathbb{P}}_n^\chi (F_{e,\xi ,v} | F_{D,\xi ,v}, E_{D \cup e, v}) & = \lim _{n \to \infty } \frac{2}{k! } \frac{\sum _{\vec{t} \in T_{D\cup e,n}} S_{D \cup e,n}({\vec{t}})}{\sum _{\vec{t} \in T_{D,n}} S_{D,n}({\vec{t}})}. {\tag{35}} \end{align}$$

Define $t^* \in [0,1]^{k+1}$ by $t^*_0 = t^*_k = 0$ and $t^*_i = \frac{1}{k(2^k-2)} \binom{k}{i}$ for $0<i<k$. We establish asymptotic estimates of the sum of $S_{D,n}(\vec{t})$ in Lemma 7.4 and show that it suffices to sum over a small ball around $t^*$.

Recall $m=|\xi ^{-1}(1) \cap e|$. Let ${\tilde{T}}_{D,n} = \{{\vec{t}} \in T_{D,n}: t_m >0\}$. We define $f_n : {\tilde{T}}_{D,n} \to T_{D \cup e, n}$ by

$$\begin{align*} f_n(\vec{t})_j = \begin{cases} \frac{(n-\# D_1)t_j-1}{n-\#D_1 - k} \text{ if } j = m \\ \frac{n - \# D_1}{ n - \#D_1 - k} t_j \text{ if } j \neq m \end{cases}. \end{align*}$$

Because $e \cap D_1 = \emptyset$, if $\vec{t} \in {\tilde{T}}_{D,n}$ then $f_n(\vec{t}) \in T_{D\cup e,n}$.

We claim that for any $\delta >0$ there exists an $N\coloneq N(\delta )$ and $\delta ' > 0$ such that for $n > N$, $T_{D\cup e,n} \cap B_{\delta '}(t^*) \subseteq f_n({\tilde{T}}_{D,n} \cap B_\delta (t^*))$. This follows from observing that $f_n$ is invertible and that $d(f_n({\vec{t}}),{\vec{t}}) \leq \frac{k^2}{n-\#D_1-k}$. By Lemma 7.4 we have

$$\begin{align} \lim _{n \to \infty } \frac{\sum _{\vec{t} \in T_{D \cup e, n}} S_{D \cup e, n}(\vec{t})}{\sum _{\vec{t} \in T_{D,n}} S_{D,n}(\vec{t})} = \lim _{n \to \infty } \frac{\sum _{\vec{t} \in \tilde{T}_{D,n} \cap B_\delta (t^*)} S_{D \cup e, n}(f_n(\vec{t}))}{ \sum _{\vec{t} \in T_{D,n} \cap B_\delta (t^*)} S_{D,n}(\vec{t}) }. {\tag{36}} \end{align}$$

Furthermore, since $1 \leq m \leq k-1$ and $t^*_m > 0$, for $\delta > 0$ sufficiently small we have $\tilde{T}_{D,n} \cap B_\delta (t^*) = T_{D,n} \cap B_\delta (t^*)$. Because $\#(D \cup e)_1 =\#D_1 +k$, the ratio $\frac{S_{D \cup e, n}(f_n(\vec{t}))}{S_{D,n}(\vec{t})}$ simplifies to

$$\begin{align*} \frac{k}{n-\#D_1} m!(k-m)! t_m(n-\#D_1) = \frac{k (k!)}{\binom{k}{m}} t_m. \end{align*}$$

In particular, at $t^*$ we obtain

$$\begin{align*} \frac{S_{D \cup e, n}(f_n(t^*))}{S_{D,n}(t^*)} = \frac{k!}{2^{k} - 2}. \end{align*}$$

Suppose $\vec{t} \in B_\delta (t^*)$. Then $|t_m - t_m^*| < \delta$. So

$$\begin{align*} \left|\frac{S_{D\cup e,n}(f_{n}(\vec{t}))}{S_{D,n}(\vec{t})} - \frac{k!}{2^{k}-2}\right| & = \left| \frac{S_{D \cup e, n}(f_n(\vec{t}))}{S_{D,n}(\vec{t})} - \frac{k!}{2^{k} - 2} \right| \\ & = \frac{k (k!)}{\binom{k}{m}} |t_m-t^*_m|\le k! \delta . \end{align*}$$

Since $\delta$ is arbitrary, this and 36 imply

$$\begin{align*} \lim _{n \to \infty } \frac{\sum _{\vec{t} \in T_{D \cup e, n}} S_{D \cup e, n}(\vec{t})}{\sum _{\vec{t} \in T_{D,n}} S_{D,n}(\vec{t})} = \frac{k!}{2^k - 2}. \end{align*}$$

We plug this into 35 to obtain

$$\begin{align*} \lim _{n \to \infty } {\mathbb{P}}_n^\chi (F_{e,\xi ,v} | F_{D,\xi ,v}, E_{D \cup e, v}) & = \frac{1}{2^{k-1}-1}. \end{align*}$$ ■

Lemma 7.4.

For any $\delta > 0$ we have

$$\begin{align*} \lim _{n \to \infty } \frac{\sum _{\vec{t} \in T_{D,n} \cap B_{\delta }(t^*)} S_{D,n}(\vec{t})}{\sum _{\vec{t} \in T_{D,n}} S_{D,n}(\vec{t})} = 1. \end{align*}$$

Proof.

We use the following general consequence of Stirling’s formula: let $l \in {\mathbb{N}}$, ${\vec{t}} \in [0,1]^l$ with $\sum _i t_i = 1$. Let ${\vec{t}}^{(n)}$ be any sequence in $[0,1]^l$ such that $n{\vec{t}}^{(n)} \in {\mathbb{N}}^l$ and ${\vec{t}}^{(n)} \to {\vec{t}}$ as $n\to \infty$. If ${\vec{t}}^{(n)} = (t_{n,i})_{i=1}^l$ then $\lim _{n \to \infty } n^{-1} \log \binom{n}{nt_{n,1},\ldots ,nt_{n,l}} = H({\vec{t}})$.

By 34

$$\begin{equation*} S_{D,n}(\vec{t}) = \binom{(n-\#D_1)/k}{t_{n,1}(n-\#D_1),\ldots ,t_{n,k-1}(n-\#D_1)} \left(\prod _{i=1}^{k-1} \binom{k}{i}^{t_i(n-\#D_1)} \right) k!^{-(n-\#D_1)/k}. \end{equation*}$$

By setting $N=(n-\#D_1)/k$, we obtain

$$\begin{align*} &\lim _{n\to \infty } n^{-1} \log \binom{(n-\#D_1)/k}{t_{n,1}(n-\#D_1),\ldots ,t_{n,k-1}(n-\#D_1)} \\ &\qquad = k^{-1}\lim _{n\to \infty } N^{-1} \log \binom{N}{t_{n,1}kN,\ldots ,t_{n,k-1}kN} \\ & \qquad = k^{-1} H(k{\vec{t}}) = - \sum _{i=0}^k t_i \log (kt_i) = H({\vec{t}}) -k^{-1} \log (k). \end{align*}$$

We thus have:

$$\begin{align*} \limsup _{n \to \infty } \sup _{\vec{t} \in T_{D,n}} \left| \frac{1}{n} \log S_{D,n}(\vec{t}) - \psi ({\vec{t}}) \right|= 0, \end{align*}$$

where $\psi$ is given by

$$\begin{align*} \psi ({\vec{t}}) \coloneq -\frac{1}{k} \log (k(k)!) + H(\vec{t}) + \sum _{i=0}^{k} t_i \log \binom{k}{i} . \end{align*}$$

Note that $\psi$ does not depend on $n$ or $D$. Furthermore $\psi$ is continuous and strictly concave. By the method of Lagrange multipliers (see §4.2) its maximum on $M\coloneq \{x \in [0,1]^{k+1} : x_0 = x_k = 0, \sum _i x_i = \frac{1}{k} \}$ occurs at $t^*$. In particular given $\delta > 0$ there is some $0 < \eta < \delta$ such that

$$\begin{align*} \inf _{x \in M \cap B_{\eta }(t^*)} \psi (x) - \sup _{x \in M \setminus B_{\delta }(t^*)} \psi (x) > 0. \end{align*}$$

We claim that $B_\eta (t^*) \cap T_{D,n} \subseteq B_\eta (t^*) \cap M$ is non-empty for sufficiently large $n$. Since $\# T_{D,n} \leq n^k$ this claim and standard arguments involving the exponential growth of $S_{D,n}(t)$ imply the lemma.

To prove the claim, we exhibit a member of $B_\eta (t^*) \cap T_{D,n}$ in a series of three steps. First, let $t^{(1)} \in {\mathbb{R}}^{k+1}$ be defined by $t^{(1)}_i = \frac{\lfloor t^*_i(n-\#D_1) \rfloor }{n-\#D_1}$ for each $0 \leq i \leq k$. This satisfies the integrality condition, that is $(n-\#D_1) t_i^{(1)} \in {\mathbb{Z}}$ for all $i$. Furthermore $|t^* - t^{(1)}| \leq \sum _{i = 0}^{k} |t^*_i - t^{(1)}_i| \leq \frac{k-1}{n - \# D_1}$.

Second, define $t^{(2)} \in {\mathbb{R}}^{k+1}$ by

$$\begin{align*} t^{(2)}_i = \begin{cases} t^{(1)}_1 + \left( \frac{1}{k} - \sum _{j=1}^{k-1} t^{(1)}_j \right) \text{ if } i =1 \\ t^{(1)}_i \text{ otherwise} \end{cases}. \end{align*}$$

Since $\frac{n-\#D_1}{k} \in {\mathbb{Z}}$ and $(n-\#D_1) t_i^{(1)} \in {\mathbb{Z}}$ for each $i$ we maintain the integrality condition, and $\sum _i t_i^{(2)} = \frac{1}{k}$. Furthermore

$$\begin{align*} \left| t^{(2)} - t^{(1)} \right| \leq \left| \frac{1}{k} - \sum _{i=1}^{k-1} t_i^{(1)} \right| & = \left| \sum _{i=0}^k (t_i^* - t_i^{(1)}) \right| \leq \sum _{i=0}^k \left| t_i^* - t_i^{(1)} \right| \leq \frac{k-1}{n - \#D_1}. \end{align*}$$

Finally let $\Delta = \frac{\#\chi ^{-1}(1) \setminus h(D_1)}{n - \# D_1} - \sum _{i=0}^k i t^{(2)}_i$. Define $t^{(3)} \in {\mathbb{R}}^{k+1}$ by

$$\begin{align*} t_i^{(3)} = \begin{cases} t_1^{(2)} - \Delta \text{ if } i = 1 \\ t_2^{(2)} + \Delta \text{ if } i = 2 \\ t_i^{(2)} \text{ otherwise} \end{cases}. \end{align*}$$

We claim $t^{(3)} \in B_\eta (t^*) \cap T_{D,n}$ for $n$ sufficiently large. First $t^{(3)}_0 = t^{(2)}_0 = t^{(1)}_0 = t^*_0 = 0$, with the same equalities holding for $t^{(3)}_k$. We have $t^{(3)}_i (n-\#D_1) \in {\mathbb{Z}}$ since $t^{(2)}_i(n-\#D_1) \in {\mathbb{Z}}$ for each $i$ and $\Delta (n-\#D_1) \in {\mathbb{Z}}$. We also have $\sum _i t^{(3)}_i = \sum _i t^{(2)}_i = \frac{1}{k}$. Furthermore $\sum _i i t_i^{(3)} = \sum _i i t_i^{(2)} + 2\Delta - \Delta = \frac{\chi ^{-1}(1) \setminus h(D_1)}{n - \#D_1}$. Finally by repeated application of the triangle inequality

$$\begin{align*} |t^* - t^{(3)}| \leq \frac{k-1}{n - \#D_1} + \frac{k-1}{n-\#D_1} + 2|\Delta |. \end{align*}$$

We show that $|\Delta |$ is small for $n$ sufficiently large. This will not only imply that $t^{(3)} \in B_\eta (t^*)$, but also that $t^{(3)}_i \in [0,1]$ for each $i$. Note that

$$\begin{equation*} \frac{n/2 - \#D_1}{n} \leq \frac{\#\chi ^{-1}(1) \setminus h(D_1)}{n - \# D_1} \leq \frac{n/2}{n - \#D_1} = \frac{(n-\#D_1)/2 + \#D_1/2}{n-\#D_1}. \end{equation*}$$

This implies $\left| \frac{\#\chi ^{-1}(1) \setminus h(D_1)}{n - \#D_1} - \frac{1}{2} \right| \leq \max \{\frac{\#D_1}{n}, \frac{\#D_1}{2(n-\#D_1)}\}$. Thus

$$\begin{align*} \left| \Delta \right| & \leq \left| \frac{\#\chi ^{-1}(1) \setminus h(D_1)}{n - \# D_1} - \frac{1}{2} \right| + \left| \frac{1}{2} - \sum _{i=0}^{k} i t^{(2)}_i \right| \\ & \leq \max \left\{\frac{\#D_1}{n}, \frac{\#D_1}{2(n-\#D_1)}\right\} + \left| \sum _{i=0}^k it_i^* - \sum _{i=0}^k i t_i^{(1)} \right| + \left| \sum _{i=0}^k i t_i^{(1)} - \sum _{i=0}^k i t_i^{(2)} \right| \\ & \leq \max \left\{\frac{\#D_1}{n}, \frac{\#D_1}{2(n-\#D_1)}\right\} + \frac{2(k-1)^2}{n-\#D_1}. \end{align*}$$

As $k$ and $\# D_1$ are fixed, we have $|t^*-t^{(3)}| < \eta$ for large enough $n$. Since $t^*_i \in (0,1)$ for each $1 \leq i \leq k-1$ we have $|t^{(3)}_i - t^*_i| \leq |t^{(3)} - t^*|$. Thus for sufficiently large $n$ we will also have $t^{(3)}_i \in (0,1)$ for each $1 \leq i \leq k-1$. Therefore $t^{(3)} \in [0,1]^{k+1}$ and we have $t^{(3)} \in B_\eta (t^*) \cap T_{D,n}$ for $n$ sufficiently large.

■

Proof of Lemma 7.1.

Let $\mu _n^\chi$ be the Borel probability measure on $X$ defined by

$$\begin{equation*} \mu _n^\chi (B) = {\mathbb{E}}_n^\chi \left( \frac{1}{\# V} \sum _{v \in V} \mathbb{1}_{B}\left( \Pi _v^{\sigma _n}(\chi ) \right) \right) \end{equation*}$$

for any Borel set $B \subset X$. By Proposition 7.2, it suffices to show that $\mu _n^\chi (B) \to \mu (B)$ as $n\to \infty$ for any clopen set $B \subset X$. Because clopen sets are finite unions of cylinder sets, it suffices to show that if $D \subset \Gamma$ is a finite subset and $\xi \in \{0,1\}^D$ then $\lim _{n \to \infty } \mu _n^{\chi }([\xi ]) = \mu ([\xi ])$ where $[\xi ]$ is the cylinder set $\{x \in X : x\upharpoonright D = \xi \}$. We can further assume $D$ to be a connected finite union of hyperedges with $1_\Gamma \in D$. The proof now follows from Lemma 7.3 since

$$\begin{equation*} \mu _n^{\chi }([\xi ]) = n^{-1} \sum _{v\in V}{\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right) = n^{-1} \sum _{v\in \chi ^{-1}(\xi (1_\Gamma ))}{\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right) = (1/2) {\mathbb{P}}^\chi _n\left( F_{D,\xi ,v_0} \right), \end{equation*}$$

where, in the last equality, $v_0$ is any vertex in $\chi ^{-1}(\xi (1_\Gamma ))$. These equations are justified as follows. By symmetry, if $v_0,v_1 \in \chi ^{-1}(\xi (1_\Gamma ))$, then ${\mathbb{P}}^\chi _n\left( F_{D,\xi ,v_0} \right)= {\mathbb{P}}^\chi _n\left( F_{D,\xi ,v_1} \right)$. On the other hand, if $v \notin \chi ^{-1}(\xi (1_\Gamma ))$, then ${\mathbb{P}}^\chi _n\left( F_{D,\xi ,v} \right)=0$. Lastly, $|\chi ^{-1}(\xi (1_\Gamma ))|=n/2$.

■

7.2. The density of the rigid set

This subsection proves Lemma 6.1. So we assume the hypotheses of Proposition 5.9. An element $x \in X$ is a 2-coloring of the Cayley hyper-tree of $\Gamma$. Interpreted as such, $C_l(x), A_l(x), A'_l(x)$ are well-defined subsets of $\Gamma$ (see §6 to recall the definitions).

For $l \in {\mathbb{N}} \cup \{\infty \}$, let

$$\begin{align*} {\tilde{C}}_l&=\{x\in X:\nobreakspace 1_\Gamma \in C_l(x)\}, \\ {\tilde{A}}_l&=\{x\in X:\nobreakspace 1_\Gamma \in A_l(x)\}, \\ {\tilde{A}}'_l&=\{x\in X:\nobreakspace 1_\Gamma \in A'_l(x)\}. \end{align*}$$

Recall that $\lambda _0 = \frac{1}{2^{k-1}-1}$ and $\lambda =d\lambda _0$. Since we assume the hypothesis of Proposition 5.9, $\lambda$ is asymptotic to $\log (2)k$ as $k \to \infty$.

Proposition 7.5.

$$\begin{align*} \mu ({\tilde{C}}_\infty ) &\ge 1 - \lambda ^2 e^{-\lambda } + O(k^6 2^{-2k}), \\ \mu ({\tilde{C}}_\infty \cup {\tilde{A}}_\infty ) &\ge 1- e^{-\lambda } + O(k^4 2^{-2k}). \end{align*}$$

Proof.

For brevity, let $e_i \subset \Gamma$ be the subgroup generated by $s_i$. So $e_i$ is a hyper-edge of the Cayley hyper-tree. Let $F^i_l \subset X$ be the set of all $x$ such that

(1)

$1_\Gamma$ supports the edge $e_i$ with respect to $x$ and

(2)

$e_i \setminus \{1_\Gamma \} \subset C_l(x)$.

Since $C_{l+1}(x) \subset C_l(x)$, it follows that $F^i_{l+1} \subset F^i_l$. The events $F^i_l$ for $i=1$, …, $d$ are i.i.d. Let $p_l = \mu (F^i_l)$ be their common probability.

We write $\operatorname {Pr}(\operatorname {Bin}(n,p) =m) = {n \choose m}p^m(1-p)^{n-m}$ for the probability that a binomial random variable with $n$ trials and success probability $p$ equals $m$. Since the events $F^1_{l-1}$, …, $F^d_{l-1}$ are i.i.d., ${\tilde{A}}_{l}$ is the event that either 1 or 2 of these events occur and ${\tilde{C}}_l$ is the event that at least 3 of these events occur, it follows that

$$\begin{equation*} \mu ({\tilde{A}}_{l}) = \operatorname {Pr}(\operatorname {Bin}(d,p_{l-1}) \in \{1,2\}). \end{equation*}$$

$$\begin{equation*} \mu ({\tilde{C}}_l) = \operatorname {Pr}(\operatorname {Bin}(d,p_{l-1})\ge 3). \end{equation*}$$ Thus

$$\begin{equation*} \mu ({\tilde{C}}_l \cup {\tilde{A}}_{l}) = \operatorname {Pr}(\operatorname {Bin}(d,p_{l-1}) >0). \end{equation*}$$

Claim 2.

$p_0=\lambda _0$ and for $l\ge 0$, $p_{l+1}=f(p_l)$ where

$$\begin{equation*} f(t) = \lambda _0 \operatorname {Pr}(\operatorname {Bin}(d-1,t) \ge 3)^{k-1}. \end{equation*}$$

Proof.

To reduce notational clutter, let $F_l=F^1_l$. Note that $p_0 =\mu (F_0)=\lambda _0$ is the probability that the edge $e_1$ is critical. So

$$\begin{equation*} p_{l+1} = \mu (F_0) \mu (F_{l+1}\nobreakspace |\nobreakspace F_0) = \lambda _0 \mu (F_{l+1}\nobreakspace |\nobreakspace F_0). \end{equation*}$$

Conditioned on $F_0$, $F_{l+1}$ is the event that $e_1 \setminus \{1_\Gamma \} \in C_{l+1}(x)$. By symmetry and the Markov property $\mu (F_{l+1}\nobreakspace |\nobreakspace F_0)$ is the $(k-1)$-st power of the probability that $s_1 \in C_{l+1}(x)$ given that $1_\Gamma$ supports $e_1$. By translation invariance, that probability is the same as the probability that $1_\Gamma \in C_{l+1}(x)$ given that $1_\Gamma$ does not support the edge $e_1$. By definition of $C_{l+1}(x)$ and the Markov property, this is the same as the probability that a binomial random variable with $(d-1)$ trials and success probability $p_l$ is at least 3. This implies the claim.

■

The next step is to bound $\operatorname {Pr}(\operatorname {Bin}(d-1,t) \ge 3)$ from below:

$$\begin{align} \operatorname {Pr}(\operatorname {Bin}(d-1,t) \ge 3) &= 1 - (1-t)^{d-1} - (d-1)t(1-t)^{d-2} - {d - 1 \choose 2}t^2(1-t)^{d-3} \\ &\ge 1 - e^{ -(d-1)t}\left(1 + \frac{(d-1)t}{1-t} + \frac{(d-1)^2t^2}{2(1-t)^2}\right). {\tag{37}} \end{align}$$

The last inequality follows from the fact that $(1-t)^{d-1} \le e^{-(d-1)t}$. This motivates the next claim:

Claim 3.

Suppose $t$ is a number satisfying $\lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1} \le t \le \lambda _0$. Then for all sufficiently large $k$,

$$\begin{align*} 0 \le \lambda -(d-1)t &\le 1 \\ 1 + \frac{(d-1)t}{1-t} + \frac{(d-1)^2t^2}{2(1-t)^2} &\le (d-1)^2t^2. \end{align*}$$

Proof.

The first inequality follows from:

$$\begin{equation*} \lambda -(d-1)t \ge \lambda -(d-1)\lambda _0 = \lambda _0 >0. \end{equation*}$$

The second inequality follows from:

$$\begin{align*} \lambda -(d-1)t &\le \lambda -(d-1)\lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1}\\ & = d\lambda _0 - (d-1)\lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1} \\ &\le d\lambda _0 - (d-1)\lambda _0( 1- (k-1) \lambda ^2 e^{1-\lambda })\\ & \le \lambda _0 + (d-1)\lambda _0 (k-1) \lambda ^2 e^{1-\lambda } \le \lambda _0 + k\lambda ^3 e^{1-\lambda } \to _{k\to \infty } 0. \end{align*}$$

The third line follows from the general inequality $(1-x)^{k-1} \ge 1-(k-1)x$ valid for all $x \in [0,1]$. To see the limit, observe that under the hypotheses of Proposition 5.9, $d \sim (\log (2)/2)k2^k$. So $\lambda \sim \log (2) k$. In particular, $k\lambda ^3 e^{1-\lambda } \to 0$ and $\lambda _0 \to 0$ as $k\to \infty$. The implies the limit. Thus if $k$ is large enough then the second inequality holds.

To see the last inequality, observe that since $t \le \lambda _0$, $t \to 0$ as $k \to \infty$. On the other hand, $(d-1)t \sim \lambda \sim \log (2)k$. Thus $\frac{(d-1)t}{1-t}$ and $(d-1)t$ are asymptotic to $\log (2)k$. Since $1 + \log (2)k + \frac{\log (2)^2k^2}{2} \le \log (2)^2k^2$ for all sufficiently large $k$, this proves the last inequality assuming $k$ is sufficiently large.

■

Now suppose that $t$ is as in Claim 3. Then

$$\begin{align*} f(t) &\ge \lambda _0\left(1 - e^{ -(d-1)t} \left(1 + \frac{(d-1)t}{1-t} + \frac{(d-1)^2t^2}{2(1-t)^2}\right)\right)^{k-1} \\ &\ge \lambda _0\left(1 - e^{1-\lambda } (d-1)^2t^2 \right)^{k-1} \ge \lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1}. \end{align*}$$

The first inequality is implied by 37. The second and third inequalities follow from Claim 3. For example, since $\lambda -(d-1)t \le 1$, $e^{-(d-1)t} \le e^{1-\lambda }$.

Therefore, if $p_l$ satisfies the bounds $\lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1} \le p_l \le \lambda _0$ then $f(p_l)=p_{l+1}$ satisfies the same bounds. Since $p_\infty = \lim _{l\to \infty } f^l(\lambda _0)$, it follows that

$$\begin{equation} \lambda _0 \ge p_\infty \ge \lambda _0\left(1 - \lambda ^2 e^{1-\lambda } \right)^{k-1} = \lambda _0 + O(k^3 2^{-2k}). {\tag{38}} \end{equation}$$

Because $(1-\frac{t}{n})^n \le e^{-t}$ for any $t,n>0$,

$$\begin{align*} \mu ({\tilde{C}}_\infty \cup {\tilde{A}}_\infty ) &= \lim _{l \to \infty } \mu ({\tilde{C}}_l \cup {\tilde{A}}_{l}) = \lim _{l \to \infty } \operatorname {Pr}(\operatorname {Bin}(d, p_{l-1}) > 0 ) = \operatorname {Pr}(\operatorname {Bin}(d, p_\infty ) > 0 ) \\ & = 1 - (1-p_\infty )^d \ge 1 - \exp (-p_\infty d) = 1 - e^{-\lambda } + O(k^4 2^{-2k}). \end{align*}$$

The first equality occurs because ${\tilde{C}}_l\cup {\tilde{A}}_l$ decreases to ${\tilde{C}}_\infty \cup {\tilde{A}}_\infty$. By 37 and Claim 3 (with $d$ in place of $d-1$),

$$\begin{align*} \mu ({\tilde{C}}_\infty ) &=\operatorname {Pr}(\operatorname {Bin}(d, p_\infty ) \ge 3 ) \ge \operatorname {Pr}(\operatorname {Bin}(d, \lambda _0 + O(k^3 2^{-2k})) \ge 3 ) \\ &\ge 1 - \exp (-\lambda _0 d)\left(1 + \frac{d\lambda _0 }{1-\lambda _0 } + \frac{d^2\lambda _0 ^2}{2(1-\lambda _0 )^2}\right) + O(k^6 2^{-2k})\\ &\ge 1 - \lambda ^2 e^{-\lambda } + O(k^6 2^{-2k}). \end{align*}$$ ■

Lemma 7.6.

$\mu ({\tilde{A}}'_{\infty }) = o(e^{-\lambda })$ where the implied limit is as $k\to \infty$ and $\eta$ is bounded.

Proof.

As in the previous proof, let $e_i \subset \Gamma$ be the subgroup generated by $s_i$. So $e_i$ is a hyper-edge of the Cayley hyper-tree.

Let $x\in X$. We say that an edge $e$ is attaching (for $x$) if it is supported by a vertex $v \in A_\infty (x)$ and $e \setminus \{v\} \subset C_\infty (x)$. Let $F(x)=0$ if $1_\Gamma \notin C_\infty (x)$. Otherwise, let $F(x)$ be the number of attaching edges containing $1_\Gamma$. Then by translation invariance,

$$\begin{equation} \mu ({\tilde{A}}'_\infty ) \le \sum _{m=2}^d m \mu (F(x)=m). {\tag{39}} \end{equation}$$

Let $G \subset X$ be the set of all $x$ such that

(1)

$e_1$ is a critical edge supported by some vertex $v \neq 1_\Gamma$,

(2)

$e_1 \setminus \{v,1_\Gamma \} \subset C_\infty (x)$,

(3)

$v \in A_\infty (x)$.

By the Markov property and symmetry,

$$\begin{equation} \mu (F(x)=m) \le {d \choose m}\mu (G)^m(1-\mu (G))^{d-m}. {\tag{40}} \end{equation}$$

Let

•

$G_1 \subset X$ be the set of all $x$ such that $e_1$ is supported by $s_1$,

•

$G_2 \subset X$ be the set of all $x$ such that $e_1 \setminus \{s_1,1_\Gamma \} \subset C_\infty (x)$,

•

$G_3 \subset X$ be the set of all $x$ such that $s_1 \in A_\infty (x)$.

By symmetry

$$\begin{equation*} \mu (G) = (k-1)\mu (G_3|G_2 \cap G_1)\mu (G_2|G_1)\mu (G_1). \end{equation*}$$

Conditioned on $G_1 \cap G_2$, if $G_3$ occurs then there are no more than $1$ attaching edge $e$ supported by $s_1$ with $e\ne e_1$. By the Markov property and symmetry,

$$\begin{equation*} \mu (G_3|G_2\cap G_1) \leq \operatorname {Pr}(\operatorname {Bin}(d-1,p_\infty ) \le 1) = O(\lambda e^{-\lambda }), \end{equation*}$$

where we have used 38. Also $\mu (G_1)=\lambda _0$. Thus $\mu (G) \leq O(k^2e^{-2\lambda })$. So 39 and 40 along with straightforward estimates imply $\mu ({\tilde{A}}'_\infty ) = o(e^{-\lambda })$.

■

Lemma 7.7.

$\limsup _{l\to \infty } \mu ({\tilde{A}}'_l) \le \mu ({\tilde{A}}'_\infty )$.

Proof.

Given a coloring $\chi :\Gamma \to \{0,1\}$ of the Cayley hyper-tree and $l \in {\mathbb{N}}$, define $A''_l(\chi ) = \cup _{m\ge l} A'_m(\chi )$. Also define ${\tilde{A}}''_l=\{x\in X:\nobreakspace 1_\Gamma \in A''_l(x)\}$. Since ${\tilde{A}}''_l \supset {\tilde{A}}'_l$ and the sets ${\tilde{A}}''_l$ are decreasing in $l$, it suffices to prove that $\cap _{l\ge 0} {\tilde{A}}''_l \subset {\tilde{A}}'_\infty$.

Suppose $x \in \cap _{l\ge 0} {\tilde{A}}''_l$. Then there exists an infinite set $S \subset {\mathbb{N}}$ such that $x \in {\tilde{A}}'_l$ $(\forall l \in S)$. So $1_\Gamma \in A'_l(x)$ $(\forall l \in S)$. So for each $l \in S$, there exist $g_l \in A_l(x) \setminus \{1_\Gamma \}$ and hyper-edges $e_l, f_l \subset \Gamma$ such that

(1)

$1_\Gamma$ supports $e_l$ (with respect to $x$),

(2)

$g_l$ supports $f_l$ (with respect to $x$),

(3)

$e_l \cup f_l \setminus \{1_\Gamma , g_l\} \subset C_{l-1}(x)$,

(4)

$e_l \cap f_l \ne \emptyset$.

Because $e_l \cap f_l \ne \emptyset$, $g_l$ is necessarily contained in the finite set $\{s^{p_i}_is^{p_j}_j:\nobreakspace 1 \le i,j\le d, 0 \le p_i \le k\}$. So after passing to an infinite subset of $S$ if necessary, we may assume there is a fixed element $g \in \Gamma$ such that $g=g_l$ $(\forall l \in S)$. Similarly, we may assume there are edges $e,f \subset \Gamma$ such that $e_l=e$ and $f_l=f$ $(\forall l \in S)$.

Observe that $1_\Gamma \notin C_\infty (x)$ because $1_\Gamma \in A_l(x)$ implies $1_\Gamma \notin C_l(x)$ $(\forall l \in S)$. Similarly, $g \notin C_\infty (x)$. Because $e_l \cup f_l \setminus \{1_\Gamma , g_l\} \subset C_l(x)$ $(\forall l \in S)$ and the sets $C_l(x)$ are decreasing in $l$, it follows that $e \cup f \setminus \{1_\Gamma , g\} \subset C_\infty (x)$. Therefore $\{1_\Gamma ,g\} \subset A_\infty (x)$. This verifies all of the conditions showing that $1_\Gamma \in A'_\infty (x)$ and therefore $x \in {\tilde{A}}'_\infty$ as required.

■

We can now prove Lemma 6.1:

Proof of Lemma 6.1.

Observe that the sets ${\tilde{C}}_l,{\tilde{A}}_l, {\tilde{A}}'_l$ are clopen for finite $l$. By Lemma 7.1,

$$\begin{equation} \lim _{\delta \searrow 0} \liminf _{n\to \infty } {\mathbb{P}}^\chi _n\left(\left|\frac{|C_l(\chi ) \cup A_l(\chi ) \setminus A'_l(\chi )|}{n} - \mu \left({\tilde{C}}_l \cup {\tilde{A}}_l \setminus {\tilde{A}}'_l\right) \right| <\delta \right)=1 {\tag{41}} \end{equation}$$

for any finite $l$. Since ${\tilde{A}}_\infty \cup {\tilde{C}}_\infty$ is the decreasing limit of ${\tilde{A}}_l \cup {\tilde{C}}_l$, Lemma 7.7 implies

$$\begin{equation*} \liminf _{l\to \infty } \mu ({\tilde{C}}_l \cup {\tilde{A}}_l \setminus {\tilde{A}}'_l) \ge \mu ({\tilde{C}}_\infty \cup {\tilde{A}}_\infty \setminus {\tilde{A}}'_\infty ). \end{equation*}$$

By Proposition 7.5 and Lemma 7.6,

$$\begin{equation*} \mu ({\tilde{C}}_\infty \cup {\tilde{A}}_\infty \setminus {\tilde{A}}'_\infty ) \geq 1 - e^{-\lambda } + o(e^{-\lambda }). \end{equation*}$$

Together with 41, this implies the lemma.

■

8. Rigid vertices

This section proves Lemma 6.2. So we assume the hypotheses of Proposition 5.9.

As in the previous section, fix an equitable coloring $\chi :V \to \{0,1\}$. We assume $|V|=n$ and let $\sigma :\Gamma \to {\operatorname {Sym}}(V)$ be a uniformly random uniform homomorphism conditioned on the event that $\chi$ is proper with respect to $\sigma$.

Lemma 8.1 (Expansivity Lemma).

There is a constant $k_0>0$ such that the following holds. If $k\ge k_0$ then with high probability (with respect to the planted model), as $n\to \infty$, for any $T \subset V$ with $|T| \le 2^{-k/2} n$ the following is true. For a vertex $v$ let $E_v$ denote the set of hyperedges supported by $v$. Let $E_T$ be the set of all edges $e\in \cup _{v\in T} E_v$ such that $|e \cap T| \ge 2$. Then

$$\begin{equation*} \#E_T \le 2 \#T. {} \end{equation*}$$

Proof.

Claim 4.

There exists $k_0 \in {\mathbb{N}}$ such that $k\ge k_0$ implies

•

$k/2 \le \lambda \le k$,

•

$1/2-k2^{1-k/2} \ge \frac{1}{\sqrt {8}}$,

•

and for any $0 < t\le 2^{-k/2}$ and $k/2 \le \lambda ' \le k$$$\begin{equation*} H(t,1-t) + \lambda 'H(2t/ \lambda ', 1-2t/ \lambda ' ) + 2t \log (4k) + 4t \log (t) \le 0.9t\log (t). \end{equation*}$$

Proof.

Recall that $\lambda = \log (2)k + O(k 2^{-k})$. So the first two requirements are immediate for $k_0$ large enough.

We estimate each of the first three terms on the left as follows. Because $1 = \lim _{t \searrow 0} \frac{H(t,1-t)}{-t\log (t)}$, there exists $k_0 \in {\mathbb{N}}$ such that $k \ge k_0$ implies $\frac{H(t,1-t)}{-t\log (t)} \le 1.01$.

Note,

$$\begin{align*} \lambda 'H(2t/ \lambda ', 1-2t/ \lambda ' ) &= - 2t\log ( 2t/\lambda ') - (\lambda ' - 2t)\log (1-2t/\lambda ') \\ &= - 2t\log ( 2t/\lambda ') + O(t) \le -2t\log (t) + 2t \log (\lambda ') + O(t)\\ &\le -2t\log (t) + 2t \log (k) + O(t). \end{align*}$$

So by making $k_0$ larger if necessary, we may assume

$$\begin{equation*} \frac{\lambda 'H(2t/ \lambda ', 1-2t/ \lambda ' )}{-t\log (t)} \le 2.01. \end{equation*}$$

Since

$$\begin{equation*} \frac{2t \log (4k)}{-t\log (t)} \le \frac{2\log (4k)}{(k/2)\log (2)}, \end{equation*}$$

we may also assume $\frac{2t \log (4k)}{-t\log (t)} \le 0.01$. Combining these inequalities, we obtain

$$\begin{align*} & H(t,1-t) + \lambda 'H(2t/ \lambda ', 1-2t/ \lambda ' ) + 2t \log (4k) + 4t \log (t)\\ & \qquad \le (1.01 + 2.01 + 0.01 -4)(-t\log (t)) \le 0.9t\log (t). \end{align*}$$ ■

From now on, we assume $k\ge k_0$ with $k_0$ as above. To simplify notation, let $\zeta =2^{-k/2}$. Given a $2d$-tuple $c=(c_{1,0}$, $c_{1,1}$, …, $c_{d,0}$, $c_{d,1})$ of natural numbers, let $E_c$ be the event that there are exactly $c_{i,0}$ critical edges of the form $\{\sigma (s_i)^j(v) : 0 \leq j \leq k-1\}$ and supported by a vertex of color $0$, and $c_{i,1}$ critical edges of the form $\{\sigma (s_i)^j(v) : 0 \leq j \leq k-1\}$ and supported by a vertex of color $1$. We denote $|c| = \sum _{1\leq i \leq d, b\in \{0,1\}} c_{i,b}$. Let ${\mathbb{P}}_{c,n}^\chi$ be the planted model conditioned on $E_c$.

This measure can be constructed as follows. Let $I_c$ be the set of triples $(i,b,j)$ with $1\le i \le d$, $b \in \{0,1\}$ and $1\le j \le c_{i,b}$. First choose edges $\{e_{i,b,j}\}_{(i,b,j)\in I_c}$ uniformly at random subject to the conditions:

(1)

each $e_{i,b,j} \subset [n]$ has cardinality $k$ and $e_{i,b,j} \cap e_{i,b',j'} = \emptyset$ whenever $b \neq b'$ or $j \ne j'$,

(2)

each $e_{i,b,j}$ is critical and is supported by a vertex of color $b$ with respect to $\chi$.

Next choose a uniformly random uniform homomorphism $\sigma$ subject to:

(1)

$\chi$ is a proper coloring with respect to $\sigma$,

(2)

each $e_{i,b,j}$ is of the form $\{\sigma (s_i)^j(v) : 0 \leq j \leq k-1\}$ with respect to $\sigma$,

(3)

the edges $\{e_{i,b,j}\}_{(i,b,j) \in I_c}$ are precisely the critical edges of $\chi$ with respect to $\sigma$.

Then $\sigma$ is distributed according to ${\mathbb{P}}_{c,n}^\chi$.

For $1\le l \le n$, let ${\mathcal{T}}_l$ be the collection of all subsets $T \subset V=[n]$ such that $|T| = l$ and $|E_T| > 2|T|$. Note that ${\mathcal{T}}_1$ is empty.

To prove the lemma, we claim it suffices to show the following:

Claim 5.

If $n$ is sufficiently large and $kn/2 \le |c| \le kn$ then $\sum _{2 \le l \le \zeta n} {\mathbb{E}}_{c,n}^\chi [\#{\mathcal{T}}_l]$ tends to zero in $n$.

We briefly return to the model ${\mathbb{P}}^\chi _n$ not conditioned on $E_c$. Let $E$ be the set of all critical edges. By Lemma 7.1, with high probability in ${\mathbb{P}}^\chi _n$, $|E|$ is asymptotic to $\lambda n$ as $n\to \infty$. Let $E'_n$ be the event that $(k/2)n \le |E| \le kn$. So ${\mathbb{P}}^\chi _n(E'_n) \to 1$ as $n\to \infty$.

By a first moment argument and the above paragraph, to prove the lemma it suffices to show that $\sum _{2 \le l \leq \zeta n}{\mathbb{E}}^\chi _n(\#{\mathcal{T}}_l|E_n')$ tends to $0$ in $n$. Now ${\mathbb{E}}^\chi _n(\#{\mathcal{T}}_l|E_n')$ is a convex combination of ${\mathbb{E}}^\chi _{c,n}(\#{\mathcal{T}}_l)$ over those $c$ such that $kn/2 \le |c| \le kn$, so the lemma follows from Claim 5.

Before proving the above claim we need to prove another claim, which needs the following setup. For $s\in I_c$ and $T\subset V$, let $F_{T,s}$ be the event that $e_s$ is supported by a vertex in $T$ and $|e_s \cap T|\ge 2$. For $S \subset I_c$, let $F_{T,S} = \cap _{s\in S} F_{T,s}$. Note that for any $T \subset [n]$, the event $\{ T \in {\mathcal{T}}_l\}$ is contained in $\cup _S F_{T,S}$ where the union is over all $S \subset I_c$ with $|S|=2l$. So

$$\begin{equation} {\mathbb{E}}^\chi _{c,n}[ \#{\mathcal{T}}_l ] \le \sum _{S,T} {\mathbb{P}}^\chi _{c,n}(F_{T,S}), {\tag{42}} \end{equation}$$

where the sum is over all $T \subset [n]$ and $S \subset I_c$ with $|T|=l$ and $|S| = 2l$.

Before proving the claim above, we need to prove:

Claim 6.

For $1 \le l \le \zeta n$, any $T \subset V$ with cardinality $|T|=l$, any $S \subset I_c$ with $|S| \le 2l-1$, and any $s_0 \in I_c \setminus S$, one has ${\mathbb{P}}^\chi _{c,n}(F_{T,s_0}| F_{T,S}) \le \frac{2kl^2}{n^2}$.

Proof of Claim 6.

For $s\in I_c$, let $e_s$ be a random edge in $[n]$ with cardinality $k$ as in the sampling algorithm above. Without loss of generality, we imagine that $e_s$ for $s\in S$ has been chosen before $e_{s_0}$. Let $s_0=(i_0,b_0,j_0)$. We say that an edge $e$ is of type $i$ if $e$ is of the form $\{\sigma (s_i)^j(v) : 0 \leq j \leq k-1\}$. Let $S_0 \subset S$ be those edges of type $i_0$, and let $V_0 = \cup _{e \in S_0} e$,

•

$n_i$ be the number of vertices $v \in [n] \setminus V_0$ such that $\chi (v)=i$, and

•

$l_i$ be the number of vertices $v \in T \setminus V_0$ such that $\chi (v)=i$.

Let $e_0 = e_{s_0}$. The probability that $e_{0}$ is supported by a vertex $v$ in $T$ is $l_{b_0}/n_{b_0}$ (this is conditioned on the edges $e_s$ for $s\in S$).

Suppose first that $e_0$ is supported by a vertex $v$ in $T$ with $\chi (v) = 0$ (so $b_0 = 0$). Then the probability that $|e_{0} \cap T| =1$ is

$$\begin{equation*} \frac{{n_1-l_1 \choose k-1}}{{n_1 \choose k-1}}. \end{equation*}$$

It follows that for $b_0 = 0$

$$\begin{equation*} {\mathbb{P}}^\chi _{c,n}(F_{T,s_0}| F_{T,S}) = \frac{l_0}{n_0} \left(1-\frac{{n_1-l_1 \choose k-1}}{{n_1 \choose k-1}}\right) . \end{equation*}$$

In order to bound this expression, consider

$$\begin{align*} \frac{{n_1-l_1 \choose k-1}}{{n_1 \choose k-1}} &= \left(\frac{n_1-l_1}{n_1}\right)\cdots \left(\frac{n_1-l_1-k+2}{n_1-k+2}\right)\\ &\ge \left(\frac{n_1-l_1-k+2}{n_1-k+2}\right)^{k-1} = \left(1-\frac{l_1}{n_1-k+2}\right)^{k-1} \\ &\ge 1-\frac{(k-1)l_1}{n_1-k+2} \ge 1 - \frac{k l_1}{n_1}. \end{align*}$$

Thus,

$$\begin{equation*} {\mathbb{P}}^\chi _{c,n}(F_{T,s_0}| F_{T,S}) \le \frac{kl_0l_1}{n_0n_1}. \end{equation*}$$

A similar argument shows that the same bound above holds for the case $b_0 = 1$.

Because $l_0+l_1 \le |T|=l$, $(l_0+l_1)^2 - (l_0 - l_1)^2 \leq l^2$, so that $l_0l_1\le l^2/4$. Note

$$\begin{equation*} n_0 \ge n/2 - 2kl \ge n(1/2 - k2^{1-k/2}) \ge n/\sqrt {8}, \end{equation*}$$

where we have used the assumption $l\le \zeta n = 2^{-k/2}n$ and Claim 4. Similarly, $n_1 \ge n/\sqrt {8}$. Substitute these inequalities above to obtain

$$\begin{equation*} {\mathbb{P}}^\chi _{c,n}(F_{T,s_0}| F_{T,S}) \le \frac{2kl^2}{n^2}. \end{equation*}$$■

We now prove Claim 5. Apply the chain rule and Claim 6 to obtain: if $S \subset I_c$ has $|S|=2l$ and $T \subset [n]$ with $|T| = l$ then

$$\begin{equation*} {\mathbb{P}}^\chi _{c,n}(F_{T,S}) \le \left(\frac{2kl^2}{n^2}\right)^{2l}. \end{equation*}$$

By 42

$$\begin{equation*} {\mathbb{E}}^\chi _{c,n}[\#{\mathcal{T}}_l] \le \sum _{S,T} {\mathbb{P}}^\chi _{c,n}(F_{T,S}) \le {n \choose l}{|c| \choose 2l}\left(\frac{2kl^2}{n^2}\right)^{2l}, \end{equation*}$$

where the sum is over all $T \subset [n]$ and $S \subset I_c$ with $|T|=l$, $|S| = 2l$. Define $t, \lambda '$ by $tn = l$ and $|c|=\lambda ' n$. By hypothesis $k/2\le \lambda ' \le k$. Consider the following cases:

Case 1.

$2 \leq l \leq n^{0.1}$. Then we make the following estimates:

$$\begin{align*} {n \choose l} &\leq n^l ,\\ {|c| \choose 2l} &\leq (kn)^{2l}. \end{align*}$$

It follows that ${\mathbb{E}}^\chi _{c,n}[\#{\mathcal{T}}_l] \le \left(\frac{4k^4l^4}{n}\right)^l$, which is bounded by $n^{-1.1}$ for large enough $n$.

Case 2.

$l > n^{0.1}$. We make the following estimates:

$$\begin{align*} {n \choose l} &= \exp (nH(t, 1-t)+ 0.5\log (n) + O(1)),\\ {|c| \choose 2l} &\le \exp (\lambda ' n H(2t/\lambda ', 1-2t /\lambda ' )+ 0.5\log (kn) + O(1)) \end{align*}$$

so that

$$\begin{equation*} {\mathbb{E}}^\chi _{c,n}[\#{\mathcal{T}}_l] \le Ckn\exp (n(H(t,1-t) + \lambda 'H(2t/ \lambda ', 1-2t/ \lambda ' ) + 2t \log (2k) + 4t \log (t))) \end{equation*}$$

for some constant $C$. For $n$ sufficiently large and $t \le 2^{-k/2}$, this is bounded above by $Ckn\exp (0.9nt\log (t)) \le Ckn2^{-0.45kn^{0.1}}$ by Claim 4 and the choice of $k_0$ and $l$. It follows that in this range of $l$, ${\mathbb{E}}^\chi _{c,n}[\#{\mathcal{T}}_l]$ decays super-polynomially.

This proves Claim 5 and finishes the lemma.■

Lemma 8.2.

Let $\rho >0$. Then there exists $L$ such that $l>L$ implies $C_l(\chi ) \subset [n]$ is $\rho$-rigid (with high probability in the planted model as $n\to \infty$).

Proof.

Without loss of generality, we may assume that $0<\rho < \mu ({\tilde{C}}_\infty )$.

Observe that the sets ${\tilde{C}}_l$ are clopen for finite $l$. By Lemma 7.1,

$$\begin{equation*} \lim _{\eta \searrow 0} \liminf _{n\to \infty } {\mathbb{P}}^\chi _n\left(\left|\frac{|C_l(\chi )|}{n} - \mu \left({\tilde{C}}_l\right) \right| <\eta \right)=1. \end{equation*}$$

Since the sets $C_l(\chi )$ are decreasing with $l$, this implies the existence of $L$ such that $l>L$ implies

$$\begin{equation*} \liminf _{n\to \infty } {\mathbb{P}}^\chi _n\left(\left|\frac{|C_l(\chi )|}{n} - \frac{|C_{l+1}(\chi )|}{n}\right| <\rho /3 \right)=1. \end{equation*}$$

Choose $l >L$. Let $\psi : V \to \{0,1\}$ be a $\sigma$-proper coloring. Let

$$\begin{equation*} T_l = \{v\in C_l(\chi ):\nobreakspace \chi (v) \neq \psi (v)\}. \end{equation*}$$

Define $T_{l+1}$ similarly. Since $|C_l(\chi ) \setminus C_{l+1}(\chi )| < \rho n/3$ (with high probability) and $T_l \setminus T_{l+1} \subset C_l(\chi ) \setminus C_{l+1}(\chi )$, it follows that $|T_l \setminus T_{l+1}| < \rho n/3$ (with high probability).

For every $v \in T_{l+1}$, let $F_v \subset E_v$ be the subset of $\chi$-critical edges $e$ such that $e \subset C_l(\chi )$.

We claim that if $v \in T_{l+1}$ then $F_v \subset E_{T_l}$ where

$$\begin{equation*} E_{T_l}=\{e \in \cup _{v\in T_l} E_v:\nobreakspace |e\cap T_l | \ge 2\}. \end{equation*}$$

Since $v \in T_{l+1}$, $\psi (v) \ne \chi (v)$. If $e \in F_v$ then $v$ supports $e$ with respect to $\chi$. Therefore because $\psi :[n] \to \{0,1\}$ is a proper coloring, there must exist a vertex $w \in e \setminus \{v\}$ such that $\psi (w) \ne \psi (v)$. This, combined with $\chi (w) \neq \chi (v)$, implies $\psi (w) \neq \chi (w)$ since there are only two possible colors. Since $\{v,w\} \subset e \subset C_l(\chi )$, this means that $|e \cap T_l | \ge 2$ and therefore $e \in E_{T_l}$, which proves the claim.

For every $v \in T_{l+1}$, $|F_v| \ge 3$ by the definition of the sets $C_l(\chi )$. Since edges can only be supported by one vertex, the sets $F_v$ are pairwise disjoint. So

$$\begin{equation*} |E_{T_l}| \geq \left|\bigcup _{v\in T_{l+1} } F_v\right| \geq 3|T_{l+1}| \ge 3|T_l| - \rho n. \end{equation*}$$

If $|T_l| > \rho n$ then $|E_{T_l}|\geq 3|T_l| - \rho n > 2|T_l|$. So it follows from Lemma 8.1 that (with high probability), $|T_l| > 2^{-k/2} n$. Thus $C_l$ is $\rho$-rigid.

■

We can now prove Lemma 6.2.

Proof of Lemma 6.2.

Let $\rho >0$. By Lemma 8.2, there exists $L$ such that $l>L$ implies $C_l(\chi )$ is $(\rho /3)$-rigid with high probability in the planted model as $n\to \infty$. So without loss of generality we condition on the event that $C_l(\chi )$ is $(\rho /3)$-rigid.

Now let $l-1>L$. Let $\psi : V \to \{0,1\}$ be a $\sigma$-proper coloring. Let

$$\begin{gather*} T_{l-1} = \{v\in C_{l-1}(\chi ):\nobreakspace \chi (v) \neq \psi (v)\}\\ T_l = \{v\in C_l(\chi ):\nobreakspace \chi (v) \neq \psi (v)\}\\ T' = \{v\in A_l(\chi ) \setminus A'_l(\chi ):\nobreakspace \chi (v) \neq \psi (v)\}. \end{gather*}$$

We claim that $|T_{l-1}| \ge |T'|$. To see this, let $v \in T'$. Then there exists an edge $e$ supported by $v$ (with respect to $\chi$) with $e \setminus \{v\} \subset C_{l-1}(\chi )$. Since $\psi$ is proper and $\psi (v)\ne \chi (v)$, there must exist a vertex $w \in e \setminus \{v\}$ with $\psi (w) \ne \chi (w)$. Necessarily, $w \in T_{l-1}$. So there exists a function $f:T' \to T_{l-1}$ such that $f(v)$ is contained in an edge $e$ supported by $v$ with $e \setminus \{v\} \subset C_{l-1}(\chi )$. Because $v \notin A'_l(\chi )$, $f$ is injective. This proves the claim.

Now suppose that $|T_l\cup T'| > \rho n$. Since $T_l$ and $T'$ are disjoint, either $|T_l| > (\rho /3)n$ or $|T'| > (2\rho /3)n$. If $|T_l| > (\rho /3)n$, we are done because by assumption that $C_l(\chi )$ is $(\rho /3)$-rigid, $|T_l| > 2^{-k/2}n$ and so

$$\begin{equation*} |T_l \cup T'| > 2^{-k/2}n. \end{equation*}$$

If $|T'| > (2\rho /3)n$ the claim implies $|T_{l-1}| > (2\rho /3)n$. Now in the proof of Lemma 8.2 we have shown that $|T_{l-1}\setminus T_l| < (\rho /3)n$, so $|T_l| > (\rho /3)n$ and we are again done. This proves the lemma.

■