Research Topic: Maker-Breaker games on random graphs
Working Groups: Lehrstuhl Diskrete Mathematik
Collaborators (MAT): Dr. Dennis Clemens, Fabian Hamann, M. Sc., Yannick Mogge, M. Sc.
Collaborators (External): Pranshu Gupta, Laurin Kirsch
Description
Biased Maker-Breaker games are played on some hypergraph \((X,\mathcal{F})\), where \(\mathcal{F}\) denotes the family of winning sets. For some biases \(m,b\), during each round of such a game Maker claims (up to) \(m\) elements of \(X\), followed by Breaker claiming (up to) \(b\) elements. If Maker is able to claim all elements of a winning set, she wins the game, otherwise Breaker is declared the winner.
Instead of playing on a complete graph \(K_n\) we can consider different boards, for example a random graph \(G \sim G_{n,p}\) with \(n\) vertices, where each edge is present in the graph with probability \(p\). Another option is to consider randomly perturbed graphs, which are the union of a random graph \(G \sim G_{n,p}\) and a deterministic graph \(G_{\alpha}\) with minimum degree \(\alpha\).
