List Ramsey numbers

Noga Alon; Matija Bucić; Tom Kalvari; Eden Kuperwasser; Tibor Szabó

doi:10.1002/jgt.22610

List Ramsey numbers

Noga Alon, Matija Bucić, Tom Kalvari, Eden Kuperwasser, Tibor Szabó

Mathematics

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

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 (Formula presented.) -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.

Original language	English (US)
Pages (from-to)	109-128
Number of pages	20
Journal	Journal of Graph Theory
Volume	96
Issue number	1
DOIs	https://doi.org/10.1002/jgt.22610
State	Published - Jan 2021

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

Ramsey theory
chromatic number
list coloring

Access to Document

10.1002/jgt.22610

Cite this

@article{18751b05d62f49168a69e37a9ba8a298,

title = "List Ramsey numbers",

abstract = "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 (Formula presented.) -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.",

keywords = "Ramsey theory, chromatic number, list coloring",

author = "Noga Alon and Matija Buci{\'c} and Tom Kalvari and Eden Kuperwasser and Tibor Szab{\'o}",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals LLC",

year = "2021",

month = jan,

doi = "10.1002/jgt.22610",

language = "English (US)",

volume = "96",

pages = "109--128",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - List Ramsey numbers

AU - Alon, Noga

AU - Bucić, Matija

AU - Kalvari, Tom

AU - Kuperwasser, Eden

AU - Szabó, Tibor

PY - 2021/1

Y1 - 2021/1

N2 - 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 (Formula presented.) -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.

AB - 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 (Formula presented.) -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.

KW - Ramsey theory

KW - chromatic number

KW - list coloring

UR - http://www.scopus.com/inward/record.url?scp=85087182323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087182323&partnerID=8YFLogxK

U2 - 10.1002/jgt.22610

DO - 10.1002/jgt.22610

M3 - Article

AN - SCOPUS:85087182323

SN - 0364-9024

VL - 96

SP - 109

EP - 128

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

List Ramsey numbers

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this