Size Ramsey Number of Bounded Degree Graphs for Games
GEBAUER, HEIDI
In: Combinatorics, Probability and Computing, 2013, vol. 22, no. 4, p. 499-516
Add to personal list- Summary
- We study Maker/Breaker games on the edges of sparse graphs. Maker and Breaker take turns at claiming previously unclaimed edges of a given graph H. Maker aims to occupy a given target graph G and Breaker tries to prevent Maker from achieving his goal. We show that for every d there is a constant c = c(d) with the property that for every graph G on n vertices of maximum degree d there is a graph H on at most cn edges such that Maker has a strategy to occupy a copy of G in the game on H. This is a result about a game-theoretic variant of the size Ramsey number. For a given graph G, $\hat{r}'(G)$ is defined as the smallest number M for which there exists a graph H with M edges such that Maker has a strategy to occupy a copy of G in the game on H. In this language, our result yields that for every connected graph G of constant maximum degree, $\hat{r}'(G) = \Theta(n)$ . Moreover, we can also use our method to settle the corresponding extremal number for universal graphs: for a constant d and for the class ${\cal G}_{n}$ of n-vertex graphs of maximum degree d, $s({\cal G}_{n})$ denotes the minimum number such that there exists a graph H with M edges where, for every G ∈ ${\cal G}_{n}$ , Maker has a strategy to build a copy of G in the game on H. We obtain that $s({\cal G}_{n}) = \Theta(n^{2 - \frac{2}{d}})$