On Turan's (3,4)-problem with forbidden configurations

2012/10/17 by Alexander Razborov, Razborov, Alexander
Engineering · Mathematics · #05D99 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1210.4605

openalex publication_date 2012/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We identify three 3-graphs on five vertices each missing in all known extremal configurations for Turan's (3,4)-problem and prove Turan's conjecture for 3-graphs that are additionally known not to contain any induced copies of these 3-graphs. Our argument is based on an (apparently) new technique of "indirect interpretation" that allows us to retrieve additional structure from hypothetical counterexamples to Turan's conjecture, but in rather loose and limited sense. We also include two miscellaneous calculations in flag algebras that prove similar results about some other additional forbidden subgraphs.

Related

• New Tur'an densities for 3-graphs
• More Constructions for Turán's (3, 4)-Conjecture
• The Turán Number of the Triangular Pyramid of 3-Layers
• On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's\n (3,4)-problem
• The generalized Turán number for K₃ in graphs without suspensions of a path on five vertices