A criterion for Andrásfai--Erdős--Sós type theorems and applications

Abstract

The classical Andrásfai--Erdős--Sós Theorem states that for $\ell \ge 2$, every $n$-vertex $K_{\ell +1}$-free graph with minimum degree greater than $\frac{3\ell -4}{3\ell -1}n$ must be $\ell$-partite. We establish a simple criterion for $r$-graphs, $r\ge 2$, to exhibit an Andrásfai--Erdős--Sós type property, also known as degree-stability. This leads to a classification of most previously studied hypergraph families with this property. An immediate application of this result, combined with a general theorem by Keevash--Lenz--Mubayi, solves the spectral Turán problems for a large class of hypergraphs. For every $r$-graph $F$ with degree-stability, there is a simple algorithm to decide the $F$-freeness of an $n$-vertex $r$-graph with minimum degree greater than $(\pi (F)-{\epsilon }_F)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ in time $O(n^r)$, where ${\epsilon }_F>0$ is a constant. In particular, for the complete graph $K_{\ell +1}$, we can take ${\epsilon }_{K_{\ell +1}}=(3{\ell }^2-\ell {)}^{-1}$, and this bound is tight up to some multiplicative constant factor unless $\mathbf{W}[1]=\mathbf{FPT}$. Based on a result by Chen--Huang--Kanj--Xia, we further show that for every fixed $C>0$, this problem cannot be solved in time $n^{o(\ell )}$ if we replace ${\epsilon }_{K_{\ell +1}}$ with $(C\ell {)}^{-1}$ unless $\mathbf{ETH}$ fails. Furthermore, we apply the degree-stability of $K_{\ell +1}$ to decide the $K_{\ell +1}$-freeness of graphs whose size is close to the Turán bound in time $(\ell +1)n^2$, partially improving a recent result by Fomin--Golovach--Sagunov--Simonov. As an intermediate step, we show that for a specific class of $r$-graphs $F$, the (surjective) $F$-coloring problem can be solved in time $O(n^r)$, provided the input $r$-graph has $n$ vertices and a large minimum degree, refining several previous results.

arXiv commentfixed some typos, changed the title, reorganized to enhance readability for combinatorial readers, comments are welcome