Premium
List Ramsey numbers
Author(s) -
Alon Noga,
Bucić Matija,
Kalvari Tom,
Kuperwasser Eden,
Szabó Tibor
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22610
Subject(s) - ramsey's theorem , mathematics , combinatorics , bounded function , graph , extension (predicate logic) , discrete mathematics , exponential function , computer science , mathematical analysis , programming language
We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For ℓ ‐uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well known that the Ramsey number is superexponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques.