Bar-Ilan Combinatorics Seminar The next meeting of the seminar will take place, IYH, (when) Sunday, 7 Iyar (Apr. 29), 14:00-15:30 (where) Room 201 (Math & CS Seminar Room), Building 216, Bar-Ilan University (who) Asaf Ferber (Tel-Aviv University) (what) Winning fast in Maker-Breaker games played on sparse random boards Abstract: In this talk we consider Maker-Breaker games played on random boards. Given a graph G=(V,E) and a graph property P, the Maker-Breaker game P played on G is defined as follows. In every round Maker and Breaker alternately claim free edges from E. Maker wins this game as soon as his graph possesses P. Otherwise, Breaker wins the game. We consider the perfect matching, hamiltonicity and k-connectivity games played on a sparse random board G(n,p), p>=polylog(n)/n. It is clear that Maker needs at least n/2, n, kn/2 moves to win these games, respectively. We prove that G(n,p) is typically such that Maker has a strategy to win within n/2+o(n), n+o(n), kn/2+o(n) moves, respectively. We also show a connection between fast strategies in Maker-Breaker games (weak games) and Maker-Maker games (strong games). Joint work with Dennis Clemens, Anita Liebenau and Michael Krivelevich. ************************************************************************* You are all invited! Graduate students are especially welcome. Seminar organizer: Ron Adin <radin@math.biu.ac.il> Seminar's homepage: <http://www.math.biu.ac.il/~radin/comsem/comsem.html> ************************************************************************* --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Ron Adin <radin@math.biu.ac.il>