Erdős-Sós via random cyclic orderings
Abstract
We present a simplified proof of the Erdős-Sós conjecture on trees in graphs, which is based on its recent resolution by GPT-6 Astra. At the same time, we also give another proof of the corresponding conjecture for antidirected trees in digraphs, posed by Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé, and we simplify recent proofs of Kalai's conjecture for tight trees in hypergraphs. Our proof uses the language of random cyclic orderings in order to take advantage of symmetries that were obscured in the original argument, and we hope that the reader will find it intuitive. We also characterize the extremal examples for Kalai's conjecture, and we generalize it to the setting of so-called fully directed r-uniform hypergraphs, whose edges are ordered r-tuples.
Related
- Cyclic Incidence Orderings of Complete Graphs and 3-Uniform Hypergraphs
- Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
- A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
- Universal Radial Laws for Random Polynomials: Erdős Problem #522 and Non-Universal Fluctuations
- Diffusion limits of cyclic finite-velocity random motions along vector fields
BibTeX
@misc{frederickson2026erdőssós,
title = {{Erdős-Sós via random cyclic orderings}},
author = {Bryce Frederickson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.21159},
eprint = {2609.21159},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21159},
}
RIS
TY - UNPB
TI - Erdős-Sós via random cyclic orderings
AU - Bryce Frederickson
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2609.21159
UR - https://arxiv.org/abs/2609.21159
AB - We present a simplified proof of the Erdős-Sós conjecture on trees in graphs, which is based on its recent resolution by GPT-6 Astra. At the same time, we also give another proof of the corresponding conjecture for antidirected trees in digraphs, posed by Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé, and we simplify recent proofs of Kalai's conjecture for tight trees in hypergraphs. Our proof uses the language of random cyclic orderings in order to take advantage of symmetries that were obscured in the original argument, and we hope that the reader will find it intuitive. We also characterize the extremal examples for Kalai's conjecture, and we generalize it to the setting of so-called fully directed r-uniform hypergraphs, whose edges are ordered r-tuples.
ER -