Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Sam Spiro

UCSD

Saturation Games for Odd Cycles

Abstract:

Given a family of graphs $\mathcal{F}$, we define a game called the $\mathcal{F}$-saturation game. In this game, two players Mini and Max 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. Mini wishes to end the game as quickly as possible, while Max 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 the order of magnitude of $\textrm{sat}_g(\{C_3\},n)$ remains unknown. We consider a variant of this game, the $\{C_3,C_5\}$-saturationgame, and we show that the saturation number $\textrm{sat}_g(\{C_3,C_5\};n)$ is quadratic. As time permits we will discuss other games involving odd cycles, such as the $\{C_3,C_5,\ldots,C_{2k+1}\}$-saturation game and the $\{C_5,C_7,\ldots\}$ saturation game.

March 19, 2019

2:00 PM

AP&M 7321

****************************