## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, December 11, 2007, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Tibor Szabó

## On the rules of avoiding

We consider two-player positional games played on the edges of the complete graph. Players Avoider and Enforcer take turns in occupying yet unoccupied edges of $K_n$. In each round Avoider occupies one edge and Enforcer occupies $b$ edges. Avoider wins the game of connectivity if at the end of the game his edges do NOT occupy a spanning tree, otherwise Enforcer wins. Other frequently studied games involve the graph theoretic properties of having minimum degree at least $k$, containing a perfect matching, or a Hamilton cycle. In general, we are searching for the smallest bias $b$ against which Avoider is able to win these games against a skillful Enforcer. In the talk I will elaborate on a couple of surprising phenomena related to this problem.

Joint work with D. Hefetz, M. Krivelevich, and M. Stojaković.

Information for students and suggested topics for student talks