Erdős problem 594 · problems.science

Erdős Problem 594 (Erdős–Hajnal [ErHa66], [Er69b]):

Sources

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

3 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

594.lean

Retained formal statement3 of 3

The earlier result of Erdős and Hajnal [ErHa66]: every graph with chromatic number $\geq \aleph_2$ contains all sufficiently large odd cycles.

Chromatic number $\geq \aleph_2$ is encoded as the nonexistence of a proper colouring with any set of at most $\aleph_1$ colours.

FormalConjectures/ErdosProblems/594.leanErdos594.erdos_594.variants.erdos_hajnal3 linesExact file

1∀ (V : Type) (G : SimpleGraph V),2  (∀ (α : Type), Cardinal.mk α ≤ Cardinal.aleph 1 → IsEmpty (G.Coloring α)) →3    ∃ N, ∀ (k : ℕ), N ≤ k → ∃ v w, w.IsCycle ∧ w.length = 2 * k + 1

SolvedStatement only, no proof

Sources

Search problems.science