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

Erdős Problem 593 (500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number $> \aleph_0$ .

A natural conjectural characterization, recorded here, is that the obligatory finite 3-uniform hypergraphs are exactly the 2-colorable ones (Property B). The forward direction (IsObligatory → IsTwoColorable) and converse (IsTwoColorable → IsObligatory) are stated as separate variants below; in the graph case ( $r = 2$ ), Erdős–Galvin–Hajnal [EGH75] proved the analogous result (obligatory ⇔ bipartite).

FormalConjectures/ErdosProblems/593.leanErdos593.erdos_5931 lineExact file

1True ↔ ∀ (W : Type) [inst : Fintype W] (F : ThreeUniformHypergraph W), IsObligatory F ↔ F.IsTwoColorable

OpenStatement only, no proof

Sources

Search problems.science