Combinatorics Seminar

When: Sunday, May 18, 10am

Where: Schreiber 309

Speaker: Alon Naor, Tel Aviv U.

Title: Saturation Games


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.

w3c valid   accessible website
redesigned by barak soreq