TUHH / Institut für Mathematik / Forschungsgebiete / Maker-Breaker games on randomly perturbed graphs Englische Flagge

Maker-Breaker games on randomly perturbed graphs

Working Groups: Lehrstuhl Diskrete Mathematik

Collaborators (MAT): Dr. Dennis Clemens, Fabian Hamann, M. Sc., Yannick Mogge, M. Sc.

Collaborators (External): Olaf Parczyk


Maker-Breaker games are played on a hypergraph \((X,\mathcal{F})\), where \(\mathcal{F} \subseteq 2^X\) denotes the family of winning sets. Both players alternately claim a predefined number (called bias) of unclaimed edges from the board \(X\), and Maker wins the game if she is able to occupy any winning set \(F \in \mathcal{F}\). These games are well studied when played on the complete graph \(K_n\) or on a random graph \(G_{n,p}\). In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph \(G_\alpha\) with minimum degree at least \(\alpha n\) and a binomial random graph \(G_{n,p}\). Depending on \(\alpha\) and Breaker?s bias \(b\) we determine the order of the threshold probability for winning the Hamiltonicity game and the \(k\)-connectivity game on \(G_{\alpha}\cup G_{n,p}\), and we discuss the \(H\)-game when \(b=1\).


[1] D. Clemens, F. Hamann, Y. Mogge, and O. Parczyk. Maker-Breaker games on randomly perturbed graphs, arXiv:2009.14583 (2020), accepted for publication in SIAM J. Discrete Math.