A hypergraph Turán problem with no stability (Q2095110)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A hypergraph Turán problem with no stability |
scientific article |
Statements
A hypergraph Turán problem with no stability (English)
0 references
9 November 2022
0 references
Let \(\mathcal{F}\) be a family of \(r\)-uniform hypergraphs (henceforth \(r\)-graphs), for \(r\geq 3\). An \(r\)-graph \(\mathcal{H}\) is \(\mathcal{F}\)-free if no member of \(\mathcal{F}\) is a subgraph of \(\mathcal{H}\). The Turán number \({\text{ex}}(n, \mathcal{F})\) of \(\mathcal{F}\) is the maximum number of edges in an \(\mathcal{F}\)-free \(r\)-graph on \(n\) vertices, and the Turán density \(\pi(\mathcal{F})\) of \(\mathcal{F}\) is \(\pi(\mathcal{F}) :=\lim_{n\to \infty} {\text{ex}}(n, \mathcal{F})/{n \choose r}\). The \textit{stability of} the family \(\mathcal{F}\) is the property (informally) that there is a unique \(\mathcal{F}\)-free \(r\)-graph \(\mathcal{G}\) on \(n\) vertices with \({\text{ex}}(n, \mathcal{F})\) edges, and moreover, any \(\mathcal{F}\)-free \(r\)-graph with number of edges \textit{close} to \({\text{ex}}(n,\mathcal{F})\) can be transformed to \(\mathcal{G}\) by deleting and adding \textit{few} edges only.\par The paper describes a family of \(3\)-graphs \(\mathcal{M}\) such that there are two near-extremal \(\mathcal{M}\)-free \(3\)-graphs that are far from each other. Moreover, the paper determines the Turán density and the Turán number of \(\mathcal{M}\). \(\mathcal{M}\) is the first known family not having the stability property for which the Turán number is known.
0 references
fundamental barrier
0 references
extremal hypergraph theory
0 references
Turán's conjecture
0 references
hypergraph family
0 references
stability theorem
0 references
edge density
0 references
Turán density
0 references
combinatorial theory
0 references