When entropy meets Turán: new proofs and hypergraph Turán results

Turán’s original proof [62] works by a clever induction on the number of vertices by removing a $K_{r}$ from the graph. Erdős [17] later provided another proof that modified the graph step by step, maintaining the $K_{r+1}$-freeness and making the graph complete multipartite at the end. This method has the benefit that it is easier to see that the Turán graph $T_{n,r}$ is the extremizer. A proof of the same spirit is a folklore proof that proceeds with symmetrization (also known now as Zykov Symmetrization as this trick was used by Zykov [65, 66] in his work). The proof modifies the graph by taking two non-adjacent vertices, and replacing one with another (see [1, Chapter 41]). Unfortunately, all those proofs do not easily generalize to hypergraphs as they all use properties of graphs crucially.

One proof that looks entirely different from the previous proofs is by applying the Caro–Wei theorem, which is due to Alon and Spencer [2]. The Caro–Wei theorem, independently proven by Caro [8] and Wei [63], gives a lower bound on the independence number of a graph $G$ based on its degree sequence. The standard proof of the Caro–Wei theorem is a nice probabilistic argument, which can be found in [2]. By taking the complement and an application of Cauchy–Schwarz, the density Turán theorem immediately follows from Caro–Wei. However, this argument does not generalize well to higher uniformities—although the Caro–Wei theorem can be extended to hypergraphs (see [9]), applying the inequality on the complement no longer gives tight hypergraph Turán results.

Another proof that is seemingly different from all the above is a proof due to Motzkin and Straus [40]. Their proof relies crucially on a quantity called Lagrangian. The Lagrangian $L(G)$ of a graph $G=(V,E)$ is defined as

Despite its somewhat long definition, it is a natural quantity to consider in the context of Turán problems. To see this, let $N$ be some large positive integers. Consider the blowup of $G$ obtained by putting in $(x_{v}+o(1))N$ copies of each vertex $v\in V$ so that there are $N$ vertices in total, where $(x_{v})_{v\in V}$ is the extremizer for the Lagrangian. Then there are $(L(G)+o(1))N^{2}$ edges in the blowup. On the other hand, it is clear that $\left\lvert E\right\rvert\leq L(G)\left\lvert V\right\rvert^{2}$, which shows that the density Turán theorem is equivalent to that $L(G)\leq\frac{1}{2}\left(1-\frac{1}{r}\right)$ for every $K_{r+1}$-free graph $G$. Motzkin and Straus’ idea is that if $u$ and $v$ are not adjacent, then there is an extremizer with either $x_{u}=0$ or $x_{v}=0$ for $L(G)$. Therefore if $G$ is $K_{r+1}$-free, then there is an extremizer with support of size at most $r$. A simple application of Cauchy–Schwarz then concludes the proof. Despite its algebraic look, this proof is actually similar to Zykov Symmetrization in spirit.

It is natural to generalize graph Lagrangian to hypergraph Lagrangian. For any $k$-graph $G=(V,E)$, its hypergraph Lagrangian $L(G)$ is defined as the maximum of $\sum_{\{u_{1},\ldots,u_{k}\}\in E}x_{u_{1}}\cdots x_{u_{v}}$ under the same condition. As before, when each $v\in V$ is blown-up to $(x_{v}+o(1))N$ vertices where $(x_{v})_{v\in V}$ is the extremizer for the Lagrangian, there are $(L(G)+o(1))N^{k}$ edges in the blowup. As we will mostly talk about the density of a hypergraph rather than the number of edges, it is convenient to define $b(G)=k!L(G)$ to be the blowup density of $G$. Intuitively, it is the largest edge density of the blowups of $G$. As it turns out, hypergraph Lagrangian is indeed useful for some hypergraph Turán problems, and we will discuss some of those later in Section 1.3 and Section 8.

A lesser-known but nonetheless interesting algebraic argument was discovered by Li and Li [38]. There, they considered the polynomial

