Positive codegree Andrásfai--Erdős--Sós theorem for the generalized triangle

Abstract

The celebrated Andrásfai--Erdős--Sós Theorem from 1974 shows that every $n$-vertex triangle-free graph with minimum degree greater than $2n/5$ must be bipartite. We establish a positive codegree extension of this result for the $r$-uniform generalized triangle ${\mathrm{T}}_r=\left\{\{1,\dots ,r-1,r\},\{1,\dots ,r-1,r+1\},\{r,r+1,\dots ,2r-1\}\right\}$$:$ For every $n\ge (r-1)(2r+1)/2$, if $\mathcal{H}$ is an $n$-vertex ${\mathrm{T}}_r$-free $r$-uniform hypergraph in which each $(r-1)$-tuple of vertices is contained in either zero edges or more than $2n/(2r+1)$ edges of $\mathcal{H}$, then $\mathcal{H}$ is $r$-partite. This result provides the first tight positive codegree Andr{á}sfai--Erdős--Sós type theorem for hypergraphs. It also immediately implies that the positive codegree Turán number of ${\mathrm{T}}_r$ is $\lfloor n/r\rfloor$ for all $r$. Additionally, for $r=3$, our result answers one of the questions posed by Hou et al.~\cite{HLYZZ22} in a strong form.

extended Theorem 1.2 to all r, added consequence in positive codegree Turan problems, updated reference