pith. the verified trust layer for science. sign in

arxiv: 1310.4096 · v4 · pith:5GQ63XRWnew · submitted 2013-10-15 · 🧮 math.CO

Generating random graphs in biased Maker-Breaker games

classification 🧮 math.CO
keywords biasedgamesgraphmaker-breakerpathapproachbarebuild
0
0 comments X p. Extension
Add this Pith Number to your LaTeX paper What is a Pith Number?
\usepackage{pith}
\pithnumber{5GQ63XRW}

Prints a linked pith:5GQ63XRW badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original 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\left(\sqrt{n}\right)$, 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(K_n)$. As another application, we show that for $b=\Theta\left(n/\ln n\right)$, playing a $(1:b)$ game on $E(K_n)$, Maker can build a graph which contains copies of all spanning trees having maximum degree $\Delta=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$).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.