Department of
Applied
Mathematics

The codegree threshold of K4-

Jan Volec

Abstract

(joint work with Victor Falgas-Ravry, Oleg Pighurko and Emil Vaughan)

The codegree threshold ex_2(n,F) of a 3-graph F is the minimum d such that every 3-graph on n vertices in which every pair of vertices is contained in at least d+1 edges contains a copy of $F$ as a subgraph. In this talk, we focus on the codegree threshold of F=K4-, the 3-graph on 4 vertices with 3 edges.

Using flag algebra techniques, we prove that ex_2(n, K4-)=n/4+O(1). This settles in the affirmative a conjecture of Nagle from 1999. In addition, we show that for every near-extremal 3-graph G, there is a quasirandom tournament T on the same vertex set such that G is close in the edit distance to the 3-graph C(T) whose edges are the cyclically oriented triangles of T. Using that, we determine the exact value of ex_2(n,K4-) for infinitely many values of n by a close relation to the existence of skew Hadamard matrices. In fact, determining the exact value of ex_2(n, K4-) for n=4k+3 is equivalent to Seberry's conjecture, which states there is a skew Hadamard matrix for any n=4k.