Hamburg University of Technology / Institute of Mathematics / Research Topics / Maker-Breaker games on randomly perturbed graphs German flag

Maker-Breaker games on randomly perturbed graphs

Working Groups: Chair Discrete Mathematics

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

Collaborators (External): Olaf Parczyk

Description

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\).

References

[1] D. Clemens, F. Hamann, Y. Mogge, and O. Parczyk, Maker-Breaker Games on Randomly Perturbed Graphs, SIAM Journal on Discrete Mathematics 35 (2021), no. 4, 2723–2748.