Chasing the k-colorability threshold

Introduction

Let $G(n,p)$ denote the random graph on the vertex set $V=\left\{{1,\ldots,n}\right\}$ in which any two vertices are connected with probability $p\in$ independently, known as the Erdős-Rényi model. Actually this model was introduced by Gilbert . In their seminal paper Erdős and Rényi consider a random graph $G(n,m)$ in which the number of edges is a fixed integer $m$ . However, with $p=m/{{n}\choose{2}}$ both models are essentially equivalent . We write $p=d/n$ and refer to $d$ as the average degree. As per common practice, we say that $G(n,d/n)$ has a property with high probability (‘w.h.p.’) if the probability that the property holds converges to $1$ as $n\rightarrow\infty$. We recall that a graph $G$ is $k$-colorable if it is possible to assign each vertex one of the colors $\left\{{1,\ldots,k}\right\}$ such that no edge connects two vertices of the same color. Moreover, the chromatic number $\chi(G)$ of a graph $G$ is the least integer $k$ such that $G$ is $k$-colorable. Unless specified otherwise, we always consider $d,k$ fixed as $n\rightarrow\infty$.

The theory of random graphs was born with the famous 1960 article by Erdős and Rényi , and has grown since into a substantial area of research with hundreds, perhaps thousands of contributions dealing with the $G(n,p)$ model alone. In their paper, Erdős and Rényi showed that the random graph $G(n,p)$ undergoes a percolation phase transition at $p=1/n$, and phase transitions have been the guiding theme of the theory ever since. In addition, Erdős and Rényi set the agenda for future research by posing a number of intriguing questions, all of which have been answered over the years except for one: for a given $d>0$, what is the typical chromatic number of $G(n,d/n)$?

Here and throughout, $o_{k}(1)$ denotes a term that tends to zero in the limit of large $k$. By comparison, a naive application of the union bound shows that

Recently , a more sophisticated union bound argument was used to prove

Theorem 1.1 enables us to pin the chromatic number down precisely on a set of asymptotic density $1$, thereby obtaining a near-complete answer to the question of Erdős and Rényi. More precisely, (1.2) and (1.4) imply

There exists a constant $k_{0}$ such that the following is true. Let

Set $F(d)=k$ for all $d\in S_{k}$. Then $S$ has asymptotic density $1$ and

Theorem 1.1 establishes the lower bound rigorously.

Additionally, the cavity method yields predictions on the combinatorial nature of the problem, particularly on the geometry of the set of $k$-colorings of the random graph. The proof of Theorem 1.1 is based on a “physics-enhanced” second moment argument that exploits this geometrical intuition. In fact, the physics intuition is one of two key ingredients that enable us to improve over the approach of Achlioptas and Naor . The second one is a novel approach, based on a local variations argument, to the analytical challenge of optimizing a certain (non-convex) function over the Birkhoff polytope. Neither of these ideas seem to depend on particular features of the graph coloring problem, and thus we expect that they will prove vital to tackle a variety of further related problems.

2. Related work

As witnessed by the notorious “four color problem” first posed by De Morgan in 1852, solved controversially by Appel and Haken in 1976 , and re-solved by Robertson, Sanders, Seymour and Thomas , the graph coloring problem has been a central subject in (discrete) mathematics for well over a century. Thus, it is unsurprising that the chromatic number problem on $G(n,p)$ has received a big deal of attention since it was posed by Erdős and Rényi. Indeed, the problem has inspired the development of techniques that are by now widely used in various areas of mathematics, computer science, physics and other disciplines.

For instance, pioneering the use of martingale tail bounds, Shamir and Spencer proved concentration bounds for the chromatic number of $G(n,p)$. Their result was enhanced first by Łuczak and then by Alon and Krivelevich , who used the Lovász Local Lemma to prove that the chromatic number of $G(n,p)$ is concentrated on two consecutive integers if $p\ll n^{-1/2}$. In a breakthrough contribution, Bollobás determined the asymptotics of the chromatic number of dense random graphs (i.e., $G(n,p)$ with $p>n^{-1/3}$). This result improved prior work by Matula , whose “merge-and-exposure” technique Łuczak built upon to obtain a similar result for sparser random graphs . However, in the case that $p=d/n$ for a fixed real $d>0$, the setting originally studied by Erdős and Rényi, Łuczak’s formula is far less precise than (1.1)–(1.2). For a comprehensive literature overview see .

The work of Achlioptas and Naor , which gave best prior result on the chromatic number of $G(n,d/n)$, is based on the second moment method. Its use in the context of phase transitions in random discrete structures was pioneered by Achlioptas and Moore and Frieze and Wormald . The techniques of have been used to prove several further important results. For instance, Achlioptas and Moore identified three (and for some $d$ just two) consecutive integers on which the chromatic number of the random $d$-regular is concentrated. This was reduced to two integers for all fixed of $d$ (and one for about half of all $d$) by adding in the small subgraph conditioning technique . Recently, the methods developed in this work have been harnessed to improve this result further still . Moreover, Dyer, Frieze and Greenhill extended the second moment argument from to the problem of $k$-coloring $h$-uniform random hypergraphs. We expect that our approach can be used to obtain improved results in the hypergraph case. Similarly, it should be possible to improve results of Dani, Moore and Olsen on a “decorated” coloring problem.

