Faster coloring and embedding in dense hypergraphs via stability
J Hou, X Liu, H Zhao - arXiv preprint arXiv:2401.17219, 2024 - arxiv.org
J Hou, X Liu, H Zhao
arXiv preprint arXiv:2401.17219, 2024•arxiv.orgThe classical Andr\'{a} sfai-Erd\H {o} sS\'{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} sS\'{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 …
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} sS\'{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 …
The classical Andr\'{a}sfai-Erd\H{o}s-S\'{o}s Theorem states that for , every -vertex -free graph with minimum degree greater than must be -partite. We establish a simple criterion for -graphs, , 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 -graph , we present a simple algorithm to decide the -freeness of an -vertex -graph with minimum degree greater than in time , where is a constant. In particular, for the complete graph , we can take . Based on a result by Chen-Huang-Kanj-Xia, we show that for every fixed , this problem cannot be solved in time if we replace with unless ETH fails. Furthermore, we establish an algorithm to decide the -freeness of an -vertex graph with edges in time for and , partially improving upon the recently provided running time of by Fomin--Golovach--Sagunov--Simonov. Moreover, we show that for every fixed , this problem cannot be solved in time if is of order unless ETH fails. As an intermediate step, we show that for a specific class of -graphs , the (surjective) -coloring problem can be solved in time , provided the input -graph has vertices and a large minimum degree, refining several previous results.
arxiv.org
Showing the best result for this search. See all results