Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T06:54:42.379Z Has data issue: false hasContentIssue false

The Game of JumbleG

Published online by Cambridge University Press:  11 October 2005

ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA (e-mail: alan@random.math.cmu.edu, pikhurko@andrew.cmu.edu)
MICHAEL KRIVELEVICH
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@post.tau.ac.il)
OLEG PIKHURKO
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA (e-mail: alan@random.math.cmu.edu, pikhurko@andrew.cmu.edu)
TIBOR SZABÓ
Affiliation:
Institut für Theoretische Informatik, ETH Zentrum, IFW B48.1, CH-8092 Zürich, Switzerland (e-mail: szabo@inf.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

JumbleG is a Maker–Breaker game. Maker and Breaker take turns in choosing edges from the complete graph $K_n$. Maker's aim is to choose what we call an $\epsilon$-regular graph (that is, the minimum degree is at least $(\frac12-\epsilon) n$ and, for every pair of disjoint subsets $S,T\subset V$ of cardinalities at least $\epsilon n$, the number of edges $e(S,T)$ between $S$ and $T$ satisfies $\bigl|\frac{e(S,T)}{|S|\,|T|}-\frac12\bigr|\leq \epsilon$.) In this paper we show that Maker can create an $\epsilon$-regular graph, for $\epsilon\geq 2(\log n/n)^{1/3}$. We also consider a similar game, JumbleG2, where Maker's aim is to create a graph with minimum degree at least $\bigl(\frac12-\epsilon\bigr)n$ and maximum co-degree at most $\bigl(\frac14+\epsilon\bigr)n$, and show that Maker has a winning strategy for $\epsilon> 3 (\log n/n)^{1/2}$. Thus, in both games Maker can create a pseudo-random graph of density $\frac12$. This guarantees Maker's win in several other positional games, also discussed here.

Information

Type
Paper
Copyright
2005 Cambridge University Press