Hypergraphs with infinitely many extremal constructions

- Center for Discrete Mathematics, Fuzhou University

- Center for Discrete Mathematics, Fuzhou University

- Mathematics Institute, University of Warwick
**ORCID iD:**0000-0002-0731-8084- More about Xizhi Liu

- Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago
- More about Dhruv Mubayi

- Center for Discrete Mathematics, Fuzhou University

*Discrete Analysis*, December. https://doi.org/10.19086/da.88508.

### Editorial introduction

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∈A, b∈B and c∈C, we can add all edges of the form a1a2b, b1b2c and c1c2a. 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 ab1b2, 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 F of 3-uniform hypergraphs such that, writing ex(F) for the asymptotically extremal density of an F-free 3-uniform hypergraph, there is not some bounded s such that for each n, every F-free hypergraph with n vertices and of density close to ex(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 F as follows. It is the minimum s such that for every n we can find hypergraphs G1(n),…,Gs(n) such that for every ϵ>0 there exists δ>0 such that every F-free hypergraph with n vertices and of density at least ex(F)−ϵ can be δ-approximated by one of G1(n),…,Gs(n). (Note that everything here is up to isomorphism, so the approximation is by an isomorphic copy of one of the Gi(n). A δ-approximation is one for which the symmetric difference has size at most δn3.) 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 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 F of k-uniform hypergraphs. This is the set of all (x,y)∈[0,1]2 such that there is a sequence F1,F2,… of k-uniform F-free hypergraphs with size tending to infinity such that the density of Fi tends to x and the density of the lower shadow of Fi (that is, the set of all sets of size k−1 that are contained in an edge of Fi) 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.