论文标题
本地考虑的大型独立集
Large independent sets from local considerations
论文作者
论文摘要
80年代后期，Erdős-Hajnal和Linial-Rabinovich独立提出了以下自然问题。图$ g $的独立数字$α（g）$必须大于其每个$ m $ $顶点都包含一套独立的尺寸$ r $？在本文中，我们讨论了攻击此问题的新方法。第一种基于界限的拉姆齐数字的新方法使我们能够改善由于海洋 - rabinovich，erdős-hajnal和alon-sudakov而引起的先前最佳下限。例如，我们证明，在每$ 7 $ vertices中，任何$ n $ vertex Graph $ g $都具有独立尺寸$ 3 $的独立集，其中$α（g）\geΩ（n^{5/12}）$。这证实了Erdős和hajnal的猜想，即$α（g）$应至少为$ n^{1/3+\ varepsilon} $，并将指数中途带到最佳的$ 1/2 $。我们的第二种方法涉及上限。它依赖于将原始问题减少到以下自然极端问题。在$ m $ $ r $的$ m $顶点上，$ 2 $密度的最小值的最小值是多少？这使我们能够由于海洋 - 拉比诺维奇，克里维尔维奇和科斯托卡·贾西而改善以前的上限。作为我们论点的一部分，我们将Erdős-Hajnal和Linial-Rabinovich的问题以及我们的新极值$ 2 $密度问题与许多其他认真的问题联系起来。这为未来的研究提供了许多有趣的方向。
The following natural problem was raised independently by Erdős-Hajnal and Linial-Rabinovich in the late 80's. How large must the independence number $α(G)$ of a graph $G$ be whose every $m$ vertices contain an independent set of size $r$? In this paper we discuss new methods to attack this problem. The first new approach, based on bounding Ramsey numbers of certain graphs, allows us to improve previously best lower bounds due to Linial-Rabinovich, Erdős-Hajnal and Alon-Sudakov. As an example, we prove that any $n$-vertex graph $G$ having an independent set of size $3$ among every $7$ vertices has $α(G) \ge Ω(n^{5/12})$. This confirms a conjecture of Erdős and Hajnal that $α(G)$ should be at least $n^{1/3+\varepsilon}$ and brings the exponent half-way to the best possible value of $1/2$. Our second approach deals with upper bounds. It relies on a reduction of the original question to the following natural extremal problem. What is the minimum possible value of the $2$-density of a graph on $m$ vertices having no independent set of size $r$? This allows us to improve previous upper bounds due to Linial-Rabinovich, Krivelevich and Kostochka-Jancey. As part of our arguments we link the problem of Erdős-Hajnal and Linial-Rabinovich and our new extremal $2$-density problem to a number of other well-studied questions. This leads to many interesting directions for future research.
