Dense networks must contain every tree shape
- What it is
- The paper claims a dense-network rule forcing every large tree shape, alongside a result on multicolor tree patterns.
- Who did it
- Bruce Reed and Maya Stein
- What it could mean
- Add enough connections and a network loses the freedom to avoid certain branching patterns. This claimed threshold would turn ‘surely it must be there’ into a mathematical guarantee for large, dense networks.
See the check plan
Evidence & validation
From announcement to evidence
Discovery recorded. State of Proof has not yet examined this claim.
Read the original work
The Erdős-Sós conjecture in dense graphs ↗See the proposed checks
Source-lock the TeX bundle; independently reconstruct the dense decomposition and tree-embedding argument with all parameter dependencies; verify the threshold and sufficiently-large-(n) quantifiers; then separately trace the claimed reduction to the multicolor Ramsey consequence with specialist extremal-combinatorics review.
No proof docket yet
A docket is the public record of checks and open questions. This paper does not have one yet; the check plan above describes work still to do.
Explore existing proof dockets →
- What it claims
- The manuscript claims that for every (gamma), all sufficiently large (n)-vertex graphs with more than ((k-2)n/2) edges contain every (k)-vertex tree whenever (k≥gamma n). It also claims to solve a 51-year-old Erdős-Graham problem on multicolor Ramsey numbers of trees. This is a current, high-consequence partial-regime resolution of a landmark extremal-graph question.
- Why this could matter
- Dense networks must contain every tree shape A dense network cannot avoid a chosen branching pattern forever. This paper claims the exact edge threshold forces every large tree shape to appear, settling the dense regime of a major extremal-graph question.
- If it holds up
- It would give combinatorics a sharp dense-network embedding rule and resolve a long-standing multicolor Ramsey question about trees.
- If it does not
- The exact threshold or asymptotic range needs repair, preventing premature use as a universal dense-graph guarantee.
- Impact horizon
- Foundational · Graph theory · Combinatorics · Network structure
- Version
- submitted 2026-09-04 17:59:54 UTC
- Why we tracked it
- a fresh claimed resolution of the dense-regime Erdős-Sós conjecture, with a second named consequence, but no linked formalization, codebase, or certificate artifact; no docket created.
- Highest-risk dependency
- The load-bearing risk is quantifier and constant management across the asymptotic dense-regime embedding theorem. The abstract does not expose whether the decomposition, absorption, or regularity-type steps preserve the exact ((k-2)n/2) threshold and the stated (k≥gamma n) range.
- Available artifacts
- arXiv supplies PDF, experimental HTML, and TeX source. The primary abstract page lists no source-linked Lean, Coq, Isabelle, code repository, data, or certificate artifact. No manuscript artifact was downloaded or run.
- Current boundary
- Intake record only; examination not started.