Combinatorics Seminar
Speaker: Prof. Anand Srivastav (Christian-Albrechts-Universität zu Kiel, Kiel, Germany)
Host: Sudhir Ghorpade
Title: The k-Hamilton Cycle Maker-Breaker Game
Time, day and date: 4:00:00 PM, Wednesday, March 12
Venue: Ramanujan Hall
Abstract: We study the Maker-Breaker k-Hamilton cycle game, k an integer constant, on the complete graph on n nodes, where the aim of Maker is to build k Hamilton cycles, while Breaker wishes to prevent it. This is a two-person perfect information game on a finite board, namely the edges of the complete graph.
The game is played under the following rules. Maker and Breaker alternately choose edges of the complete graph not taken by any of the players so far. Maker starts, and chooses one edge of the complete graph. Thereafter, Breaker may choose upto b free edges. The game ends without a draw latest after all edges have been choosen by the two players.
In such games, the challenging problem is to find the threshold bias b*, an integer, so that for b < b* there is a winning strategy for Maker, but for b > b* Breaker has a winning strategy, and to present such strategies.
Krivelevich (J. AMS 2010) determined in a breakthrough paper, extending foundational work of Chvatal and Erdös (1978), the asymptotially exact threshold bias to be (1 - o(1))n/ln(n) for k = 1. Brüstle, Clusiau, Narayan, Ndiaye, Reed & Seamone (2023) showed that for k = 1 the game can be won by Maker in at most n + Cn/sqrt(ln(n)) many rounds, C a constant, if b < n/ln(n) - cn/ln(n)^{3/2}. This is an asymptotically optimal round complexity.
The game for k > 1 is much more complicated because we must ensure edge-disjointness of the k Hamilton cycles, while these cycles are competing for favorable edges. We show that Maker wins the k-Hamilton cycle game, if b < n/ln(n) -c n/ln(n)^{3/2}, in at most kn + c'n/sqrt(ln(n)) rounds, c, c' being constants depending on k only.
This round complexity is asymptotically optimal as well.
(joint work with Jan Geest, Department of Mathematics, Kiel University)