In several problems, sophisticated applications of the second moment method gave bounds very close to the predictions made by the physicists’ cavity method . Examples where the physics predictions have (largely) been verified rigorously in this way include the hypergraph $2$-coloring problem and the random $k$-SAT problem . But thus far a general limitation of the rigorous proof techniques has been that they only apply to binary problems where there are only two values available for each variable. By contrast, in random graph coloring each variable (vertex) has $k$ values (colors) to choose from, where $k$ can be arbitrarily large. As we will see in Section 2, the large number of available values complicates the problem dramatically. In effect, random graph coloring remained the last among the intensely-studied benchmark problems in which there remained a very substantial gap between the physics predictions and the rigorous results, a situation rectified by the present paper. Thus, we view this paper as an important step towards the long-term goal of providing a mathematical foundation for the cavity method.

3. Notation and preliminaries.

In addition to $G(n,p)$, we consider the $G(n,m)$ model, which is a random graph with vertex set $V=\left\{{1,\ldots,n}\right\}$ and exactly $m$ edges, chosen uniformly at random amongst all such graphs. Working with $G(n,m)$ facilitates the second moment argument because the total number of edges is a deterministic quantity. Nonetheless, Lemma 2.1 below shows that any results for $G(n,m)$ with $m=\lceil dn/2\rceil$ extend to $G(n,d/n)$. Thus, throughout the paper we always set $m=\lceil dn/2\rceil$.

Since our goal is to establish a statement that holds with probability tending to $1$ as $n\rightarrow\infty$, we are always going to assume tacitly that the number $n$ of vertices is sufficiently large for the various estimates to hold. Similarly, at the expense of the error term $o_{k}(1)$ in Theorem 1.1 we will tacitly assume that $k\geq k_{0}$ for a large enough constant $k_{0}$.

We use the standard $O$-notation to refer to the limit $n\rightarrow\infty$. Thus, $f(n)=O(g(n))$ means that there exist $C>0$, $n_{0}>0$ such that for all $n>n_{0}$ we have $|f(n)|\leq C\cdot|g(n)|$. In addition, we use the standard symbols $o(\cdot),\Omega(\cdot),\Theta(\cdot)$. In particular, $o(1)$ stands for a term that tends to $0$ as $n\rightarrow\infty$. Furthermore, we write $f(n)\sim g(n)$ if $\lim_{n\rightarrow\infty}f(n)/g(n)=1$.

If $G$ is a graph $v$ is a vertex of $G$, then we denote by $N_{G}(v)$ the neighborhood of $v$ in $G$, i.e., the set of all vertices $w$ that are connected to $v$ by an edge of $G$. Where the graph $G$ is apparent from the context we just write $N(v)$. If $s\geq 1$ is an integer, we write $\left[{s}\right]$ for the set $\left\{{1,2,\ldots,s}\right\}$. Moreover, throughout the paper we use the conventions that $0\ln 0=0$ and (consistently) that $0\ln\frac{0}{0}=0$.

Outline

Suppose that $Z=Z(G(n,m))\geq 0$ is a random variable such that $Z(G)>0$ implies that $G$ is $k$-colorable. Moreover, suppose that there is a number $C=C(d,k)>0$ that may depend on the average degree $d$ and the number of colors $k$ but not on $n$ such that

This inequality yields a lower bound on the $k$-colorability threshold.

2. Balanced colorings and the Birkhoff polytope.

To get started, we compute the first moment. By Stirling’s formula the number of balanced maps is $\left|{\mathcal{B}}\right|=\Theta(k^{n})$. Furthermore, for $\sigma$ to be a $k$-coloring, the random graph $G(n,m)$ must not contain any of the

“forbidden” edges that join two vertices with the same color under $\sigma$. If $\sigma$ is balanced, we easily check that $\mathcal{F}(\sigma)=(1-1/k){{n}\choose{2}}+O(n)$. Thus, letting $N={{n}\choose{2}}$ and using Stirling’s formula, we find that the probability that $\sigma$ is a $k$-coloring of $G(n,m)$ comes to

represent the proportion of vertices with color $i$ under $\sigma$ and color $j$ under $\tau$.

While in binary problems the relevant overlap parameter is just a $1$-dimensional (e.g., in random $k$-SAT, the Hamming distance of two truth assignments), here the high-dimensional overlap matrix is required. The need for this high-dimensional overlap parameter is what makes the $k$-colorability problem so difficult.

Uniformly for $\rho\in{\mathcal{R}}$ we have

Since the function $f$ turns out to be the key object in this paper, we include the simple proof to explain where it comes from combinatorially. By Stirling’s formula, the total number of $\sigma,\tau\in\mathcal{B}$ with overlap $\rho$ equals

Now, suppose that $\sigma,\tau$ have overlap $\rho$. By inclusion/exclusion, the number of “forbidden” edges joining two vertices with the same color under either $\sigma$ or $\tau$ equals

Let $N={{n}\choose{2}}$. Then Stirling’s formula yields

The assertion follows from (2.6), (2.7) and the linearity of expectation. ∎

The bound (2.5) is essentially tight as similar calculations show that

Moreover, by the linearity of expectation we can express the second moment as

As the total number of summands is $\left|{{\mathcal{R}}}\right|\leq n^{k^{2}}$, we obtain from (2.8) and (2.9) that

Further, because we work with balanced colorings, the row and column sums of any $\rho\in{\mathcal{R}}$ are $1+O(n^{-\frac{1}{2}})$. Thus, let $\mathcal{D}$ be the set of all doubly-stochastic $k\times k$ matrices, the Birkhoff polytope. Together with the continuity of $f$ and the observation that ${\mathcal{R}}\cap\mathcal{D}$ becomes a dense subset of $\mathcal{D}$ as $n\rightarrow\infty$, (2.10) implies that

