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>