OPENNOTORIOUSgraph theorychromatic numberset theory
Is there a graph of chromatic number $\aleph_1$ with $\aleph_1$ vertices such that for all $\epsilon>0$, if $n$ is sufficiently large, every subgraph on $n$ vertices contains an independent set of size $>n^{1-\epsilon}$?
Notes: Conjectured by Erdos, Hajnal, and Szemeredi. Erdos offered generous rewards for any significant partial results.
AI Status: NONE · 0 total attempts