Canonical Ramsey Numbers of Sparse Graphs
METADATA ONLY
Loading...
Author / Producer
Date
2025-09
Publication Type
Journal Article
ETH Bibliography
yes
METADATA ONLY
Data
Rights / License
Abstract
The canonical Ramsey theorem of Erdős and Rado implies that for any graph Η, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph ΚN contains a monochromatic, lexicographic, or rainbow copy of H. The least such N is called the Erdős-Rado number of H, denoted by ER(H). Erdős-Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős-Rado numbers of sparse graphs. For example, we prove that if H has bounded degree, then ER(H) is polynomial in | V (H)| if H is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree S and given path Pt, we study the minimum N such that every edge-coloring of KN contains a monochromatic copy of S or a rainbow copy of Pt. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
39 (3)
Pages / Article No.
1491 - 1519
Publisher
SIAM
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Ramsey theory; canonical colorings; paths; trees; sparse graphs
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
Notes
Funding
228014 - 10001163 - Ramsey and Turan Type Problems (SNF)