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 statement5 of 5

Nguyen, Scott, and Seymour [NSS23] proved the conjecture for $H = P_5$ , the path on five vertices: every $P_5$ -free graph on $n$ vertices has a clique or independent set of polynomial size.

[NSS23] Nguyen, T., Scott, A. and Seymour, P., Induced subgraph density. VII. The five-vertex path. [arXiv:2312.15333](https://arxiv.org/abs/2312.15333)

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

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

SolvedStatement only, no proof

Sources

Search problems.science