The neighbourhood conjecture for Maker-Breaker games
Combinatorics Seminar
4th February 2025, 3:00 pm – 4:00 pm
Fry Building, 2.04
Consider the following game on a fixed, finite hypergraph H. Two players, Maker and Breaker alternately claim one not-yet-claimed vertex of H, until all the vertices are claimed. Maker wins if at the end of the game there exists a hyperedge all of whose vertices are claimed by Maker, otherwise Breaker wins. For a positive integer k, define D(k) to be the minimal n such that there exists a k-uniform hypergraph H on n vertices such that Maker wins on H going first. One version of Beck's Neighborhood Conjecture asserts that D(k) > c^k for some constant c > 1.
In this talk, we discuss the currently best-known bounds for D(k), the limitations of the methods used for proving them and possibly a generalization to biased games.
Comments are closed.