3. The singly-stochastic bound.

Yet solving the optimization problem (2.11) proves seriously difficult. Achlioptas and Naor resort to a relaxation: with $\mathcal{S}\supset\mathcal{D}$ the set of all $k\times k$ singly stochastic matrices, they study

4. A physics-enhanced random variable.

Futher, to formalize the notion that the clusters are “well-separated”, we call a balanced $k$-coloring $\sigma$ separable if

In other words, the overlap matrix $\rho(\sigma,\tau)$ does not have entries in the interval $(0.51,1-\kappa)$. Hence, if two color classes have an overlap of more than $51\%$, then they must, in fact, be nearly identical. This definition ensures that the clusters of two separable colorings $\sigma,\tau$ are either disjoint or identical. We thus arrive at the following definition.

Let $G$ be a graph with $n$ vertices and $m$ edges. A $k$-coloring $\sigma$ of $G$ is tame if

In Section 3 we show that a typical $k$-coloring of $G(n,m)$ is indeed tame, which implies that the expected number of tame $k$-colorings satisfies the following.

is attained at $\bar{\rho}$. Indeed, that (2.16) mirrors the second moment calculation seems reasonable: for any two tame colorings $\sigma,\tau$ the overlap matrix $\rho(\sigma,\tau)$ is separable by T2. Moreover, if $\rho(\sigma,\tau)$ is $k$-stable, then $\tau\in{\mathcal{C}}(\sigma)$ by the very definition of ${\mathcal{C}}(\sigma)$, and T3 provides an a priori bound on the number of such $\tau$.

Thus, in a sense the proof strategy that we pursue is the opposite of the one from . While Achlioptas and Naor relax the optimization problem (by working with a rather significantly larger domain: singly rather than doubly-stochastic matrices), here we restrict the domain by imposing further physics-inspired constraints. This approach, carried out in Section 4, yields

Finally, Theorem 1.1 is an immediate consequence of Propositions 2.4 and 2.5 combined with Lemma 2.1.

5. The condensation phase transition

The first moment

Throughout this section we keep the assumptions of Proposition 2.4 and the notation introduced in Section 2.

The following lemma is the key step towards proving Proposition 2.4.

To establish Lemma 3.1, we denote by $G(n,m,\sigma)$ the random graph $G(n,m)$ conditional on the event that $\sigma\in\mathcal{B}$ is a $k$-coloring. Thus, $G(n,m,\sigma)$ consists of $m$ edges drawn uniformly at random without replacement out of those edges that are bichromatic under $\sigma$. This probability distribution is also known as the “planted model”.

To establish the bound T3 on the cluster size, we show that w.h.p. $G(n,m,\sigma)$ contains a vast “core” comprising of vertices that have several neighbors of each color other than their own that also belong to the core. Formally, if $G=(V,E)$ is a graph on the vertex set $V=\left\{{1,\ldots,n}\right\}$ and $\sigma\in\mathcal{B}$, we define the core of $(G,\sigma)$ as the largest subset $V^{\prime}\subset V$ such that

The core is well-defined: if $V^{\prime},V^{\prime\prime}$ satisfy (3.1), then so does $V^{\prime}\cup V^{\prime\prime}$. (Of course, the constant $100$ is a bit arbitrary.)

As we will see, due to expansion properties no vertex in the core of $G(n,m,\sigma)$ can be recolored without leaving the cluster ${\mathcal{C}}(\sigma)$ w.h.p. The basic reason is that recoloring any vertex $v$ in the core sets off an avalanche of recolorings: to give $v$ another color, we will have to recolor at least 100 vertices that also belong to the core, and so on.

In addition, if a vertex $v$ outside the core is such that for each color other than its own, $v$ has a neighbor in the core of that color, then it should be impossible to recolor $v$ without leaving ${\mathcal{C}}(\sigma)$ as well. For to assign $v$ some color $i\neq\sigma(v)$ we will have to recolor at least one vertex in the core. Guided by this observation, we call a vertex $v$ $\sigma$-complete, if for each color $i\neq\sigma(v)$, $v$ has a neighbor $w$ in the core with $\sigma(v)=i$.

If $\sigma$-complete vertices do not contribute to $|{\mathcal{C}}(\sigma)|$, then the cluster size stems from recoloring vertices $v$ that fail to have a neighbor in the core of some color $i\neq\sigma(v)$. As we shall see, most of these vertices miss out on exactly one color $i\neq\sigma(v)$ and hence have precisely two colors to choose from. Formally, we call a vertex $v$ $a$-free in $(G,\sigma)$ if, with $V^{\prime}$ denoting the core, we have $\left|{\left\{{i\in\left[{k}\right]:N(u)\cap V^{\prime}\cap\sigma^{-1}(i)=\emptyset}\right\}}\right|\geq a+1.$

The following lemma summarizes the expansion properties of $G(n,m,\sigma)$ that the proof of Lemma 3.1 builds upon.

Let $\sigma\in\mathcal{B}$ and assume that $2k\ln k-\ln k-2\leq d\leq 2k\ln k$. Let $V_{i}=\sigma^{-1}(i)$ for $i=1,\ldots,k$. Then w.h.p. the random graph $G(n,m,\sigma)$ has the following four properties.

Let $i\in\left[{k}\right]$. For any subset $S\subset V_{i}$ of size $0.509\cdot\frac{n}{k}\leq|S|\leq(1-k^{-0.499})\frac{n}{k}$, the number of vertices $v\in V\setminus V_{i}$ that do not have a neighbor in $S$ is less than $\frac{n}{k}-|S|-n^{2/3}$.