for any graph $G$. The key observation is that if $G$ is $K_{r+1}$-free, then $f$ vanishes whenever $r+1$ of the variables $(x_{v})_{v\in V(G)}$ are equal to one another. In light of this, let $I$ be the ideal of polynomials that vanish whenever $r+1$ of the variables are equal. Then $f\in I$, and Turán’s theorem follows from an explicit description of the generators of $I$ that Li and Li worked out.

Our proof looks different from all the proofs mentioned above. For graphs, our proof can be seen as a double-counting argument that, peculiarly, counts infinitely many objects. In particular, we will lower bound the number of stars of each size, and show that $K_{r+1}$-freeness actually imposes an upper bound on the numbers. An interesting feature our proof has is that in order to get the tight bound on the Turán density, it is necessary to take stars of any size into account. Despite the distinctive look of our proof, our proof is closely related to the standard probabilistic proof of the Caro–Wei theorem. In fact, if one runs the standard proof on the blowup of the graph, and take the size of the blowup to infinity, then the limit of the argument becomes our argument (we thank Maya Sankar for pointing this out to us).

In spite of the similarity to the proof of the Caro–Wei theorem, our counting argument has the advantage that it can be easily rephrased in terms of entropy. This will be crucial as it will inform us how we should adapt the proof for hypergraphs. We will therefore give an introduction to the entropy method in the next subsection.

The concept of entropy in the context of information theory was first formulated by Shannon in his seminal work in 1948 on the noisy-channel coding theorem [56]. Roughly speaking, the entropy of a random variable measures how much information the random variable carries. Using entropy, Shannon determined the best efficiency of a code transmitted through a noisy channel that can be corrected with high probability. This has become the foundation of information theory, and many other definitions of entropy have been made as well. However, in this paper, we will only use Shannon’s definition of entropy.

The adaptation of Shannon entropy in combinatorics and outside the context of information theory came much later in comparison. Some early examples include Chung, Frankl, Graham and Shearer’s work on triangle-intersecting family of graphs [12] (where Shearer’s inequality was introduced), Radhakrishnan’s entropic proof of the Brégman’s theorem [52], and Friedgut and Kahn’s theorem on the number of copies of a fixed hypergraph in another hypergraph with a given number of edges [26]. There is nonetheless a significant growth in work using the entropy method in the past decade or two. Two recent exciting, and perhaps unexpected, examples are Gilmer’s breakthrough on the union-closed set conjecture [27] and the work of Gowers, Green, Manners and Tao resolving Marton’s conjecture (also known as the polynomial Freimann–Ruzsa conjecture over $\mathbb{F}_{2}$) [28].

In the context of extremal graph theory, the entropy method is particularly useful when dealing with counts of homomorphisms or homomorphism densities. Here, for any $F,G$ that are graphs or general $k$-graphs, a homomorphism from $F$ to $G$ is a function $f:V(F)\to V(G)$ that sends edges of $F$ to edges of $G$. In particular, $f$ must be injective on any edge of $F$. The homomorphism density $t(F,G)$ is the probability that a uniformly random chosen function from $V(F)\to V(G)$ is actually a homomorphism. In this terminology, a corollary of the Kruskal–Katona theorem says that $t(K_{3},G)\leq t(K_{2},G)^{\frac{3}{2}}$, which follows immediately from Shearer’s inequality (see also [11] for an entropic proof of a slightly stronger result). In the last decade, the entropy method has been applied to show that various bipartite graphs $F$ are Sidorenko, i.e. $t(F,G)\geq t(K_{2},G)^{e(F)}$. This was first formalized by Szegedy [60] building on a previous work [37], and this was later adapted to attack Sidorenko’s conjecture [48, 15, 14, 13] and related problems [19, 36, 29, 5]. In fact, we will also prove some Sidorenko-type result using arguments similar to Szegedy’s in our entropic proofs.

Given how much the entropy method has been utilized to understand relations between homomorphism densities, it should be surprising that no entropic proof for Turán’s theorem was known. Indeed, an equivalent formulation of the density Turán theorem is that if $t(K_{r+1},G)=0$ then $t(K_{2},G)\leq 1-\frac{1}{r}$. In this paper, we give the first entropic proof of the density Turán theorem. To do so, we rephrase the density Turán theorem in the following way, and we will later show the equivalence between the two formulations. Below, and throughout the paper, we use $\mathbb{H}(X)$ to denote the Shannon entropy of a random variable $X$ (see Section 3 for definitions and basic properties).

