Erdős problem 1175 · problems.science

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

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1175.lean

Retained formal statement3 of 5

The threshold variant threshold_formulation is stronger than the exact-equality form erdos_1175: if every graph with chromaticCardinal ≥ μ has the desired triangle-free subgraph, then in particular every graph with chromaticCardinal = μ does too.

FormalConjectures/ErdosProblems/1175.leanErdos1175.erdos_1175.test.threshold_implies_exact10 linesExact file

1(∀ (κ : Cardinal.{0}),2    Cardinal.aleph0 < κ →3      ∃ μ,4        ∀ (V : Type) (G : SimpleGraph V),5          μ ≤ G.chromaticCardinal → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ) →6  ∀ (κ : Cardinal.{0}),7    Cardinal.aleph0 < κ →8      ∃ μ,9        ∀ (V : Type) (G : SimpleGraph V),10          G.chromaticCardinal = μ → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ

TestStatement only, no proof

Sources

Search problems.science