Erdős problem 750 · problems.science

Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$ . Does there exist a graph $G$ of infinite chromatic number such that every subgraph on $m$ vertices contains an independent set of size at least $\frac{m}{2}-f(m)$ ?

Sources

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

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

750.lean

Retained formal statement3 of 3

In [Er69b] Erdős conjectures this for $f(m)=\epsilon m$ for any fixed $\epsilon>0$ . This follows from a result of Erdős, Hajnal, and Szemerédi [EHS82], as described by Sellke in the comments.

FormalConjectures/ErdosProblems/750.leanErdos750.erdos_750.variants.epsilon5 linesExact file

1True ↔2  ∀ ε > 0,3    ∃ V G,4      G.chromaticNumber = ⊤ ∧5        ∀ (m : ℕ) (S : Set V), 0 < m → S.ncard = m → ∃ I ⊆ S, G.IsIndepSet I ∧ ↑m / 2 - ε * ↑m ≤ ↑I.ncard

SolvedStatement only, no proof

Sources

Search problems.science