Induced subgraph density. I. A loglog step towards Erdos-Hajnal
Induced subgraph density. I. A loglog step towards Erdos-Hajnal
复制标题
诱导子图密度。
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
Matija Bucic;Tung H. Nguyen;A. Scott;P. Seymour
1977年，Erd\H{o}s和Hajnal做出猜想，对于每个图$H$，都存在$c>0$，使得每个无$H$的图$G$都有一个大小至少为$|G|^c$的派系或稳定集；他们用 $ |G|^c$ 替换为 $2^{c\sqrt{\log |G|}}$ 证明了这是正确的。到目前为止，这个结果还没有任何改善（对于一般$H$）。我们证明了一个强化：对于每个图 $H$，存在 $c>0$，使得每个 $H$-free 图 $G$ 与 $|G|\ge 2$ 都有一个大小至少为 $$2^{c\sqrt{\log |G|\log\log|G|}} 的集团或稳定集。$$ 事实上，我们证明了 Fox 和 Sudakov 定理的相应强化，这反过来又是定理的共同强化R\"odl、Nikiforov 以及上面提到的 Erd\H{o}s 和 Hajnal 定理。
In 1977, Erd\H{o}s and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $ |G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We prove a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of R\"odl, Nikiforov, and the theorem of Erd\H{o}s and Hajnal mentioned above.
影响因子：
1.1
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
通讯作者：
Spirkl, Sophie