Faster coloring and embedding in dense hypergraphs via stability

The classical Andr\'{a}sfai-Erd\H{o}s-S\'{o}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 \geq 2$, to exhibit an Andr\'{a}sfai-Erd\H{o}s-S\'{o}s-type property (AES), leading to a classification of most previously studied hypergraph families with this property. For every AES $r$-graph $F$, we present a simple algorithm to decide the $F$-freeness of an $n$-vertex $r$-graph with minimum degree greater than $(\pi(F) - \varepsilon_F)\binom{n}{r-1}$ in time $O(n^r)$, where $\varepsilon_F >0$ is a constant. In particular, for the complete graph $K_{\ell+1}$, we can take $\varepsilon_{K_{\ell+1}} = (3\ell^2-\ell)^{-1}$. Based on a result by Chen-Huang-Kanj-Xia, we show that for every fixed $C > 0$, this problem cannot be solved in time $n^{o(\ell)}$ if we replace $\varepsilon_{K_{\ell+1}}$ with $(C\ell)^{-1}$ unless ETH fails. Furthermore, we establish an algorithm to decide the $K_{\ell+1}$-freeness of an $n$-vertex graph with $\mathrm{ex}(n,K_{\ell+1})-k$ edges in time $(\ell+1)n^2$ for $k \le n/30\ell$ and $\ell \le \sqrt{n/6}$, partially improving upon the recently provided running time of $2.49^k n^{O(1)}$ by Fomin--Golovach--Sagunov--Simonov. Moreover, we show that for every fixed $\delta > 0$, this problem cannot be solved in time $n^{o(\ell)}$ if $k$ is of order $n^{1+\delta}$ unless ETH fails. 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.