Let $i\in\left[{k}\right]$. No more than $\frac{\kappa n}{3k}$ vertices $v\not\in V_{i}$ have less than $15$ neighbors in $V_{i}$, where $\kappa=\ln^{20}k/k$.

There is no set $S\subset V$ of size $|S|\leq k^{-4/3}n$ that spans more than $5|S|$ edges.

The proof of Lemma 3.2 is based on arguments that are, by now, fairly standard; in particular, the “core” has, tweaked in various ways, become a standard tool . For the sake of completeness, we give a full proof of Lemma 3.2 in Appendix A. Here we proceed to show how Lemma 3.2 implies Lemma 3.1.

Assume that $2k\ln k-\ln k-2\leq d\leq 2k\ln k$ and let $\sigma\in\mathcal{B}$. Then $\sigma$ is separable in $G(n,m,\sigma)$ w.h.p.

By Lemma 3.2 we may assume that the random graph $G(n,m,\sigma)$ has the properties P1–P3. Suppose that $\tau\in\mathcal{B}$ is another $k$-coloring of this random graph and that $i,j\in\left[{k}\right]$ are such that $\rho_{ij}(\sigma,\tau)\geq 0.51$. Our aim is to show that $\rho_{ij}(\sigma,\tau)>1-\kappa$. Without loss of generality we may assume that $i=j=1$.

Let $R=\sigma^{-1}(1)\setminus\tau^{-1}(1)$, $S=\tau^{-1}(1)\cap\sigma^{-1}(1)$ and $T=\tau^{-1}(1)\setminus\sigma^{-1}(1)$. Because $\tau$ is a $k$-coloring, none of the vertices in $T$ has a neighbor in $S$. Furthermore, because $\tau$ is balanced we have $|S\cup T|\geq\frac{n}{k}-\sqrt{n}$, and thus $|T|\geq\frac{n}{k}-|S|-\sqrt{n}$. Since $|S|=\frac{n}{k}\rho_{11}(\sigma,\tau)>0.509\frac{n}{k}$, P1 implies that

Now, let $U$ be the set of all $v\in T$ that have at least $15$ neighbors in $\sigma^{-1}(1)$. Then all of these neighbors lie in $R$, because $\tau$ is a $k$-coloring. Further, as $\sigma,\tau$ are asymptotically balanced we obtain from (3.2)

Hence, P3 applies to $R\cup U$. By the definition of $U$ and P3, the number $e(R\cup U)$ of edges spanned by $R\cup U$ satisfies

Let $W=T\setminus U$. Because $W$ consists of vertices with fewer than $15$ neighbors in $\sigma^{-1}(1)$, P2 yields

Since $\sigma,\tau$ are balanced, we have

Finally, (3.5) and (3.6) imply that $\rho_{11}(\sigma,\tau)=\frac{k}{n}\cdot|S|=1+o(1)-\frac{k}{n}\cdot|R|>1-\kappa,$ as desired. ∎

As a next step, we are going to verify that the $\sigma$-complete vertices take the same color in all the colorings in ${\mathcal{C}}(\sigma)$ w.h.p.; a similar argument was used in .

Assume that $2k\ln k-\ln k-2\leq d\leq 2k\ln k$ and let $\sigma\in\mathcal{B}$. W.h.p. the random graph $G(n,m,\sigma)$ has the following property.

If $\tau\in{\mathcal{C}}(\sigma)$, then for all $\sigma$-complete vertices $v$ we have $\sigma(v)=\tau(v)$ w.h.p.

By Lemmas 3.2 and 3.3 we may assume that P3 holds and that $\sigma$ is separable in $G(n,m,\sigma)$. Let $V^{\prime}$ be the core of this random graph. Moreover, set

The assumptions that $\sigma$ is separable and that both $\sigma,\tau$ are asymptotically balanced imply that

By construction, this implies that $\sigma(v)=\tau(v)$ for all $\sigma$-complete vertices.

To establish (3.9), let $S_{i}=\Delta_{i}^{+}\cup\Delta_{i}^{-}$ for $i=1,\ldots,k$. Because $\Delta_{i}^{+}$ is contained in the core, each $v\in\Delta_{i}^{+}$ has at least $100$ neighbors in $\sigma^{-1}(i)$. Since $\tau$ is a $k$-coloring, all of these neighbors lie in the set $\Delta_{i}^{-}$. Hence, the number $e(S_{i})$ of edges spanned by $S_{i}$ is at least $100|\Delta_{i}^{+}|$. On the other hand, (3.8) implies that $|S_{i}|\leq k^{-4/3}n$ for all $i$. Therefore, P3 entails that $e(S_{i})\leq 5|S_{i}|$ for all $i$. Thus, we obtain $100|\Delta_{i}^{+}|\leq e(S_{i})\leq 5|S_{i}|\leq 5(\left|{\Delta_{i}^{+}}\right|+\left|{\Delta_{i}^{-}}\right|).$ Consequently, $|\Delta_{i}^{-}|\geq 2|\Delta_{i}^{+}|$ for all $i$. Thus, (3.7) shows that $\Delta_{i}^{+}=\Delta_{i}^{-}=\emptyset$ for all $i$, whence (3.9) follows. ∎

Let $\sigma\in\mathcal{B}$. We need to show that $G(n,m,\sigma)$ enjoys the properties T2–T3 from Definition 2.3 w.h.p. The fact that T2 holds w.h.p. follows directly from Lemma 3.3.

