Skip to content

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

The source's own material, retained exactly.

12 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

593.lean

Retained formal statement3 of 10

Graph analogue — bipartite graphs are obligatory (Erdős–Galvin–Hajnal [EGH75]): For the 2-uniform (graph) case, a graph of chromatic cardinal >ℵ0> \aleph_0 must contain all finite bipartite graphs. Specifically, for every finite bipartite graph F and every graph G with chromatic cardinal >ℵ0> \aleph_0, 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.

FormalConjectures/ErdosProblems/593.leanErdos593.erdos_593.variants.graph_case_bipartite_obligatory4 linesExact file
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