Solving Turán's Tetrahedron Problem for the ℓ2-Norm

Date
2022-03-09
Authors
Balogh, József
Clemen, Felix Christian
Lidicky, Bernard
Lidicky, Bernard
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
Abstract
Turán's famous tetrahedron problem is to compute the Turán density of the tetrahedron K34. This is equivalent to determining the maximum ℓ1-norm of the codegree vector of a K34-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, co2(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 ℓ2-norm of the codegree vector of the pairs of vertices. We define exco2(n,H) to be the maximum co2(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 K34 and K35 and additionally prove stability results. In particular, we prove that the extremal K34-free hypergraphs in ℓ2-norm have approximately the same structure as one of the conjectured extremal hypergraphs for Turán's conjecture. Further, we prove several general properties about exco2(n,H) including the existence of a scaled limit, blow-up invariance and a supersaturation result.
Comments
This is a manuscript of an article published as Balogh, J., Clemen, F.C. and Lidický, B. (2022), Solving Turán's tetrahedron problem for the ℓ2 -norm. J. London Math. Soc.. https://doi.org/10.1112/jlms.12568. Posted with permission.
Description
Keywords
Citation
DOI
Collections