Erdős Problem 75
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
Mathematical statement
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all
ε > 0, if n is sufficiently large and H is a subgraph on n vertices,
then H contains an independent set of size > n ^ (1 - ε)?
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_75
theorem erdos_75 : answer(sorry) ↔ ∃ (V : Type) (G : SimpleGraph V), G.chromaticCardinal = ℵ_ 1 ∧ #V = ℵ_ 1 ∧ ∀ ε > (0 : ℝ), ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (H : G.Subgraph), H.verts.ncard = n → ∃ (I : Finset V), (I : Set V) ⊆ H.verts ∧ G.IsIndepSet (I : Set V) ∧ (I.card : ℝ) > (n : ℝ) ^ (1 - ε) := 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