Erdős problem 918 · problems.science

A question of Erdős and Hajnal [ErHa68b], who proved that for every finite $k$ there is a graph with chromatic number $\aleph_1$ and $\aleph_k$ vertices where each subgraph on less than $\aleph_k$ vertices has chromatic number $\leq \aleph_0$ .

Sources

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

9 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

918.lean

Retained formal statement2 of 9

Is there a graph with $\aleph_{\omega+1}$ vertices and chromatic number $\aleph_1$ such that every subgraph on $\aleph_\omega$ vertices has chromatic number $\leq\aleph_0$ ?

FormalConjectures/ErdosProblems/918.leanErdos918.erdos_918.parts.ii7 linesExact file

1True ↔2  ∀ (ω : Ordinal.{u}),3    ∃ V G,4      Cardinal.mk V = Cardinal.aleph (ω + 1) ∧5        G.chromaticCardinal = Cardinal.aleph 1 ∧6          ∀ (W : Set V),7            Cardinal.mk ↑W = Cardinal.aleph ω → (SimpleGraph.induce W G).chromaticCardinal ≤ Cardinal.aleph0

OpenStatement only, no proof

Sources

Search problems.science