Breakthrough Tracker record

Dense-graph Erdős–Sós progress also resolves an Erdős–Graham Ramsey problem

Bruce Reed and Maya Stein prove the Erdős–Sós conjecture for sufficiently large host graphs when the tree size is at least a fixed positive fraction of the host size. As a corollary, they report a solution to a 51-year-old Erdős–Graham problem on multicolor Ramsey numbers of trees.

← Back to the filtered Breakthrough Tracker

Stable ID: math-erdos-sos-dense-graphs-erdos-graham-2026
Revision: math-erdos-sos-dense-graphs-erdos-graham-2026.v1
Field: Mathematics · Extremal graph theory and Ramsey theory
Evidence: Tier 1 · Peer reviewed: No
Record state: Provisional · Provisional dense-regime theorem
Last checked: 2026-09-07

AI role

No substantive AI role was disclosed in the inspected manuscripts.

Record details

Problem or result: Dense-regime Erdős–Sós theorem and a 51-year-old Erdős–Graham tree-Ramsey problem
Authors: Bruce Reed and Maya Stein
Institutions: Academia Sinica; Universidad de Chile and Centro de Modelamiento Matemático
Result date: Companion preprints submitted September 4, 2026

Why it matters

Erdős–Sós is a central tree-embedding conjecture from the 1960s. The exact dense-regime theorem removes maximum-degree restrictions and yields a separate long-open Ramsey-theory consequence.

Limits

This does not prove the full Erdős–Sós conjecture: it assumes sufficiently large n and k at least a fixed positive fraction of n. Both papers are first-version preprints without located peer review.

Sources

Primary: Reed and Stein, the Erdős–Sós conjecture in dense graphs
Companion: Reed and Stein, extremal cases of the Erdős–Sós conjecture

Correction and revision history

2026-09-07 — Added after primary-source, scope, status, AI-role and limitation review.

Machine-readable: JSON v1 · CSV v1 · Schema v1

This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.