Combinatorics Seminar
When: Sunday, March 23, 10am
Where: Schreiber 309
Speaker: Ohad Feldheim, Tel Aviv University,
Title: Winning fast in graph construction games
Abstract:
In a graph construction game two players take turns in choosing
previously unoccupied edges of the complete graph K_N. In the
"strong" variant both players try to claim a copy of a given
graph G first, while in the "weak" variant, one player called Maker
tries to claim a copy of G while the other called Breaker aims to
prevent him from doing so. In this talk, after a short introduction
to positional games, we will survey the theory of graph
construction games, and introduce some results regarding the
number of turns required for winning for large N and sparse G both
in the "weak" and the "strong" variants.
Our main result is that in the weak variant, for large enough
N and a target graph G of bounded maximum degree d (or even
d-degenerate) the number of turns required for winning is linear in
the size of G (though exponential in d). We also connect this
result to the celebrated Burr-Erdos conjecture from Ramsey theory
regarding d-degenerate graphs. Another result we show is that in
the strong variant for every G there exists G' that contains it
and can be won by the first player in a number of turns equal to
its size.
Joint work with M. Krivelevich.