Rainbow connectivity Maker-Breaker game
Juri Barkey, Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački, Miloš Stojaković · 2026
Read Rainbow connectivity Maker-Breaker game by Juri Barkey, Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački, Miloš Stojaković (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09770.txt.
Introduction
Juri Barkey and coauthors analyse a Maker Breaker game where Maker must claim rainbow paths between every pair of points. Edges may come from several given graphs, with at most one edge taken from each. They pin down the threshold bias on complete graphs, up to the role of how many graphs are in play. The work also settles the bias order for a diameter game.
Catalog record
| CREATOR | Juri Barkey, Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački, Miloš Stojaković |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116862 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.09770
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rainbow connectivity Maker-Breaker game Juri Barkey, Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački, Miloš Stojaković Abstract We study biased Maker-Breaker games on a graph system { G 1 , … , G s } \{G_{1},\ldots,G_{s}\} , in which Maker’s goal is to claim certain rainbow structures, i.e., specified subgraphs consisting of at most one edge from each graph G i G_{i} . We consider the rainbow-connectivity game, in which Maker wants to claim a rainbow path between every pair of vertices. We analyse this game in detail, essentially determining the threshold bias when played on the system of complete graphs, and observing that whether the random graph intuition holds depends on the size of s s . The key ingredient of our result is the analysis of a Maker’s strategy that combines several randomized strategies with an appropriately designed balancing game. As a byproduct, we find the order of the threshold bias for the Maker-Breaker diameter game, and disprove a conjecture by Balogh, Martin and Pluhár. Another natural and general way to analyse Maker-Breaker games that are played on a colored board is to require Maker to occupy a rainbow winning set of a given positional game. In the case of the connectivity game, Maker’s goal is to claim a rainbow spanning tree. For this game played on the system of complete graphs, we establish matching upper and lower bounds on the threshold bias, up to constant factors. 1 Introduction 1.1 Rainbow Combinatorics A recent trend in combinatorics is the study of rainbow variants of central results in extremal and random graph theory, see, e.g., the survey [ 41 ] . One of the earliest and most famous problems in this direction is the well-known Ryser-Brualdi-Stein Conjecture [ 11 , 37 , 39 ] on the existence of long transversals in Latin squares, which can be reformulated as a question on rainbow matchings, and which was recently resolved for every large enough Latin square of even size in the breakthrough paper of Montgomery [ 34 ] . Partially motivated by this problem, one popular type of rainbow questions in the literature considers the search for transversals and rainbow structures in systems of graphs. The central definition for these problems is as follows. Definition 1 . Let m\in\mathbb{N} and let \mathcal{G}=\{G_{1},G_{2},\ldots,G_{m}\} be a system of graphs on the same vertex set V . Then a graph H on V with m edges is called transversal in G if it contains exactly one edge of each of the graphs G_{i} , that is, if there exists a bijection \phi:E(H)\rightarrow[m] such that e is contained in G_{\phi(e)} for every edge e\in E(H) . Similarly, if H has at most m edges, then it is called rainbow in G if it contains at most one edge of each of the graphs G_{i} . Note that one may identify each of the graphs G_{i} with a distinct color c_{i} . Then the union G=(V,E) with E=\bigcup_{i\in[m]}E(G_{i}) can be considered as a colored multigraph, and H\subseteq G being rainbow simply means that the edges of H have distinct colors. Recent results in this area cover the cases when H is a triangle [ 1 ] , a perfect matching or a Hamilton cycle [ 4 , 8 , 14 , 20 , 30 ] , or a more complex structure [ 10 , 9 , 12 , 15 , 24 , 26 ] . We quickly mention two highlights from this list of papers. Let \mathcal{G}=\{G_{1},\ldots,G_{n}\} be a system of Dirac graphs, i.e., each graph has minimum degree at least \frac{n}{2} . Then Bradshaw et al. [ 8 ] prove that \mathcal{G} has at least \left(\left(\frac{1}{64}-o(1)\right)n\right)! rainbow Hamilton cycles. Moreover, Anastos et al. [ 4 ] show that there is a constant c>0 with the following property: If G is a Dirac graph on n vertices and if additionally \{H_{1},\ldots,H_{n}\} is a system of random graphs distributed independently like G_{n,p} , with p\geq\frac{c\log(n)}{n^{2}} , then the system \{G\cap H_{1},\ldots,G\cap H_{n}\} has a rainbow Hamilton cycle a.a.s. (asymptotically almost surely). In the following, we study biased Maker-Breaker games on graph systems, where we put a focus on two different notions of connectivity in the rainbow setting. 1.2 Maker-Breaker games Given a hypergraph \mathcal{H}=(X,\mathcal{F}) and an integer b\in\mathbb{N} , the (1:b) Maker-Breaker game on \mathcal{H} is played as follows. Maker and Breaker alternatingly claim unclaimed elements of the given board X . In every round, Maker claims 1 element and then Breaker claims b elements, until all the elements are claimed. Maker wins if at the end of the game she claimed all elements of a winning set F\in\mathcal{F} , and Breaker wins otherwise, i.e., if he claimed at least one element in every winning set. Maker-Breaker games have a long history of research, starting from the seminal papers of Hales and Jewett [ 25 ] and Chvátal and Erdős [ 16 ] , with the biggest research output done in the last roughly twenty years. For an overview on Maker-Breaker games and other positional games, we refer to the survey [ 32 ] and the book [ 28 ] . An important fact about biased Maker-Breaker games, which was already observed by Chvátal and Erdős [ 16 ] , is that these game are bias monotone. That is, for any game \mathcal{H}=(X,\mathcal{F}) , if Breaker wins the (1:b) game, then he also wins the (1:b+1) game. In particular, as long as \min\{|A|:A\in\mathcal{F}\}\geq 2 , there is a unique integer b_{\mathcal{H}} such that Breaker wins the (1:b) game on \mathcal{H} if and only if b\geq b_{\mathcal{H}} . This integer, referred to as the threshold bias of the game \mathcal{H} , has become a central object of study in the theory on Maker-Breaker games, see, e.g., [ 2 , 5 , 7 , 21 , 23 , 27 , 31 , 33 ] . As a prominent and well-studied example, let us consider the connectivity game on the complete graph K_{n} . This game is played on the hypergraph \mathcal{C}_{n}=(X,\mathcal{F}) , where X is the edge-set of the complete graph, X=E(K_{n}) , and the winning sets \mathcal{F} are the edge sets of all spanning trees in K_{n} . Chvátal and Erdős [ 16 ] proved that b_{\mathcal{C}_{n}} is of the order \frac{n}{\log(n)} , leaving it as an open problem to determine the precise constant of the leading term. This was resolved 30 years later by Gebauer and Szabó [ 23 ] , improving on an intermediate result by Beck [ 6 ] to show that b_{\mathcal{C}_{n}}=(1+o(1))\frac{n}{\log(n)} . Note that this result is surprising in the following way. If Maker and Breaker would play purely at random, Maker’s final graph would be a random graph on \lceil\frac{1}{b+1}\binom{n}{2}\rceil edges. Such a random graph is known to be connected a.a.s. if b\geq(1+\varepsilon)\frac{n}{\log(n)} and it is disconnected a.a.s. if b\leq(1-\varepsilon)\frac{n}{\log(n)} (see, e.g., [ 3 , 22 ] ). Hence, a game between two random players is “quite likely” to have the same winner as the game between two players playing optimally. This exciting connection between Maker–Breaker games and random graphs is now widely recognized in the literature as the random graph intuition , or the Erdős paradigm . The results by Chvátal