With respect to T3, by Lemma 3.4 we may assume that that for all $\sigma$-complete $v$ and all $\tau\in{\mathcal{C}}(\sigma)$ we have $\tau(v)=\sigma(v)$. Let $F_{j}$ be the set of $j$-free vertices for $j=1,2$. By Lemma 3.2 we may assume that

By construction, for any vertex $v\in F_{1}\setminus F_{2}$ there is a set $C_{v}\subset\left[{k}\right]$ of at most two colors such that $\tau(v)\in C_{v}$ for all $\tau\in{\mathcal{C}}(\sigma)$. Hence,

Combining (3.10) and (3.11), we see that w.h.p. in $G(n,m,\sigma)$,

The Second Moment

In this section we keep the assumptions of Proposition 2.5 and the notation introduced in Section 2.

The proof of Proposition 4.1, based on the Laplace method, is a mere technical exercise, which we put off to Section 5.

Thus, Proposition 2.5 is immediate from Propositions 4.1 and 4.2.

The proof of Proposition 4.2 is the heart of the second moment argument. Of course, we need to take a closer look at the function $f$. As we will see, it consists of two ingredients: an entropy term and a probability term. More specifically, suppose that $p:\Omega\rightarrow\left[{0,1}\right]$ is a probability distribution on a finite set $\Omega$ (i.e., $\sum_{x\in\Omega}p(x)=1$). Recalling our convention that $0\ln 0=0$, we denote by

the entropy of $p$. Since any $\rho\in\mathcal{D}$ satisfies $\sum_{i,j}\rho_{ij}=k$, we can view $k^{-1}\rho$ as a probability distribution on $\left[{k}\right]\times\left[{k}\right]$. Hence, we can write

Combinatorially, $E(\rho)$ corresponds to the (logarithm of the) probability that $\sigma,\tau\in\mathcal{B}$ with overlap $\rho$ simulataneously happen to be $k$-colorings, cf. the proof of Fact 2.2.

It is clear that the entropy is maximized at the barycentre $\bar{\rho}$ of the Birkhoff polytope, because $k^{-1}\bar{\rho}$ is the uniform distribution on $\left[{k}\right]\times\left[{k}\right]$. Furthermore, among all the matrices $\rho$ with non-negative entries that sum to $k$, $\bar{\rho}$ is the one that minimizes the Frobenius norm and hence $E(\rho)$. This shows that $\bar{\rho}$ is a stationary point of $f(\rho)$. But how do we prove that $\bar{\rho}$ is the global maximizer of $f$?

We start by showing that we may confine ourselves to matrices without an entry in the interval $(0.15,1-\kappa)$. Recall that $\mathcal{S}$ is the set of all singly-stochastic $k\times k$-matrices.

For all $\rho\in\mathcal{S}$ such that $\rho_{ij}\in\left[{0.15,0.51}\right]$ for some $(i,j)\in\left[{k}\right]\times\left[{k}\right]$ we have $f(\rho)<0$.

More precisely, the following fact is the cornerstone of the local variations argument. Let $\rho\in\mathcal{S}$, let $i\in\left[{k}\right]$ be a row index, and let $\emptyset\neq J\subset\left[{k}\right]$ be a set of column indices. Obtain $\hat{\rho}\in\mathcal{S}$ from $\rho$ by letting

That is, $\hat{\rho}$ is obtained by redistributing in row $i$ the total mass of the columns in $J$ equally over these columns. Clearly, the entropy satisfies $H(k^{-1}\hat{\rho})\geq H(k^{-1}\rho)$. In fact, this inequality is strict unless $\hat{\rho}=\rho$. However, it may well be that for the probability term we have $E(\hat{\rho})<E(\rho)$. The following proposition trades the increase in entropy against the drop in the probability term and shows that $f(\hat{\rho})\geq f(\rho)$ if $J$ is “not too small” and $\max_{j\in J}\rho_{ij}$ is “not too big”.

Suppose that $\rho\in\mathcal{S}$. Let $i\in\left[{k}\right]$ and $J\subset\left[{k}\right]$ be such that for some number $3\ln\ln k/\ln k\leq\lambda\leq 1$ we have $|J|\geq k^{\lambda}$. Moreover, assume that $\max_{j\in J}\rho_{ij}<\lambda/2-\ln\ln k/\ln k$. Then the matrix $\hat{\rho}$ from (4.1) satisfies $f(\hat{\rho})\geq f(\rho)$. In fact, if $\rho\neq\hat{\rho}$, then $f(\hat{\rho})>f(\rho)$.

Let us illustrate the use of Proposition 4.7 by proving

To obtain (4.2), we apply Proposition 4.7 to the $i$th row of $\rho[i-1]$ with $J=\left[{k}\right]$ and $\lambda=1$. This is possible because $\max_{j}\rho_{ij}[i-1]=\max_{j}\rho_{ij}\leq 0.15$. The resulting matrix $\hat{\rho}$ is precisely $\rho[i]$. Thus, (4.2) follows from Proposition 4.7. Indeed, Proposition 4.7 shows that one of the inequalities (4.2) is strict (as $\rho\neq\bar{\rho}$). Hence, $f(\rho)<f(\bar{\rho})$. ∎

Proposition 4.2 is immediate from Propositions 4.4–4.6 and Corollary 4.8. Thus, we are left to prove Propositions 4.3–4.7. In the Section 4.3 we prove Proposition 4.7. Building upon that estimate, we then proceed to prove Propositions 4.3–4.6. But before we start, we introduce a few pieces of notation and some basic facts.

