Solving Turán's tetrahedron problem for the ℓ2\ell _2‐norm

DOI10.1112/JLMS.12568zbMATH Open1519.05131arXiv2108.10408OpenAlexW4220960689MaRDI QIDQ6133947FDOQ6133947

Bernard Lidický, Felix Christian Clemen, József Balogh

Publication date: 21 August 2023

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Abstract: Tur'an's famous tetrahedron problem is to compute the Tur'an density of the tetrahedron $K_4^3$. This is equivalent to determining the maximum $el{l}_1$-norm of the codegree vector of a $K_4^3$-free $n$-vertex $3$-uniform hypergraph. We introduce a new way for measuring extremality of hypergraphs and determine asymptotically the extremal function of the tetrahedron in our notion. The codegree squared sum, $ext{co}_2(G)$, of a $3$-uniform hypergraph $G$ is the sum of codegrees squared $d(x,y{)}^2$ over all pairs of vertices $xy$, or in other words, the square of the $el{l}_2$-norm of the codegree vector of the pairs of vertices. We define $ext{exco}_2(n,H)$ to be the maximum $ext{co}_2(G)$ over all $H$-free $n$-vertex $3$-uniform hypergraphs $G$. We use flag algebra computations to determine asymptotically the codegree squared extremal number for $K_4^3$ and $K_5^3$ and additionally prove stability results. In particular, we prove that the extremal $K_4^3$-free hypergraphs in $el{l}_2$-norm have approximately the same structure as one of the conjectured extremal hypergraphs for Tur'an's conjecture. Further, we prove several general properties about $ext{exco}_2(n,H)$ including the existence of a scaled limit, blow-up invariance and a supersaturation result.

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

Recommendations

• scientific article; zbMATH DE number 5942358
• scientific article; zbMATH DE number 736291
• On local Turán problems
• scientific article; zbMATH DE number 1439495
• The Turán problem for hypergraphs on fixed size

zbMATH Keywords

supersaturationblow-up invarianceextremality of hypergraphsscaled limit

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Cites Work

• CSDP, A C library for semidefinite programming
• On extremal problems of graphs and generalized graphs
• On 3-Hypergraphs with Forbidden 4-Vertex Configurations
• Hypergraphs Do Jump
• Title not available (Why is that?)
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Flag algebras
• Title not available (Why is that?)
• On the structure of linear graphs
• Generalizations of the removal lemma
• What we know and what we do not know about Turán numbers
• The codegree threshold of \(K_4^-\)
• Turán \(H\)-densities for 3-graphs
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• Rainbow triangles in three-colored graphs
• Embedding tetrahedra into quasirandom hypergraphs
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• Supersaturated graphs and hypergraphs
• A new generalization of the Erdős-Ko-Rado theorem
• Three-graphs without two triples whose symmetric difference is contained in a third
• Stability theorems for cancellative hypergraphs
• The Turán number of the Fano plane
• A new lower bound based on Gromov's method of selecting heavily covered points
• Triple Systems Not Containing a Fano Configuration
• An upper bound for the Turán number \(t_3(n,4)\)
• The Turán number of \(F_{3,3}\)
• Counting flags in triangle-free digraphs
• The co-degree density of the Fano plane
• Co-degree density of hypergraphs
• The Codegree Threshold for 3-Graphs with Independent Neighborhoods
• On the codegree density of complete 3-graphs and related problems
• Title not available (Why is that?)
• Monochromatic triangles in three-coloured graphs
• ${\ell}$-Degree Turán Density
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• On the number of 4-cycles in a tournament
• Minimum number of edges that occur in odd cycles
• A class of constructions for Turan's (3,4)-problem
• Title not available (Why is that?)
• Extremal Problems on the Hypercube and the Codegree Turán Density of Complete $r$-Graphs
• On the maximum quartet distance between phylogenetic trees
• More constructions for Turan's (3,4)-conjecture
• Systems of sets possessing the T-property
• Method for construction of (3,4)-graphs
• Strong forms of stability from flag algebra calculations
• Codegree Turán Density of Complete $r$-Uniform Hypergraphs
• WHAT IS... a Flag Algebra?
• Improving bounds on packing densities of 4-point permutations
• Title not available (Why is that?)
• Closing in on Hill's Conjecture
• The exact Turán number of \(F(3,3)\) and all extremal configurations

Cited In (2)

• Counting \(r\)-graphs without forbidden configurations
• Turán numbers and switching

This page was built for publication: Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm

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