Restricted online Ramsey numbers of matchings and trees

DOI10.37236/8649MaRDI QIDQ2195227zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 8 September 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1904.00246

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$, which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builder's goal is to locate a particular monochromatic structure in Painter's coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this "particular monochromatic structure" is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching on at least $n-t+1overt+1$ edges by revealing at most $O(nlogt)$ edges. We show also that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on at least $n/2$ vertices by revealing at most $5n$ edges.

Review text

Summary: Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of \(K_n\), which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builder's goal is to locate a particular monochromatic structure in Painter's coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this ``particular monochromatic structure is a large matching or a large tree. We show that in any \(t\)-coloring of \(E(K_n)\), Builder can locate a monochromatic matching on at least \(\frac{n-t+1}{t+1}\) edges by revealing at most \(O(n\log t)\) edges. We show also that in any \(3\)-coloring of \(E(K_n)\), Builder can locate a monochromatic tree on at least \(n/2\) vertices by revealing at most \(5n\) edges.

Recommendations

• A note on restricted online Ramsey numbers of matchings
• An upper bound for the restricted online Ramsey number
• On-line Ramsey Numbers
• On-line Ramsey numbers for paths and short cycles
• On-line Ramsey theory for bounded degree graphs

Cites work

• An upper bound for the restricted online Ramsey number
• Covering the complete graph by partitions
• scientific article; zbMATH DE number 524119 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• On-line Ramsey Numbers
• Online Ramsey numbers and the subgraph query problem
• The Ramsey number for stripes
• Two variants of the size Ramsey number

Cited in

(4)

• A note on restricted online Ramsey numbers of matchings
• An upper bound for the restricted online Ramsey number
• On induced online Ramsey number of paths, cycles, and trees
• Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze

This page was built for publication: Restricted online Ramsey numbers of matchings and trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195227)