Hypergraphs with infinitely many extremal constructions

Hypergraphs with infinitely many extremal constructions, Discrete Analysis 2023:18, 34 pp.

A fundamental result in extremal graph theory, Turán’s theorem, states that the maximal number of edges of a graph with $n$ vertices that does not contain a clique with $r$ vertices is attained by a complete $(r-1)$-partite graph with all its parts of equal size, or as close to equal size as divisibility constraints allow. The theorem can be proved with a short inductive argument, and finds its way into many undergraduate courses in graph theory.

An obvious follow-up question is whether a similar result holds for hypergraphs. For example, is the maximal number of edges in a 3-uniform hypergraph with $n$ vertices that does not contain a clique with $k$ vertices (that is, a set $A$ of $k$ vertices such that all subsets of $A$ of size 3 belong to the hypergraph) attained by a complete $(k-1)$-partite 3-uniform hypergraph with vertex sets of (almost) equal size?

As posed, this question is not too hard, because the answer turns out to be no, even when $k=4$. Indeed, in that case, not only is a complete tripartite hypergraph not of maximal size, it is not even maximal, since if the vertex sets are $A, B$ and $C$ and we already have all edges $abc$ with $a\in A$, $b\in B$ and $c\in C$, we can add all edges of the form $a_1a_2b$, $b_1b_2c$ and $c_1c_2a$. To see that this does not create a clique of size 4, note that such a clique would have to have two vertices in the same vertex set. If that vertex set is $A$, say, then the other two vertices have to belong to $B$, but then we have an edge $ab_1b_2$, which is not allowed. If $A$, $B$ and $C$ have equal size, then the probability that three random vertices are in different vertex sets is $2/9$, and the probability that two of them are in $A$ and the third in $B$ is approximately $1/9$, so the density of the hypergraph is approximately $2/9+3/9=5/9$.

Of course, the next question is whether this slightly more complicated example is the extremal one, and more generally what the greatest possible density is of a 3-uniform hypergraph that contains no clique of size 4. This is one of the most famous open problems in extremal combinatorics.

It is conjectured that the extremal density is 5/9, but a sign that the conjecture is hard is that if the conjecture is true, the example just presented is not the extremal example, but merely an extremal example, as it is now known that there is an infinite family of 3-uniform hypergraphs with no cliques of size 4 and with asymptotic density 5/9.

Thus, the hypergraph problem appears to be markedly more complex than the graph one. The word “appears” is there because we don’t actually know that there is an infinite family of extremal examples, because we don’t know that they are extremal!

That raises another question. Is there any example of a Turán-type problem for hypergraphs for which one can prove that there is an infinite family of extremal examples? That is the question addressed and answered by this paper, which gives an example (in fact, more than one example) of a finite set $\mathcal F$ of 3-uniform hypergraphs such that, writing $\text{ex}(\mathcal F)$ for the asymptotically extremal density of an $\mathcal F$-free 3-uniform hypergraph, there is not some bounded $s$ such that for each $n$, every $\mathcal F$-free hypergraph with $n$ vertices and of density close to $\text{ex}(\mathcal F)$ can be approximated by one of $s$ hypergraphs with $n$ vertices. (The answer was known for exactly extremal examples: there is a 3-uniform hypergraph $F$ for which extremal $F$-free hypergraphs can be built with the help of Steiner triple systems, and any Steiner triple system can be used.)

More precisely, let us define the stability number of a family $\mathcal F$ as follows. It is the minimum $s$ such that for every $n$ we can find hypergraphs $G_1(n),\dots,G_s(n)$ such that for every $\epsilon>0$ there exists $\delta>0$ such that every $\mathcal F$-free hypergraph with $n$ vertices and of density at least $\text{ex}(\mathcal F)-\epsilon$ can be $\delta$-approximated by one of $G_1(n),\dots,G_s(n)$. (Note that everything here is up to isomorphism, so the approximation is by an isomorphic copy of one of the $G_i(n)$. A $\delta$-approximation is one for which the symmetric difference has size at most $\delta n^3$.) Previously it was known that finite families with arbitrarily large finite stability number existed. In this paper, the authors give an example, not conditional on any unproved hypotheses, of a finite family $\mathcal F$ with infinite stability number.

To construct the families, the authors introduce and use an operation on hypergraphs that they call a crossed blowup. To analyse them, they use some observations about multilinear polynomials, which are connected to Turán densities via a concept known as a hypergraph Lagrangian, which was introduced by Frankl and Rödl.

Their methods also allow them to answer a question about the feasible region of a family $\mathcal F$ of $k$-uniform hypergraphs. This is the set of all $(x,y)\in[0,1]^2$ such that there is a sequence $F_1,F_2,\dots$ of $k$-uniform $\mathcal F$-free hypergraphs with size tending to infinity such that the density of $F_i$ tends to $x$ and the density of the lower shadow of $F_i$ (that is, the set of all sets of size $k-1$ that are contained in an edge of $F_i$) tends to $y$. The shape of this region is known to be the area below the graph of a reasonably nice function supported on an interval $[0,c]$. However, it was an open problem whether the function could have infinitely many global maxima. For the main family constructed by the authors, it turns out that the associated function attains its maximum everywhere on an interval, so they solve this problem in a strong way.

Thus, the paper is a valuable contribution to the extremal theory of hypergraphs, and sheds interesting light on a notorious old conjecture.