Large Independent Sets from Local Considerations
Large Independent Sets from Local Considerations
复制标题
考虑局部因素的大型独立集
DOI：
10.1007/s00493-023-00023-w
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
M. Buci'c;B. Sudakov
以下自然问题是由90年代早期的Erdős -Hajnal和Linial -Rabinovich独立提出的。独立的尺寸R？由于海洋 - 拉比诺维奇，erdős -hajnal和alon – sudakov，我们证明，在每7个顶点中，任何n -vertex graph g具有$ \ alpha（g）的独立3个（n^{5/12}）$$α（g）≥Ω（n 5/12）。 $$ n^{1/3+\ varepsilon} $$ n 1 / 3 +ε并将指数的最佳值为1/2。 2密度（图H的2密度定义为$$ m_2（h）：= \ max _ {h'\ subseteq h，| h'| \ ge 3} \ frac {e（h'） -1} {| h'| -2} $$ m 2（h）：= max h'⊆ H |。 Krivelevich和Kostochka-Jancey。未来的研究。
The following natural problem was raised independently by Erdős–Hajnal and Linial–Rabinovich in the early ’90 s. How large must the independence number $$\alpha (G)$$ α ( 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 the 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 $$\alpha (G) \ge \Omega (n^{5/12})$$ α ( G ) ≥ Ω ( n 5 / 12 ) . This confirms a conjecture of Erdős and Hajnal that $$\alpha (G)$$ α ( G ) should be at least $$n^{1/3+\varepsilon }$$ n 1 / 3 + ε and brings the exponent halfway 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 (The 2- density of a graph H is defined as $$m_2(H):=\max _{H' \subseteq H, |H'| \ge 3} \frac{e(H')-1}{|H'|-2}$$ m 2 ( H ) : = max H ′ ⊆ H , | H ′ | ≥ 3 e ( H ′ ) - 1 | H ′ | - 2 ) 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.