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