2. Preliminaries.

denotes the entropy function. We recall the elementary inequality $h(z)\leq z(1-\ln z)$. In addition, we note that

Indeed, we have $h(z)-z\ln k\leq z(1-\ln z-\ln k)$ and differentiating twice, we see that $z\mapsto z(1-\ln z-\ln k)$ takes its global maximum $1/k$ at $z=1/k$.

We need the following well-known fact about the entropy.

Let $p\in\left[{0,1}\right]^{k}$ be such that $\sum_{i=1}^{k}p_{i}=1$. Then $H(p)\geq 0$ and the following two statements hold.

If $p$ is supported on a set of size $s$, then $H(p)\leq\ln s$.

Let $\mathcal{I}\subset\left[{k}\right]$ and suppose that $q=\sum_{i\in\mathcal{I}}p_{i}\in(0,1)$. Let $p^{\mathcal{I}}$ be the vector with entries

Then $H(p)=h(q)+qH(q^{-1}p^{\mathcal{I}})+(1-q)H((1-q)^{-1}(p-p^{\mathcal{I}})).$

As an immediate consequence of Fact 4.9, we have

Let $p\in\left[{0,1}\right]^{k}$ be such that $\sum_{i=1}^{k}p_{i}=1$.

Let $\mathcal{I}\subset\left[{k}\right]$ and set $q=\sum_{i\in\mathcal{I}}p_{i}$. Then $H(p)\leq h(q)+q\ln\left|{\mathcal{I}}\right|+(1-q)\ln(k-\left|{\mathcal{I}}\right|).$

Let $\mathcal{I}\subset\left\{{2,\ldots,k}\right\}$ be a set of size $0<\left|{\mathcal{I}}\right|<k-1$. Set $q=\sum_{i\in\mathcal{I}}p_{i}$. If $p_{1}<1$, then

The first claim follows simply by first using H2 and then applying H1 to $q^{-1}p^{\mathcal{I}}$ and $(1-q)^{-1}(p-p^{\mathcal{I}})$. To obtain the second assertion, use H2 with $\mathcal{I}=\left\{{1}\right\}$ and then apply (i) to the probability distribution $q^{-1}p^{\mathcal{I}}$. ∎

Let $\rho\in\mathcal{S}$ be a singly-stochastic matrix. We can view each row $\rho_{i}$ as a probability distribution on $\left[{k}\right]$. With this interpretation, we see that

To facilitate the following calculations, we note that

Moreover, differentiating $E(\rho)$ by $y=\left\|{\rho}\right\|_{2}^{2}$ and recalling that $d=2k\ln k+O_{k}(\ln k)$, we obtain

Further, using the expansion $\ln(1+z)=z+z^{2}/2+O(z^{3})$, we obtain the approximation

Since $f(\rho)=H(k^{-1}\rho)+E(\rho)$, (4.8) and (4.9) yield

3. Proof of Proposition 4.7.

We pursue the following strategy. Suppose that $a,b\in J$ are such that $\rho_{ia}=\min_{j\in J}\rho_{ij}$ and $\rho_{ib}=\max_{j\in J}\rho_{ij}$. If $\rho_{ia}=\rho_{ib}$, then $\rho=\hat{\rho}$ and there is nothing to prove. Otherwise, we are going to argue that increasing $\rho_{ia}$ slightly at the expense of $\rho_{ib}$ yields a matrix $\rho^{\prime}$ with $f(\rho^{\prime})>f(\rho)$. We start by calculating the partial derivatives of $f$.

Let $\rho\in\mathcal{S}$. Let $i,j,l\in\left[{k}\right]$ and set $\delta=\rho_{il}-\rho_{ij}$. Suppose that $\rho_{ij},\rho_{il}>0$. Then

Using (4.5), (4.6) and the chain rule, we obtain

Substituting $\delta=\rho_{il}-\rho_{ij}$, we find

Taking exponentials completes the proof. ∎

As a next step, we take a closer look at the right hand side of (4.11).

Let $\rho\in\mathcal{S}$, let $i,j\in\left[{k}\right]$ and assume that $\rho_{ij}>0$.

then there exists a unique $\delta^{*}>0$ such that

Furthermore, for all $0<\delta<\delta^{*}$ we have $1+\frac{\delta}{\rho_{ij}}-\exp\left[{\frac{d}{k-2+\frac{1}{k}\left\|{\rho}\right\|_{2}^{2}}\cdot\delta}\right]>0.$

If (4.12) does not hold, then for all $\delta>0$ we have $1+\frac{\delta}{\rho_{ij}}<\exp\left[{\frac{d}{k-2+\frac{1}{k}\left\|{\rho}\right\|_{2}^{2}}\cdot\delta}\right].$

There is at most one $\delta^{*}>0$ where the straight line $\delta\mapsto 1+\frac{\delta}{\rho_{ij}}$ intersects the strictly convex function

In fact, there is exactly one such $\delta^{*}$ iff the differential of the linear function is greater than that of the exponential function at $\delta=0$, which occurs iff (4.12) holds. ∎

Thus, (4.12) is satisfied. Further, setting $\hat{\delta}=\lambda/2-\ln\ln k/\ln k$, we find

4. Proof of Proposition 4.3

To proof is based on two key lemmas. The first one rules out that $f(\rho)$ takes its maximum over $\rho\in\mathcal{S}$ at a matrix with an entry close to $1/2$.

