A criterion for Andrásfai--Erdős--Sós type theorems and applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916253503848448 |
|---|---|
| author | Hou, Jianfeng Liu, Xizhi Zhao, Hongbin |
| author_facet | Hou, Jianfeng Liu, Xizhi Zhao, Hongbin |
| contents | 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 \geq 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 $(π(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}$, 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 $\varepsilon_{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17219 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A criterion for Andrásfai--Erdős--Sós type theorems and applications Hou, Jianfeng Liu, Xizhi Zhao, Hongbin Combinatorics Computational Complexity 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 \geq 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 $(π(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}$, 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 $\varepsilon_{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. |
| title | A criterion for Andrásfai--Erdős--Sós type theorems and applications |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2401.17219 |