The codegree threshold of K4−$K_4^{-}$
Authors:
Open Access
- 16 February 2023
- journal article
- research article
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 107 (5) , 1660-1691
Abstract
The codegree threshold of a 3‐graph is the minimum such that every 3‐graph on vertices in which every pair of vertices is contained in at least edges contains a copy of as a subgraph. We study when , the 3‐graph on 4 vertices with 3 edges. Using flag algebra techniques, we prove that if is sufficiently large, then This settles in the affirmative a conjecture of Nagle [Congressus Numerantium, 1999, pp. 119–128]. In addition, we obtain a stability result: for every near‐extremal configuration , there is a quasirandom tournament on the same vertex set such that is ‐close in the edit distance to the 3‐graph whose edges are the cyclically oriented triangles from . For infinitely many values of , we are further able to determine exactly and to show that tournament‐based constructions are extremal for those values of .Keywords
Funding Information
- Vetenskapsrådet (VR 2016‐03488, VR 2021‐03687)
- Leverhulme Trust (RPG‐2018‐424)
- European Research Council (101020255)
This publication has 27 references indexed in Scilit:
- Hypergraph Turán problems2011
- Generalizations of the removal lemmaCombinatorica, 2009
- A hypergraph regularity method for generalized Turán problemsRandom Structures & Algorithms, 2008
- Codegree problems for projective geometriesJournal of Combinatorial Theory, Series B, 2007
- Co-degree density of hypergraphsJournal of Combinatorial Theory, Series A, 2007
- Oriented hamilton cycles in digraphsJournal of Graph Theory, 1995
- Quasi‐random tournamentsJournal of Graph Theory, 1991
- An exact result for 3-graphsDiscrete Mathematics, 1984
- Doubly regular tournaments are equivalent to skew hadamard matricesJournal of Combinatorial Theory, Series A, 1972
- Some (1, −1) matricesJournal of Combinatorial Theory, Series B, 1971