If $\rho\in\mathcal{S}$ has an entry $\rho_{ij}\in\left[{0.49,0.51}\right]$, then there is $\rho^{\prime}\in\mathcal{S}$ such that $f(\rho^{\prime})\geq f(\rho)+\frac{\ln k}{5k}$.

Without loss of generality we may assume that $(i,j)=(1,1)$ and that $\rho\in\mathcal{S}$ maximizes $f$ subject to the condition that $\rho_{11}\in\left[{0.49,0.51}\right]$. There are two cases.

Applying Proposition 4.7 to the set $J=\left\{{2,\ldots,k}\right\}$ (with $\lambda=\frac{\ln(k-1)}{\ln k}$), we see that $\rho_{1j}=\frac{1-\rho_{11}}{k-1}$ for all $j\geq 2$, due to the maximality of $f(\rho)$. Hence, Corollary 4.10 yields

Moreover, because $\rho_{11}\leq 0.51$ we have

Let $\rho^{\prime}$ be the matrix obtained from $\rho$ by replacing the first row by $(1,0,\ldots,0)$. Since $H(1,0,\ldots,0)=0$, (4.4) and (4.16) yield

Furthermore, (4.17) entails $\left\|{\rho}\right\|_{2}^{2}-\left\|{\rho^{\prime}}\right\|_{2}^{2}\leq\left\|{\rho_{1}}\right\|_{2}^{2}-1\leq-0.739.$ Hence, (4.6) yields

Combining (4.18) and (4.19), we obtain $f(\rho)-f(\rho^{\prime})\leq\frac{1}{k}\left[{\ln 2-0.22\ln k}\right]\leq-\frac{\ln k}{5k}$.

We may assume that $j=2$. Because $\sum_{j}\rho_{1j}=1$, we see that $\max_{j\geq 3}\rho_{1j}\leq 0.02$. Hence, we can apply Proposition 4.7 to $J=\left\{{3,\ldots,k}\right\}$ (with, say, $\lambda=1/2$). Due to the maximality of $f(\rho)$, we obtain $\rho_{1j}=(1-\rho_{11}-\rho_{12})/(k-2)$ for all $j\geq 3$. Hence, Corollary 4.10 yields

Further, because $\rho_{11}^{2}+\rho_{12}^{2}\leq 0.51^{2}+0.49^{2}$ as $\rho_{11},\rho_{12}\in\left[{0.49,0.51}\right]$ and $\rho_{11}+\rho_{12}\leq 1$, we see that

As in the first case, obtain $\rho^{\prime}$ from $\rho$ by replacing the first row by $(1,0,\ldots,0)$. From (4.21) we obtain $\left\|{\rho}\right\|_{2}^{2}-\left\|{\rho^{\prime}}\right\|_{2}^{2}\leq 0.501-1=-0.499$. Hence, (4.6) yields

Hence, in either case we obtain the desired bound. ∎

We have $\max_{\rho\in\mathcal{S}}f(\rho)\leq\frac{\ln k}{8k}+O_{k}(1/k).$

The proof of Lemma 4.14 requires two intermediate steps. We start with the following exercise in calculus.

Let $\xi:b\in(0,k/2)\mapsto k^{2b/k}(b^{-1}-k^{-1})$. Let $\mu=\frac{k}{2}(1-\sqrt{1-2/\ln k})$. Then $\xi$ is decreasing on the interval $(0,\mu)$ and increasing on $(\mu,k/2)$. Furthermore, we have

The first derivative vanishes at the two points $b=\frac{k}{2}(1\pm\sqrt{1-2/\ln k})$ only. Moreover, an elementary calculation shows that $\mu=\frac{k}{2}(1-\sqrt{1-2/\ln k})$ is a local minimum, while $\frac{k}{2}(1+\sqrt{1-2/\ln k})>k/2$ is a local maximum. Hence, $\xi$ is decreasing on the interval $(0,\mu)$ and increasing on $(\mu,k/2)$. The last assertion follows by direct inspection of the above expression for $\xi^{\prime}$. ∎

Let $\rho\in\mathcal{S}$. Suppose that $i\in\left[{k}\right]$ is such that $\rho_{ij}\not\in\left[{0.49,0.51}\right]$ for all $j\in\left[{k}\right]$.

Suppose that $\rho_{ij}\leq 0.49$ for all $j\in\left[{k}\right]$. Let $\rho^{\prime}$ be the stochastic matrix with entries

we have $f(\rho)\leq f(\rho^{\prime\prime}).$

To obtain the first assertion, we simply apply Proposition 4.7 to row $i$ and $J=\left[{k}\right]$ (with $\lambda=1$). With respect to the second claim, we may assume without loss that $i=j=1$ and $\rho_{11}\geq 0.51$. Let $\hat{\rho}\in\mathcal{S}$ be the matrix that maximizes $f$ subject to the conditions

$\hat{\rho}_{a}=\rho_{a}$ for all $a\in\left\{{2,\ldots,k}\right\}$. (In words, the last $k-1$ rows of $\hat{\rho}$ and $\rho$ coincide.)

Since $\hat{\rho}_{1j}\leq 1-\hat{\rho}_{11}\leq 0.49$ for all $j\geq 2$, Proposition 4.7 applies to $J=\left\{{2,\ldots,k}\right\}$ (with $\lambda=\frac{\ln(k-1)}{\ln k}$) and yields

Let $\delta=\hat{\rho}_{11}-\hat{\rho}_{12}$, let $0\leq\beta\leq 0.49k$ be such that $\hat{\rho}_{11}=1-\beta/k$ and let $Q=1-1/k+\|\hat{\rho}\|_{2}^{2}/k^{2}.$

