OPENNOTORIOUSgraph theoryRamsey theory
For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices not containing $H$ as an induced subgraph contains a complete graph or independent set on $\geq n^c$ vertices?
Notes: Erdos and Hajnal proved existence of a clique or independent set on >= exp(c_H * sqrt(log n)) vertices. Bucic, Nguyen, Scott, and Seymour improved to exp(c_H * sqrt(log n * log log n)).
AI Status: NONE · 0 total attempts