Logo
All Random Solved Random Open
SOLVED
If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots $ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$.
Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density, and in [Er95d] he speculates the upper density (or even upper logarithmic density) must be $\geq 1/2$.

The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].