Because $\hat{\rho}$ is the maximizer of $f$ subject to i. and ii., Lemma 4.11 implies that

First, we observe that $\beta>0$. For (4.5) shows that the derivative $\partial H(\rho_{1})/\partial\rho_{11}$ of the entropy of row $\rho_{1}$ tends to $-\infty$ as $\rho_{11}$ approaches $1$, while (4.6) implies that the derivative $\partial E(\rho)/\partial\rho_{11}$ remains bounded in absolute value. Hence, the maximality of $f(\rho)$ implies that $\beta>0$.

Further, since $\|\hat{\rho}\|_{2}^{2}\in\left[{1,k}\right]$, we have $Q\geq(1-1/k)^{2}$. Moreover, (4.24) implies that $\delta=\hat{\rho}_{11}-O_{k}(1/k)$. Therefore, recalling that $d=2k\ln k+O_{k}(\ln k)$, we obtain

Thus, with $\xi(b)=k^{2b/k}(b^{-1}-k^{-1})$ the function from Lemma 4.15, we see that for a certain $\eta=O_{k}(\ln k/k)$,

Let $\mu=\frac{k}{2}(1-\sqrt{1-2/\ln k})=(1+o_{k}(1))\frac{k}{2\ln k}$. By Lemma 4.15, $\xi$ is decreasing on $(0,\mu)$. Moreover, $\xi^{\prime}(b)$ is negative and bounded away from $0$ for $b$ close to $1$. Hence, setting $\gamma=\ln^{2}k/k$, we find

In addition, $\xi$ is increasing on $(\mu,k/2)$. Thus,

Plugging these two bounds into (4.26), we get

Similarly, because $\mu$ is the unique local minimum of $\xi$, we have

Let $\rho^{\prime}$ be the matrix obtained from $\rho$ by replacing the first $s$ rows by $(1,0,\ldots,0)$. This matrix satisfies

To complete the proof, we calculate $f(\rho^{\prime})$. Recall that $d=2k\ln k-\ln k-c$ with $c$ bounded. Moreover, (4.35) shows that $\left\|{\rho^{\prime}_{i}}\right\|_{2}^{2}=1$ for $i=1,\ldots,s$. In addition, since $\rho_{ij}^{\prime}=1/k$ for all $i>s$, $j\in\left[{k}\right]$, we get $\left\|{\rho_{i}^{\prime}}\right\|_{2}^{2}=1/k$ for $i>s$. Hence, $\left\|{\rho^{\prime}}\right\|_{2}^{2}=1+(1-1/k)s$. Thus, using (4.7) and performing an elementary calculation, we get

Further, $H(\rho_{i}^{\prime})=0$ for $i\leq s$, while $H(\rho_{i}^{\prime})=\ln k$ for $i>s$. Hence, (4.4) yields $H(k^{-1}\rho^{\prime})=\ln k+(1-s/k)\ln k=2\ln k-\frac{s}{k}\ln k$. Thus,

Finally, combining (4.39) and (4.40), we see that $f(\rho)\leq\frac{s}{k}(1-s/k)\cdot\frac{\ln k}{2k}+O_{k}(1/k)\leq\frac{\ln k}{8k}+O_{k}(1/k)$, as claimed. ∎

Suppose that $\rho\in\mathcal{S}$ has an entry $\rho_{ij}\in\left[{0.49,0.51}\right]$. We claim that $f(\rho)<0$. Indeed, by Lemmas 4.13 and 4.14

Now, suppose that $\rho\in\mathcal{S}$ has a row $i$ such that $\max_{j\in\left[{k}\right]}\rho_{ij}\in\left[{0.15,0.49}\right]$. Without loss of generality, we may assume $i=1$ and $\rho_{11}=\max_{j\in\left[{k}\right]}\rho_{ij}$. In fact, we may assume that $\rho$ is the maximizer of $f$ subject to the condition $\rho_{11}=\max_{j}\rho_{1j}\in\left[{0.15,0.49}\right]$. Again, we show that $f(\rho)<0$.

What can we say about this maximizer $\rho$? We apply Proposition 4.7 to $i=1$ and $J=\left\{{2,\ldots,k}\right\}$: if we let $\lambda=\ln(k-1)/\ln k$, then $|J|=k-1\geq k^{\lambda}$. Moreover, $\rho_{1j}\leq 0.49<\lambda/2-10/\ln k$ for all $j\in J$. Hence, Proposition 4.7 implies that

Thus, Corollary 4.10 shows that the entropy of $\rho_{1}$ is

By comparison, let $\hat{\rho}$ be the matrix obtained from $\rho$ by replacing the first row by \frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Then $H(\hat{\rho}_{1})=\ln k$. Therefore, (4.4) yields

Moreover, (4.41) yields $\left\|{\rho_{1}}\right\|_{2}^{2}=\rho_{11}^{2}+(1-\rho_{11})^{2}/(k-1)$ and $\left\|{\hat{\rho}_{1}}\right\|_{2}^{2}=1/k$, whence

Since $f(\hat{\rho})\leq\frac{\ln k}{8k}+O_{k}(1/k)$ by Lemma 4.14, we obtain from (4.43)

The assertion follows because $\rho_{11}(1-\rho_{11})>1/8$ for $\rho_{11}\in\left[{0.15,0.49}\right]$. ∎

5. Proof of Proposition 4.4

Let $\hat{\rho}$ be the singly-stochastic matrix with entries