Hostname: page-component-848d4c4894-r5zm4 Total loading time: 0 Render date: 2024-06-28T16:20:33.220Z 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: [email protected], [email protected])
MICHAEL KRIVELEVICH
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: [email protected])
OLEG PIKHURKO
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA (e-mail: [email protected], [email protected])
TIBOR SZABÓ
Affiliation:
Institut für Theoretische Informatik, ETH Zentrum, IFW B48.1, CH-8092 Zürich, Switzerland (e-mail: [email protected])

Abstract

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.

Type
Paper
Copyright
2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)