Skip to content

Erdős problem 750

Let f(m)f(m) be some function such that f(m)→∞f(m)\to \infty as m→∞m\to \infty. Does there exist a graph GG of infinite chromatic number such that every subgraph on mm vertices contains an independent set of size at least m2−f(m)\frac{m}{2}-f(m)?

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/750.lean

Formal Conjectures

FormalConjectures/ErdosProblems/750.leanErdos750.erdos_7506 linesExact file
True ↔  ∀ (f : ℕ → NNReal),    Filter.Tendsto f Filter.atTop Filter.atTop →      ∃ V G,        G.chromaticNumber = ⊤ ∧          ∀ (m : ℕ) (S : Set V), 0 < m → S.ncard = m → ∃ I ⊆ S, G.IsIndepSet I ∧ ↑m / 2 - f m ≤ ↑I.ncard
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Proof manifests naming this Problem

  • Jayyhk Erdős Leanjayyhk:erdos:750

Reported activity

Work these sources record against this Problem. Source-reported attribution, not reviewed here.

  • AI collaborating with humans

    Erdős AI contributions wiki · 3 May, 2026

    Machine
    GPT-5.5 Pro
    People
    Przemek Chojecki
    Open the source record

  • Formalization

    Erdős AI contributions wiki · 4 May, 2026

    Machine
    Claude Code, Claude Opus 4.7, GPT-5.5 Pro
    Open the source record

  • argument

    VibeMathed

    Machine
    GPT-5.5 Pro
    People
    Przemek Chojecki
    Reported outcome
    resolved
    Open the source record

Continue

Start a contributionBrowse the source filesOpen the collection entry

Search problems.science

Find a Problem, Result, source, or page