A New Upper Bound for the Tur\'an Density of the Tetrahedron

Gyeongwon Jeong; Seonghun Park; Seonghyuk Im; Joonkyung Lee; and Hongseok Yang

Math & statisticsCombinatorics & discrete math

A New Upper Bound for the Tur\'an Density of the Tetrahedron

Gyeongwon Jeong, Seonghun Park, Seonghyuk Im, Joonkyung Lee, and Hongseok Yang

PreprintCode available

In the authors' words

We prove that the Tur\'an density of the tetrahedron $K_{4}^{(3)}$ satisfies $π (K_{4}^{(3)}) \leq 312372062889819/560000000000000 < 0.557808$ , improving Baber's upper bound of $0.5615$ and closing about $62$ of the gap to the conjectured value $5/9$ . The proof uses an exact seven-vertex flag-algebra certificate incorporating degree-stationarity from Razborov's differential method. To find the certificate, we combine the established techniques of cutting planes and column generation to optimize jointly over flag families whose types have at most five vertices. We give a complete formal proof of this Tur\'an density bound in Lean 4.

Main resultThe abstract does not state a limitation.

Read the paper PDF Code

Appeared: Thursday, September 24. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 28 pages, 5 figures, 8 tables. Lean 4 formalization, exact certificate and code: https://github.com/taeyool/tetrahedron-turan

A New Upper Bound for the Tur\'an Density of the Tetrahedron

In the authors' words

More on Combinatorics & discrete math that day

Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

A Szemer\'edi-Trotter Theorem in Arbitrary Fields

The Laplacian Sn,n​ conjecture is true

Smallest Cubic Non-1-Planar Graphs

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

The Laplacian $S_{n, n}$ conjecture is true