Saturation games for odd cycles

Sam Spiro¹

¹UC San Diego

The electronic journal of combinatorics, Tome 26 (2019) no. 4

Résumé

Given a family of graphs $\mathcal{F}$, we consider the $\mathcal{F}$-saturation game. In this game, two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph that lies in $\mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $\textrm{sat}_g(\mathcal{F};n)$ denote the number of edges that are in the final graph when both players play optimally. The $\{C_3\}$-saturation game was the first saturation game to be considered, but as of now the order of magnitude of $\textrm{sat}_g(\{C_3\},n)$ remains unknown. We consider a variation of this game. Let $\mathcal{C}_{2k+1}:=\{C_3,\ C_5,\ldots,C_{2k+1}\}$. We prove that $\textrm{sat}_g(\mathcal{C}_{2k+1};n)\ge(\frac{1}{4}-\epsilon_k)n^2+o(n^2)$ for all $k\ge 2$ and that $\textrm{sat}_g(\mathcal{C}_{2k+1};n)\le (\frac{1}{4}-\epsilon'_k)n^2+o(n^2)$ for all $k\ge 4$, with $\epsilon_k<\frac{1}{4}$ and $\epsilon'_k>0$ constants tending to 0 as $k\to \infty$. In addition to this we prove $\textrm{sat}_g(\{C_{2k+1}\};n)\le \frac{4}{27}n^2+o(n^2)$ for all $k\ge 2$, and $\textrm{sat}_g(\mathcal{C}_\infty\setminus C_3;n)\le 2n-2$, where $\mathcal{C}_\infty$ denotes the set of all odd cycles.

Détail

DOI : 10.37236/8113

Classification : 05C57, 91A43, 91A05
Mots-clés : \(\{C_3\}\)-saturation game, \(\mathcal{F}\)-saturation game