We make a brief remark that the equivalence is shown via an entropic reinterpretation of blowup density and Langrangian. Indeed, it turns out that for a given graph $G$, the maximum of the quantity $\mathbb{H}(X,Y)-2\mathbb{H}(X)$ for symmetric $V(G)$-valued random variables $X,Y$ with $\{X,Y\}\in E(G)$ is related to the blowup density $b(G)$ of $G$. More surprisingly, the maximum of $\mathbb{H}(X,Y)-\mathbb{H}(X)$ is related to the spectral radius $\rho(G)$ of $G$. Those connections will be made precise and proven in Section 5, where we also generalize the connections to hypergraphs. One benefit is that as an immediate corollary of our entropic Turán theorem, we can generalize spectral Turán theorems established by Wilf [64] and Nikiforov [44, 45].

To see that this is indeed a generalization of Wilf’s and Nikiforov’s results, we can take $T$ to be the path $P_{\ell}$ on $\ell$ vertices. Wilf’s result corresponds to $\ell=1$, whereas Nikiforov’s results correspond to $\ell=2$ and general $\ell$.

Using the idea from our entropic proof of the density Turán theorem, we can determine the Turán densities for some new family of hypergraphs. Before presenting our results, let us first introduce some definitions and previous work that are relevant.

For any family of $k$-graphs $\mathcal{F}$, its Turán number $\textup{ex}(n,\mathcal{F})$ is defined to be the maximum number of edges in a $k$-graph $G$ that is $F$-free for every $F\in\mathcal{F}$. The Turán density is defined analogously by $\pi(\mathcal{F})=\lim_{n\to\infty}\textup{ex}(n,\mathcal{F})/\binom{n}{k}$. For any family of $k$-graphs $\mathcal{F}$ and a $k$-graph $G$, we say that $G$ is $\mathcal{F}$-hom-free if there does not exist any homomorphism $F\to G$ for every $F\in\mathcal{F}$. A $F$-hom-free $k$-graph is simply a $k$-graph that is $\{F\}$-hom-free.

It is a standard result in the field that $\pi(\mathcal{F})$ is the supremum of $b(G)$ where $G$ runs through all $\mathcal{F}$-hom-free $k$-graphs (see [32, Section 2] or [55, Lemma 2.2] for example). Notice that a single edge has blowup density $k!/k^{k}$, showing that $b(G)\geq k!/k^{k}$ if $G$ is not empty. This immediately shows that either $\pi(\mathcal{F})=0$ or $\pi(\mathcal{F})\geq k!/k^{k}$ for any family of $k$-graphs $\mathcal{F}$. We see that among the possible values of Turán density, there is a “jump” going from $0$ to $k!/k^{k}$. When $k=2$, this is indeed the behavior of Turán densities: the Erdős–Stone theorem shows that all possible values are $0,\frac{1}{2},\frac{2}{3},\frac{3}{4},\ldots$, showing that there are only jumps in the case of graphs. However, for hypergraphs, the set of possible Turán densities has a different behavior. It was first discovered by Frankl and Rödl [24] that for each $k\geq 3$, there are infinitely many non-jumps $\delta$, where for every $\varepsilon>0$ there exists a family $\mathcal{F}$ of $k$-graphs with $\pi(\mathcal{F})\in(\delta,\delta+\varepsilon)$. On the other hand, Baber and Talbot [3] showed that jumps do exist above $k!/k^{k}$ when $k=3$. However, our understanding in jumps and non-jumps is still limited, and we do not even know whether $k!/k^{k}$ is a jump.

