Generating random graphs in biased Maker-Breaker games

Asaf Ferber, Michael Krivelevich, Humberto Naves

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker-Breaker games. In particular, we show that for b=o(n), Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a (1:b) game on E(Kn). As another application, we show that for b=Θ(n/lnn), playing a (1:b) game on E(Kn), Maker can build a graph which contains copies of all spanning trees having maximum degree Δ=O(1) with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T).

Original languageEnglish (US)
Pages (from-to)615-634
Number of pages20
JournalRandom Structures and Algorithms
Volume47
Issue number4
DOIs
StatePublished - Dec 2015

Bibliographical note

Publisher Copyright:
© 2015 Wiley Periodicals, Inc.

Keywords

  • Games
  • Random Graphs

Fingerprint

Dive into the research topics of 'Generating random graphs in biased Maker-Breaker games'. Together they form a unique fingerprint.

Cite this