Premium
On the optimality of the uniform random strategy
Author(s) -
Kusch Christopher,
Rué Juanjo,
Spiegel Christoph,
Szabó Tibor
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20829
Subject(s) - hypergraph , van der waerden's theorem , generalization , matching (statistics) , mathematics , set (abstract data type) , container (type theory) , game theory , type (biology) , computer science , combinatorics , discrete mathematics , mathematical economics , theoretical computer science , mechanical engineering , mathematical analysis , ecology , statistics , engineering , biology , programming language
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.