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 statement6 of 9

In [ErHa69] the questions are stated with $= \aleph_0$ rather than $\leq\aleph_0$ . This is a likely typo since it can be shown that no such graph exists in this case.

This is the second question with all subgraphs.

FormalConjectures/ErdosProblems/918.leanErdos918.erdos_918.variants.eq_aleph_0_all_subgraphs.parts.ii5 linesExact file

1∀ (ω : Ordinal.{u}),2  ¬∃ V G,3      Cardinal.mk V = Cardinal.aleph (ω + 1) ∧4        G.chromaticCardinal = Cardinal.aleph 1 ∧5          ∀ (H : G.Subgraph), Cardinal.mk ↑H.verts = Cardinal.aleph ω → H.coe.chromaticCardinal = Cardinal.aleph0

TextbookStatement only, no proof

Sources

Search problems.science