エルデシュ・ハイナル予想

既知の最良の結果

• すべてのグラフ $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}$ へと改良できるか。