A New Upper Bound for the Turán Density of the Tetrahedron

Abstract

We prove that the Turán density of the tetrahedron $K_4^{(3)}$ satisfies $\pi (K_4^{(3)})\le 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án density bound in Lean 4.

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