Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 19, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Dan Hefetz (Tel Aviv Univ.)
Let p and q be positive integers and let H be a hypergraph. In a (p,q,H) Avoider-Enforcer game two players, called Avoider and Enforcer, take turns selecting previously unclaimed vertices of H. Avoider selects p vertices per move and Enforcer selects q vertices per move. Avoider loses if he claims all the vertices of some hyperedge of H, otherwise Enforcer loses. We prove a sufficient condition for Avoider to win the (p,q,H) game, and use it to analyze several classic games - connectivity, hamiltonicity and perfect matching.
Some of our results are quite surprising as they differ from those obtained for the analogous Maker-Breaker games.
(Joint work with Michael Krivelevich and Tibor Szabó)
Automatic MiSe System Software Version 1.4803M | admin login