Skip to content

Erdős problem 596

Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G1,G2)(G_1, G_2) is it true that

Sources

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

9 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

596.lean

Retained formal statement1 of 9

Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G1,G2)(G_1, G_2) is it true that

(1) for every n1n \geq 1 there is a graph HH without a G1G_1 such that any nn-colouring of HH's edges contains a monochromatic G2G_2, and yet (2) for every graph HH without a G1G_1 there is an 0\aleph_0-colouring of HH's edges with no monochromatic G2G_2?

Erdős and Hajnal originally conjectured that no such pair exists; but (C4,C6)(C_4, C_6) witnesses it (Nešetřil–Rödl + Erdős–Hajnal). The full question is to characterise the class of all such pairs, recorded here as answer(sorry).

See Problem 595 for the specific case (G1,G2)=(K4,K3)(G_1, G_2) = (K_4, K_3).

FormalConjectures/ErdosProblems/596.leanErdos596.erdos_5962 linesExact file
∀ {UU₂ : Type} (G₁ : SimpleGraph U₁) (G₂ : SimpleGraph U₂),  G₁.IsErdosHajnalExceptional G₂ ↔ (fun {UU₂} => sorry) GG
OpenStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page