Hypergraphs with infinitely many extremal constructions
This paper studies the extension of Turán numbers to \(r\)-uniform hypergraphs (a collection of \(r\)-subsets of a finite set \(V\)), which are here called \(r\)-graphs. Given a family \(\mathcal F\) of \(r\)-graphs, an \(r\)-graph is said to be \(\mathcal F\)-free if it does not contain any member of \(\mathcal F\) as a subgraph. The Turán number ex\((n, {\mathcal F})\) of \(\mathcal F\) is the maximum number of edges in an \(\mathcal F\)-free \(r\)-graph on \(n\) vertices. The Turán density is defined to be \(\pi{\mathcal F}=\lim_{n \to \infty}\mbox{ex}(n, {\mathcal F})/\binom{n}{r}\), and the family \(\mathcal F\) is said to be nondegenerate if \(\pi(\mathcal F)>0\). A central problem in this area is proving Turán's Conjecture that, for every \(\ell\geq3\), \(\pi(K_{\ell+1}^3) = 1 - 4/\ell^2\), where \(K_\ell^r\) is the complete \(r\)-graph on \(\ell\) vertices.\N\NIn this remarkable paper, the authors' intention is to give results whose flavour is showing that phenomena which are impossible for graphs are possible for \(r\)-graphs, akin to the results by \textit{P. Frankl} and \textit{V. Rödl} [Combinatorica 4, 149--159 (1984; Zbl 0663.05047)] and \textit{O. Pikhurko} [Isr. J. Math. 201, Part A, 415--454 (2014; Zbl 1302.05097)].\N\NMany families \(\mathcal F\) have the property that there is a unique \(\mathcal F\)-free \(\mathcal G\) on \(n\) vertices achieving ex\((n, {\mathcal F})\), and moreover, any \(\mathcal F\)-free hypergraph \(\mathcal H\) of size close to ex\((n, {\mathcal F})\) can be transformed to \(\mathcal G\) by very few edits, that is, deletion or addition of edges. This property is called the stability of \(\mathcal F\). Here, the authors' main result is to give the first exact stability results with infinitely many extremal constructions that are far from each other in the edit distance. Their novel approach is to construct certain multinomial polynomials by which they define an operation on hypergraphs such that the maxima of the polynomials give extremal hypergraph constructions.
- Non-degenerate hypergraphs with exponentially many extremal constructions
- Two stability theorems for \(\mathcal{K}_{\ell + 1}^r\)-saturated hypergraphs
- Toward a density Corrádi-Hajnal theorem for degenerate hypergraphs
- Finite hypergraph families with rich extremal Turán constructions via mixing patterns
- Hypergraphs with many extremal configurations
- A criterion for Andrásfai-Erdős-Sós type theorems and applications
This page was built for publication: Hypergraphs with infinitely many extremal constructions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6962329)
