Erdős problem 61 · problems.science

The Erdős–Hajnal Conjecture states that there is a constant $c(H) > 0$ for each $H$ such that we can take $f(n) = n^{c(H)}$ in the above formulation.

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

61.lean

Retained formal statement3 of 5

Chudnovsky, Scott, Seymour, and Spirkl [CSSS23] proved the conjecture for $H = C_5$ , the cycle on five vertices: every graph with no induced five-cycle has a clique or independent set of polynomial size.

[CSSS23] Chudnovsky, M., Scott, A., Seymour, P. and Spirkl, S., Erdős–Hajnal for graphs with no 5-hole. Proc. Lond. Math. Soc. (3) 126 (2023), 997–1014.

FormalConjectures/ErdosProblems/61.leanErdos61.erdos_61.variants.c51 lineExact file

1∃ c > 0, Erdos61.IsErdosHajnalLowerBound (SimpleGraph.cycleGraph 5) fun n => ↑n ^ c

SolvedStatement only, no proof

Sources

Search problems.science