Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Graph theory P-erdos-566

Erdős Problem #566

Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?

Status (as of 2026-11-11): Open according to erdosproblems.com (status last updated 2025-08-31).

Current state (tracked automatically)

  • erdosproblems.com lists Erdős problem #566 as open (status updated 31 August 2025).
  • Formal Conjectures marks the Lean statement erdos_566 as open.
All tracked facts and sources
FactValueSource
Status of Erdős problem #566 on erdosproblems.comopen
2025-08-31
erdosproblems.com
Formal Conjectures: status of `erdos_566`research openFormal Conjectures
Formal Conjectures: research statements in the file1 open, 0 solvedFormal Conjectures

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): erdosproblems.com (checked 2026-11-12), Formal Conjectures (checked 2026-11-12). How it works.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Try it with your chatbot Submit a claim Follow (RSS)
Cite 
@misc{cairn-erdos-566,
  title        = {Erdős Problem #566},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-566}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Ferdos-566.json)](https://cairn-commons.com/problems/erdos-566)
Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

  1. Get a task — one click
  2. Your chatbot works on it — 5–10 minutes, in its own tab
  3. Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

Let be such that any subgraph on vertices has at most edges. Is it true that, if has edges and no isolated vertices, then ?

In other words: if is sparse (every induced subgraph on vertices has edges), is Ramsey size linear?

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«566».

theorem erdos_566 :
    ∀ (p : ℕ) (G : SimpleGraph (Fin p)),
      (∀ S : Finset (Fin p), 2 ≤ S.card → (G.induce S).edgeSet.ncard ≤ 2 * S.card - 3) →
      G.IsRamseySizeLinear

What counts as progress

  • A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already — check erdosproblems.com/566. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

:

Combin. Probab. Comput. (1993), 389-399.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.