Strong games played on random graphs

MaRDI QIDQ510354zbMATH OpenFDO

Authors Asaf Ferber, Pascal Pfister

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04229, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p35

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

perfect matchingpositional gamesrandom graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique, a perfect matching, a Hamilton cycle, etc.). It is well known that Red can always ensure at least a draw in any strong game, but finding explicit winning strategies is a difficult and a quite rare task. We consider strong games played on the edge set of a random graph G ~ G(n,p) on n vertices. We prove, for sufficiently large $n$ and a fixed constant 0 < p < 1, that Red can w.h.p win the perfect matching game on a random graph G ~ G(n,p).

Recommendations

• Positional games on random graphs
• Winning strong games through fast strategies for weak games
• Fast strategies in maker-breaker games played on random boards
• Hitting time results for maker-breaker games
• scientific article; zbMATH DE number 3970795

Cites work

• An algorithm for finding hamilton cycles in random directed graphs
• Combinatorial Games
• Equitable coloring of random graphs
• Fast winning strategies in maker-breaker games
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2200042 (Why is no real title available?)
• Inevitable randomness in discrete mathematics
• Random graphs.
• Regularity and Positional Games
• Weak and strong \(k\)-connectivity games
• Winning strong games through fast strategies for weak games

Cited in

(7)

• A matching game
• The matcher game played in graphs
• Proper strong-Fibonacci games
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• Trapping games on random boards
• Product rule wins a competitive game
• Winning strong games through fast strategies for weak games

This page was built for publication: Strong games played on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510354)