A linear hypergraph extension of Turán's theorem (Q2112579)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear hypergraph extension of Turán's theorem |
scientific article |
Statements
A linear hypergraph extension of Turán's theorem (English)
0 references
11 January 2023
0 references
An \(r\)-uniform hypergraph is said to be linear if every two edges intersect in at most one vertex. For a family of \(r\)-uniform hypergraphs \(\mathcal{F}\), the linear Turán number \(ex_{r}^{lin} (n,F)\) is the maximum number of edges of a linear \(r\)-uniform hypergraph with \(n\) vertices that does not contain any member of \(\mathcal{F}\) as a subgraph. The \(r\)-expansion of a complete graph \(K_{l}\) with \(l\) vertices and \(r\geq 2\) is the \(r\)-graph \(K^{+}_{l}\) obtained from \(K_{l}\) by enlarging each edge of \(K_{l}\) with a vertex set of size \(r-2\) disjoint from \(V(K_{l})\) such that distinct edges of \(K_{l}\) are enlarged by disjoint sets. Let \(T_{2}(n, l)\) be the Turán graph, that is, an almost balanced complete \(l\)-partite graph with \(n\) vertices. For \(l \geq r \geq 3\) and \(n\) being sufficiently large, the authors prove the extension of Turán's Theorem \[ ex_{r}^{lin}(n,K^{+}_{l+1}\leq \frac{ |T_{2}(n, l)|}{\binom {r}{2}}, \] with equality if and only if there exist almost balanced \(l\)-partite \(r\)-graphs such that each pair of vertices from distinct parts are contained in exactly one hyperedge. Also, the authors give some results on linear Turán number of general configurations.
0 references
linear hypergraph
0 references
Turan's theorem, complete \(l\)-partite graph
0 references
0 references