埃尔德什–哈伊纳尔猜想

已知最佳结果

• 对任意图 $H$，每个不含诱导 $H$ 的 $n$ 顶点图都含有规模至少为 $2^{c_H \sqrt{\log n \log\log n}}$ 的团或独立集（布契奇、阮松、斯科特与西摩，2023）。
• 完整的多项式猜想对所有满足 $|V(H)| \le 5$ 的图 $H$（由丘德诺夫斯基–斯科特–西摩–施皮尔克尔2021年解决 $C_5$ 以及阮松–斯科特–西摩2023年解决 $P_5$ 而收官）及由其经顶点替换生成的全部图均成立。

使用的方法及其局限

尚未解决的问题

• 埃尔德什–哈伊纳尔猜想对不含诱导 $P_6$ 的图和不含诱导 $C_6$ 的图是否成立？
• 能否将任意 $H$ 的一般下界从 $2^{c_H \sqrt{\log n \log\log n}}$ 提升至某个 $\alpha > 1/2$ 对应的 $2^{c_H (\log n)^\alpha}$？