Erdős Problem #601
Erdős Problem 601 (500 prize). For which limit ordinals α does HasPathOrIndepSetOfType α hold?
Current state (tracked automatically)
- erdosproblems.com lists Erdős problem #601 as open (status updated 31 August 2025).
All tracked facts and sources
| Fact | Value | Source |
|---|---|---|
| Status of Erdős problem #601 on erdosproblems.com | open 2025-08-31 | erdosproblems.com |
| Formal Conjectures: research statements in the file | 3 open, 2 solved | Formal 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.
Cite
@misc{cairn-erdos-601,
title = {Erdős Problem #601},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/erdos-601}},
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):
[](https://cairn-commons.com/problems/erdos-601)
- 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.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- 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.
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
erdos_601. Erdős Problem 601 ($500 prize).
For which limit ordinals does HasPathOrIndepSetOfType α hold?
omega_1_omega_plus_2. Erdős–Hajnal–Milner conjecture at [Er81, Section VII]: every graph on contains an infinite path or an independent set of that order type. Erdős conjectured the positive answer. This is the first limit ordinal not covered by the Erdős–Hajnal–Milner theorem.
Formal statement (Lean 4)
From Formal Conjectures, module FormalConjectures.ErdosProblems.«601» (2 statements).
theorem erdos_601 :
∀ α : Ordinal.{0}, Order.IsSuccLimit α →
(HasPathOrIndepSetOfType α ↔
erdos_601.answer α)theorem omega_1_omega_plus_2 :
HasPathOrIndepSetOfType (ω_ 1 ^ (ω + 2))What counts as progress
- A Lean proof of one of the statements above, pinned as the claim's formal statement.
- 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/601. Report it as a literature claim.
- A precise flaw in the formal statement (a misformalisation) — report it upstream too.
Variants
erdos_601.variants.universal— Erdős–Hajnal–Milner conjecture [Er81, Section VII]: every graph on a limit ordinal α contains an infinite path or an independent set of order type α.
References
References:
- [EHM70] Erdős, P.; Hajnal, A.; Milner, E.C. Set mappings and polarized partition relations. Combinatorial theory and its applications, I–III (Balatonfüred, 1969) (1970), 327–363.
- [Er81] Erdős, P. On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25–42, Section VII.
- [La90] Larson, J.A. *Martin's Axiom and ordinal graphs: large independent sets or infinite paths.* Ann. Pure Appl. Logic 47 (1990), 31–39.
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.