Skip to content

Erdős problem 1175

Start work

Let κ\kappa be an uncountable cardinal. Must there exist a cardinal λ\lambda such that every graph with chromatic number λ\lambda contains a triangle-free subgraph with chromatic number κ\kappa?

Sources

The source's own material, retained exactly.

5 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1175.lean

Retained formal statement1 of 5

Let κ\kappa be an uncountable cardinal. Must there exist a cardinal λ\lambda such that every graph with chromatic number λ\lambda contains a triangle-free subgraph with chromatic number κ\kappa?

Shelah proved that a negative answer is consistent when κ=λ=ℵ1\kappa = \lambda = \aleph_1 (see erdos_1175.variants.shelah_consistency).

FormalConjectures/ErdosProblems/1175.leanErdos1175.erdos_11756 linesExact file
True ↔  ∀ (κ : Cardinal.{u_1}),    Cardinal.aleph0 < κ →      ∃ μ,        ∀ (V : Type u_1) (G : SimpleGraph V),          G.chromaticCardinal = μ → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ
OpenStatement only, no proof