Erdős problem 593
Erdos Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system. The answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations. Problem #1177 on exact spectra is settled alongside it.
Sources
FormalConjectures/ErdosProblems/
593.lean
Retained formal statement
Graph analogue — bipartite graphs are obligatory (Erdős–Galvin–Hajnal [EGH75]): For the 2-uniform (graph) case, a graph of chromatic cardinal must contain all finite bipartite graphs. Specifically, for every finite bipartite graph F and every graph G with chromatic cardinal , there is a graph embedding from F into G.
This uses Nonempty (F ↪g G) (graph embedding), aligned with the injective vertex map used in the hypergraph Appears definition.
True ↔ ∀ (V : Type u_1) (G : SimpleGraph V), Cardinal.aleph0 < G.chromaticCardinal → ∀ (W : Type u_2) [Fintype W] (F : SimpleGraph W), F.IsBipartite → Nonempty (F ↪g G)SolvedStatement only, no proof