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 statement4 of 10

Graph analogue — no odd cycle is obligatory (Erdős–Galvin–Hajnal [EGH75]): For every odd $k \geq 3$ , there exists a graph with chromatic cardinal $\aleph_1$ that contains no cycle of length $k$ . This shows the class of obligatory graphs is strictly smaller than all finite graphs.

FormalConjectures/ErdosProblems/593.leanErdos593.erdos_593.variants.graph_case_no_odd_cycle2 linesExact file

1True ↔2  ∀ (k : ℕ), Odd k → 3 ≤ k → ∃ V G, G.chromaticCardinal = Cardinal.aleph 1 ∧ IsEmpty (SimpleGraph.cycleGraph k →g G)

SolvedStatement only, no proof

Sources

Search problems.science