On a hypergraph Turán problem of Frankl

DOI10.1007/S00493-005-0042-2zbMATH Open1089.05075arXivmath/0211179OpenAlexW2078034676MaRDI QIDQ2368596FDOQ2368596

Benny Sudakov, Peter Keevash

Publication date: 27 June 2006

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Let $C_r^{2k}$ be the $2k$-uniform hypergraph obtained by letting $P_1,\mathrm{...},P_r$ be pairwise disjoint sets of size $k$ and taking as edges all sets $P_{i}cup{P}_j$ with $ieqj$. This can be thought of as the `$k$-expansion' of the complete graph $K_r$: each vertex has been replaced with a set of size $k$. We determine the exact Turan number of $C_3^{2k}$ and the corresponding extremal hypergraph, thus confirming a conjecture of Frankl. Sidorenko has given an upper bound of $(r-2)/(r-1)$ for the Tur'an density of $C_r^{2k}$ for any $r$, and a construction establishing a matching lower bound when $r$ is of the form $2^p+1$. We show that when $r=2^p+1$, any $C_r^4$-free hypergraph of density $(r-2)/(r-1)-o(1)$ looks approximately like Sidorenko's construction. On the other hand, when $r$ is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Tur'an density of $C_r^4$ to $(r-2)/(r-1)-c(r)$, where $c(r)$ is a constant depending only on $r$. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal-Katona theorem and properties of Krawtchouck polynomials.

Full work available at URL: https://arxiv.org/abs/math/0211179

zbMATH Keywords

extremal problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05)

Cited In (35)

• Title not available (Why is that?)
• Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs
• Stability theorems for cancellative hypergraphs
• Optimal strong parity edge-coloring of complete graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Codegree problems for projective geometries
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• On vertex independence number of uniform hypergraphs
• A unified approach to hypergraph stability
• Turán problems on non-uniform hypergraphs
• On the algebraic and topological structure of the set of Turán densities
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• On \(k\)-uniform random hypergraphs without generalized fans
• Two-regular subgraphs of hypergraphs
• A hypergraph extension of Turán's theorem
• Counting substructures. II: Hypergraphs
• Co-degree density of hypergraphs
• Set systems without a simplex or a cluster
• New lower bounds for the Turán density of \(PG_m(q)\)
• Constructions of non-principal families in extremal hypergraph theory
• Quadruple systems with independent neighborhoods
• Structure and stability of triangle-free set systems
• Simplex Stability
• Stability results for random discrete structures
• A hypergraph regularity method for generalized Turán problems
• Comparable pairs in families of sets
• A hypergraph Turán problem with no stability
• A new generalization of Mantel's theorem to \(k\)-graphs
• On the Codegree Density of $PG_m(q)$
• On Turán numbers for disconnected hypergraphs
• An exact Turán result for the generalized triangle
• The Turán problem for projective geometries
• 2-cancellative hypergraphs and codes
• An intersection theorem for four sets

   Recommendations

• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers 👍 👎
• An exact result for hypergraphs and upper bounds for the Turán density of \(K^r_{r+1}\) 👍 👎
• Turán densities of some hypergraphs related to \(K_{k+1}^{k}\) 👍 👎
• The Turán problem for hypergraphs on fixed size 👍 👎
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós 👍 👎

This page was built for publication: On a hypergraph Turán problem of Frankl

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368596)