On the optimality of the uniform random strategy. Issue 2 (10th December 2018)

• Record Type: Journal Article
• Authors: Kusch, Christopher; Rué, Juanjo; Spiegel, Christoph; Szabó, Tibor
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 371
• Page End: 401
• Publication Date: 2018-12-10
• Subjects: arithmetic Ramsey theory -- positional games -- probabilistic method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20829
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Biased Maker‐Breaker games, introduced by Chvátal and Erdős, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain "container‐type" regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H ‐building games studied by Bednarska and Łuczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.