# Combinatorics Seminar

When: Sunday, May 18, 10am

Where: Schreiber 309

Speaker: Alon Naor, Tel Aviv U.

Title: Saturation Games

## Abstract:

Let P be a monotone increasing graph property and let G be a graph on n
vertices which does not satisfy P. An edge e in K_n - G is called legal
(with respect to G and P) if G union {e} does not satisfy P. A graph G is
P-saturated if it does not satisfy P and there are no legal edges
(with respect to G and P).

In the saturation game (n,P) two players, called Minimizer and Maximizer,
build together a graph G in K_n which does not satisfy P. Minimizer and
Maximizer take turns is claiming legal edges (starting from the empty graph
on n vertices) until none exist. At this point the game is over, and the
resulting graph G is P-saturated. The score of the game is the number of
edges in G at the end of the game. Minimizer's goal is to minimize the
score of the game, while Maximizer's goal it to maximize the score of
the game.

We analyze saturation games for several graph properties, such as
P = "being k-connected", P = "having chromatic number at least k"
and P = "containing a k-matching", showing some surprising results.

Joint work with Dan Hefetz, Michael Krivelevich and Milos
Stojakovic.

redesigned by barak soreq