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 statement2 of 3

In [ErHa67b] Erdős and Hajnal prove this for $f(m)\geq cm$ for all $c>1/4$ .

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

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

SolvedStatement only, no proof

Sources

Search problems.science