Erdős problem 593 · problems.science

Which finite triple systems occur in every triple system of uncountable chromatic number? The claimed characterization: exactly those that, after removing isolated vertices, are linear, have every hyperedge-node of their Levi graph meeting a bridge, and have every Berge cycle even.

Sources

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

12 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

593.lean

Retained formal statement10 of 10

Vertices must be uncountable: Every 3-uniform hypergraph with chromatic cardinal $> \aleph_0$ must have an uncountable vertex set.

Proof: If V is countable, there exists an injection φ : V → ℕ. Using distinct natural numbers as colors gives a proper coloring, so $\chi(H) \leq \#\mathbb{N} = \aleph_0$ , contradicting $\chi(H) > \aleph_0$ .

FormalConjectures/ErdosProblems/593.leanErdos593.erdos_593.variants.uncountable_vertices_if_large_chromatic1 lineExact file

1∀ {V : Type} (H : ThreeUniformHypergraph V), Cardinal.aleph0 < H.chromaticCardinal → ¬Countable V

TextbookStatement only, no proof

Sources

Search problems.science