The Namer–Claimer game

Ben Barber

doi:10.1016/j.disc.2020.112256

The Namer–Claimer game

Ben Barber

Pure Mathematics

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

102 Downloads (Pure)

Abstract

In each round of the Namer–Claimer game, Namer names a distance d, then Claimer claims a subset of [n] that does not contain two points that differ by d. The game ends once sets covering [n] have been claimed. We show that the length of this game is Θ(loglogn) with optimal play from each side. This parameter is an online analogue of the previously studied upper chromatic number for the family of ‘distance-d’ graphs on [n], and the analysis reveals a surprising connection to the Ramsey theory of Hilbert cubes. We also suggest some variations of this game.

Original language	English
Article number	112256
Journal	Discrete Mathematics
Volume	344
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2020.112256
Publication status	Published - 1 Mar 2021

Access to Document

10.1016/j.disc.2020.112256

namer-claimerAccepted author manuscript, 224 KBLicence: CC BY-NC-ND

Cite this

@article{fc18d88d556b4d1a8135254b1a79b8a1,

title = "The Namer–Claimer game",

abstract = "In each round of the Namer–Claimer game, Namer names a distance d, then Claimer claims a subset of [n] that does not contain two points that differ by d. The game ends once sets covering [n] have been claimed. We show that the length of this game is Θ(loglogn) with optimal play from each side. This parameter is an online analogue of the previously studied upper chromatic number for the family of {\textquoteleft}distance-d{\textquoteright} graphs on [n], and the analysis reveals a surprising connection to the Ramsey theory of Hilbert cubes. We also suggest some variations of this game.",

author = "Ben Barber",

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

year = "2021",

month = mar,

day = "1",

doi = "10.1016/j.disc.2020.112256",

language = "English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "3",

}

TY - JOUR

T1 - The Namer–Claimer game

AU - Barber, Ben

PY - 2021/3/1

Y1 - 2021/3/1

N2 - In each round of the Namer–Claimer game, Namer names a distance d, then Claimer claims a subset of [n] that does not contain two points that differ by d. The game ends once sets covering [n] have been claimed. We show that the length of this game is Θ(loglogn) with optimal play from each side. This parameter is an online analogue of the previously studied upper chromatic number for the family of ‘distance-d’ graphs on [n], and the analysis reveals a surprising connection to the Ramsey theory of Hilbert cubes. We also suggest some variations of this game.

AB - In each round of the Namer–Claimer game, Namer names a distance d, then Claimer claims a subset of [n] that does not contain two points that differ by d. The game ends once sets covering [n] have been claimed. We show that the length of this game is Θ(loglogn) with optimal play from each side. This parameter is an online analogue of the previously studied upper chromatic number for the family of ‘distance-d’ graphs on [n], and the analysis reveals a surprising connection to the Ramsey theory of Hilbert cubes. We also suggest some variations of this game.

U2 - 10.1016/j.disc.2020.112256

DO - 10.1016/j.disc.2020.112256

M3 - Article

AN - SCOPUS:85097787768

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

M1 - 112256

ER -

The Namer–Claimer game

Abstract

Access to Document

Fingerprint

Cite this