Erdős Problem 596
Erdős Problem 596* (Erdős–Hajnal, [Er87]). For which graph pairs is it true that
Mathematical statement
Erdős Problem 596* (Erdős–Hajnal, [Er87]). For which graph pairs is it true that
(1) for every there is a graph without a such that any -colouring of 's edges contains a monochromatic , and yet (2) for every graph without a there is an -colouring of 's edges with no monochromatic ?
Erdős and Hajnal originally conjectured that no such pair exists; but
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 .
Statement source: Erdős Problems statement material
Statement terms: Source-specific
Source-specific terms. Therefore does not assert reuse rights beyond attributed display.
Statement artifacts, not proofs
These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.
Pinned Lean formulation 1
erdos_596
theorem erdos_596 : ∀ {U₁ U₂ : Type} (G₁ : SimpleGraph U₁) (G₂ : SimpleGraph U₂), IsErdosHajnalExceptional G₁ G₂ ↔ (answer(sorry) : ∀ {U₁ U₂ : Type}, SimpleGraph U₁ → SimpleGraph U₂ → Prop) G₁ G₂ := by sorry- Statement source
- Formal Conjectures
- Lean version
- v4.27.0
- Placeholder
- Present; no proof artifact
- Source evidence
- Pinned source index
- Fidelity review
- Community formulation
References