论文标题
朝着$ p_5 $ - free Graphs的Erdős-Hajnal猜想
Towards the Erdős-Hajnal conjecture for $P_5$-free graphs
论文作者
论文摘要
Erdős-Hajnal的猜想是可以追溯到1977年的极端和结构组合学中最古典和最著名的问题之一。它断言，与一般的$ n $ vertex相比，如果一个人在图表上施加了一些较小的结构，即使在固定的图形上，它是固定的，而不是仅仅是固定图形$ h，而不是诱导的量子，而不是诱导的siplirial，则是诱导的siplirial，而不是诱导的一定尺寸。或独立集可以找到多项式大小之一。尽管多年来一直是人们关注的重点，但猜想仍然开放。在本文中，我们在这个问题上改善了$ 2^{ω（\ sqrt {\ log n}）} $的最著名的下限，这是由于1989年的ErdőS和Hajnal，在最小的开放式案例中，即当一个人禁止$ P_5 $时，这是$ 5 $ fertices的路径。也就是说，我们表明任何$ p_5 $ -free $ n $ pertex图都包含一个集团或独立大小的集合至少$ 2^{ω（\ log n）^{2/3}} $。我们的方法还导致无限图系列的改进。
The Erdős-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to the case of a general $n$-vertex graph if one imposes even a little bit of structure on the graph, namely by forbidding a fixed graph $H$ as an induced subgraph, instead of only being able to find a polylogarithmic size clique or an independent set one can find one of polynomial size. Despite being the focus of considerable attention over the years the conjecture remains open. In this paper we improve the best known lower bound of $2^{Ω(\sqrt{\log n})}$ on this question, due to Erdős and Hajnal from 1989, in the smallest open case, namely when one forbids a $P_5$, the path on $5$ vertices. Namely, we show that any $P_5$-free $n$ vertex graph contains a clique or an independent set of size at least $2^{Ω(\log n)^{2/3}}$. Our methods also lead to the same improvement for an infinite family of graphs.
