Davoodi 2026 asymptotic version erdos sos conjecture beyond

../

---

Akbar Davoodi, Diana Piguet, Hanka Řada, Nicolás Sanhueza-Matamala, The asymptotic version of the Erdős-Sós conjecture and beyond. arXiv preprint (2026). arXiv:2603.17755, doi:10.48550/arXiv.2603.17755. The arXiv record names arXiv's non-exclusive distribution license (arXiv:2603.17755), every other right reserved.

The copy read for this card is arXiv:2603.17755v1 (18 March 2026, 104 pages), the only version on the arXiv listing (API record read). Read status: claims checked for Conjecture 1.2, Theorem 1.3 and Corollaries 1.4--1.6 (pp. 3--4), read on the page images, with the proofs of the corollaries (pp. 5--8) read for their inputs only; the proof of Theorem 1.3 was not read. The paper's target is Conjecture 1.2 of Klimošová, Piguet and Rozhoň (p. 3): an n-vertex graph with minimum degree at least k/2 and at least n/(2 sqrt k) vertices of degree at least k contains every tree with k edges. Theorem 1.3 (p. 3) proves an approximate form for dense hosts: for eta, q > 0, n large and k >= qn, every n-vertex graph with minimum degree at least (1 + eta)k/2 and at least eta n vertices of degree at least (1 + eta)k contains every tree with k edges. Corollary 1.4 (p. 3) deduces the Erdős–Sós conjecture in the same approximate dense form: for k >= qn and n large, average degree above (1 + eta)k forces every tree with at most k edges, whatever its maximum degree. Corollary 1.5 (p. 3), proved with a hyper-stability theorem of Pokrovskiy (Theorem 3.1, p. 6), keeps the degree conditions of Theorem 1.3 but drops k >= qn, for trees with at most k edges and maximum degree at most a fixed Delta, once k is large. For problem 557, Corollary 1.6 (p. 4; proved on p. 8 from Corollary 1.4) bounds the r-color Ramsey number of arbitrary trees, with no degree restriction: for r >= 2 and eps > 0, R_r(T_1, ..., T_r) <= (1 + eps)(|V(T_1)| + ... + |V(T_r)|) once that sum is large. For one tree T on n vertices this gives R_r(T) <= rn + o(n), short of the error O(1) that the problem asks for.

Source: https://arxiv.org/abs/2603.17755.

Bears on. #557 (Corollary 1.6, p. 4: R_r(T) <= rn + o(n) for every tree T on n vertices, short of the O(1) error asked); #548 (Corollary 1.4, p. 3: the Erdős–Sós statement in an approximate dense form, average degree above (1 + eta)k forcing every tree with at most k edges when k >= qn and n is large).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.