A standard argument shows that $k!/k^{k}$ is a jump if and only if there exists a finite family $\mathcal{F}$ of $k$-graph with $\pi(\mathcal{F})=k!/k^{k}$ and $b(F)>k!/k^{k}$ for each $F\in\mathcal{F}$ (see [24]). The fact that we do not know whether $k!/k^{k}$ is a jump can thus be seen as a result of not having sufficient understanding in the families $\mathcal{F}$ with $\pi(\mathcal{F})=k!/k^{k}$. Indeed, known families with Turán densities equal to $k!/k^{k}$ are so few that we can list them here. For general $k$, Mubayi [41] showed that the $k$-uniform extended clique $E^{(k)}_{k+1}$ of size $k+1$ has Turán density $k!/k^{k}$. Here, the extension of a hypergraph is another hypergraph with higher uniformity obtained by adding different vertices into the edges, and an extended clique is an extension of a complete graph. In particular, $E^{(k)}_{k+1}$ is obtained by adding $k-2$ extra vertices to each edge of $K_{k+1}$, where no two edges share any extra vertices. This was later generalized by Mubayi and Pikhurko [42], who showed that the hypergraph $\Delta_{(1,1,\ldots,1)}$ with edges

also has Turán density $k!/k^{k}$. Here, and later whenever the vertex set is not explicitly described, the vertex set consists of vertices that appear in the description of the edges. Mubayi and Pikhurko’s result is indeed an improvement as $E^{(k)}_{k+1}$ is homomorphic to $\Delta_{(1,1,\ldots,1)}$, showing that $E^{(k)}_{k+1}$-hom-free graphs are also $\Delta_{(1,1,\ldots,1)}$-hom-free and so $\pi(E^{(k)}_{k+1})\leq\pi(\Delta_{(1,1,\ldots,1)})$.

We remark that both Mubayi’s [41] and Mubayi and Pikhurko’s [42] results are stronger—the exact Turán numbers were determined for sufficiently many vertices. If we only care about the Turán density, then an argument of Sidorenko [57] based on hypergraph Lagrangian can be modified to show that $\pi(\Delta_{(1,\ldots,1)})=k!/k^{k}$ as well—this is an observation by Keevash [32, Theorem 3.1].

For smaller $k$’s, slightly more is known. When $k=3$, Bollobás [6] showed that $\pi(\{K_{4}^{-},F_{5}\})=\frac{2}{9}$ where $K_{4}^{-}=\{123,124,134\}$ and $F_{5}=\{123,124,345\}$. This was improved by Frankl and Füredi [25], who showed that $\pi(F_{5})$ is already equal to $\frac{2}{9}$. Using flag algebra, Baber and Talbot [4] improved this further by showing that $\pi(\{123,124,345,156\})=\frac{2}{9}$. Finally, when $k=4$, Pikhurko [49] showed that $\pi(\{1234,1235,4567\})=\frac{3}{32}$.

As shown above, not a lot is known about families $\mathcal{F}$ of $k$-graphs with $\pi(\mathcal{F})=k!/k^{k}$. As an application of our entropic proof of the density Turán theorem, we will generalize our argument to show $\pi(\mathcal{F})=k!/k^{k}$ for a new family $\mathcal{F}$ of $k$-graphs. Our method has a benefit that we may first come up with an argument and then see what family of $k$-graphs need to be forbidden in order for the argument to work. We believe that this advantage can help discovering more families $\mathcal{F}$ with minimum positive Turán densities.

To state our result, for any partition $\lambda$ of $k$, let $\lambda=(\lambda_{1},\ldots,\lambda_{\ell})$ where $\ell=\ell(\lambda)$ is the length of $\lambda$, and $\lambda_{1}\geq\cdots\geq\lambda_{\ell}$. We also denote $\sum_{i=1}^{\ell}\lambda_{i}$ by $\left\lvert\lambda\right\rvert$ (which is equal to $k$ by definition). For any $\lambda$ with $\ell(\lambda)\geq 2$, we define the $\lambda$-tent, denoted by $\Delta_{\lambda}$, to be the following $k$-graph. The $\lambda$-tent comes with an edge $e$ that is the base and a vertex $v$ that is the apex. Setting $\ell=\ell(\lambda)$ to be the length of $\lambda$, for each $i\in[\ell]$ we also have an edge $e_{i}$ containing $v$ such that $\left\lvert e_{i}\cap e\right\rvert=\lambda_{i}$. Moreover, we require that $e_{i}\cap e_{j}=\{v\}$ for any $i\neq j\in[\ell]$. It is clear that this determines $\Delta_{\lambda}$ uniquely up to isomorphism—in fact, we must have $e\cap e_{1},\ldots,e\cap e_{\ell}$ partition $e$. It is easy to check that this definition matches the definition of $\Delta_{(1,1,\ldots,1)}$ above, $F_{5}=\Delta_{(2,1)}$ (with base $123$ and $4$ being the apex) and Pikhurko’s result can be rephrased as $\pi(\Delta_{(3,1)})=\frac{3}{32}$. Our result can now be stated as follows.

