2023/10/31 by Richard Montgomery, Montgomery, Richard, Matías Pavez‐Signé +3 · 2 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.20461
openalex publication_date 2023/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
For every k≥ 2 and Δ, we prove that there exists a constant CΔ,k such that the following holds. For every graph H with χ(H)=k and every tree with at least CΔ,k|H| vertices and maximum degree at most Δ, the Ramsey number R(T,H) is (k-1)(|T|-1)+σ(H), where σ(H) is the size of a smallest colour class across all proper k-colourings of H. This is tight up to the value of CΔ,k, and confirms a conjecture of Balla, Pokrovskiy, and Sudakov.