Note that this is a stronger statement than Mubayi’s and Mubayi and Pikhurko’s results. In fact, $\Delta_{(1,1,\ldots,1)}$ admits a homomorphism to $\Delta_{\lambda}$ for every $\left\lvert\lambda\right\rvert=k$ and $\ell(\lambda)=2$, which shows that $\pi(\Delta_{(1,1,\ldots,1)})\leq\pi(\mathcal{F}_{k})$. Using the same argument, we can transform Theorem 1.4 into a Turán result of a single $k$-graph.

Although when $k=3$ and $4$, Theorem 1.5 is subsumed by the known results mentioned above, this gives a new Turán result for larger $k$’s. To show that this should be a nontrivial result for larger $k$’s, we prove the following result in the opposite direction.

Theorem 1.5 shows that the constant in Theorem 1.6 cannot be smaller than $1/2$, and it seems like an interesting question to determine the best possible value of $\alpha$. It might help us understand the $k$-graphs $F$ with $\pi(F)=k!/k^{k}$ as well. We leave this as a future direction for interested readers.

Beyond showing $\pi(\mathcal{F})=k!/k^{k}$ for various families $\mathcal{F}$ of $k$-graphs, our method also applies to some other scenarios where the extremizers are blowups of complete hypergraphs. Unfortunately, we have not been able to find an argument that proves a new and clean statement in those settings. We nonetheless include the arguments later in Section 8 in the hope that they will be enlightening for readers interested in adapting our arguments. The relevant background will also be introduced there.

We will first present our new proof of the density Turán theorem in Section 2. We will then introduce the necessary entropic tools in Section 3, which will set us up for Section 4, where we rephrase our proof in terms of entropy. In Section 5, we will show how our entropic formulation captures quantities such as hypergrpah Lagrangian and spectral radius. We will use the connection to prove the spectral Turán theorems and the equivalence between the entropic Turán theorem and the density Turán theorem. In Section 6, we set up some notations and propositions that will be useful in the later sections. In Section 7, we will apply the entropic argument in Section 4 to show Theorem 1.4 in two different ways, and we will also prove Theorems 1.5 and 1.6. Some further generalization of our arguments is included in Section 8, where we also introduce some related known results. Finally, we will end with some concluding remarks in Section 9.

For any discrete random variable $X$, we write $p_{X}(x)\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\mathbb{P}(X=x)$. Also, we denote by $\operatorname{supp}(X)$ the support of $X$, i.e. the set of all $x$ such that $p_{X}(x)>0$. Through out this paper, the random variables we will consider are always discrete with finite support, i.e. $\left\lvert\operatorname{supp}(X)\right\rvert<\infty$. For any such random variable, we may define its Shannon entropy.

We also define the conditional entropy of $X$ given $Y$.

Using the definition of conditional entropy, we have the following chain rule.

The following proposition says that on a fixed support, the entropy is maximized by the uniform distribution on that support.

We will also need the following two propositions about entropy.

In this subsection, the concern is what is called the mixture of random variables.

In our applications, we will consider mixtures of random variables whose supports do not overlap too much.

With the definitions above, we may state our lemma about an upper bound on the entropies of random variables with $(a+1)$-wise disjoint supports, in terms of the entropy of their mixture.

The following example shows that Lemma 3.9 resembles a double counting on $(a+1)$-wise disjoint sets. Thus, the mixture bound can be viewed as an entropic version of this double counting.