The Rainbow Arborescence Problem on Cycles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi · 2025
Read The Rainbow Arborescence Problem on Cycles by Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi (2025) 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-2511-04953.txt.
Introduction
Kristóf Bérczi and co-authors prove a case of the rainbow arborescence guess, a claim about directed graphs whose arcs are painted in many colors. In the set-up, each color class by itself forms a spanning tree shape that fans out from a root.
The guess says a spanning tree exists that uses each color once and only once. The authors prove it when the base undirected graph is a simple cycle. Their proof adds one firm case to a broad open claim in graph theory, where most graph shapes still lack a proof.
Catalog record
| CREATOR | Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04953
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Rainbow Arborescence Problem on Cycles Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi Abstract The rainbow arborescence conjecture posits that if the arcs of a directed graph with n n vertices are colored by n − 1 n-1 colors such that each color class forms a spanning arborescence, then there is a spanning arborescence that contains exactly one arc of every color. We prove that the conjecture is true if the underlying undirected graph is a cycle. 1 Introduction The rainbow arborescence conjecture posits that if a directed graph with n vertices is the disjoint union of spanning arborescences A_{1},\dots,A_{n-1} (called colors ), then one can choose a_{c}\in A_{c} ( c\in\{1,\dots,n-1\} ) such that \{a_{1},\dots,a_{n-1}\} is a spanning arborescence. The conjecture was proposed several years ago by one of the authors [ 5 , Open Problem: Rainbow Arborescence Problem] and it is still wide open, but some special cases are solved; see [ 3 ] for proofs of partial results towards the conjecture, as well as a detailed account of related problems. The rainbow arborescence problem is related to the Ryser–Brualdi–Stein conjecture on Latin squares [ 4 , 7 ] and more specifically to its generalization to matroid intersection by Aharoni, Kotlar, and Ziv [ 1 , 2 ] . This conjecture proposes that for any two matroids on the same ground set and any given k pairwise disjoint common independent sets of size k , there exists a common independent set of size k-1 intersecting each of the k sets in at most one element. Notice that the rainbow arborescence conjecture is stronger than the matroid intersection conjecture specialized to spanning arborescences: the latter would only imply the existence of a branching of size n-2 whose arcs have different colors. In terms of the structure of the graph, one of the simplest open cases of the rainbow arborescence conjecture is when the underlying undirected graph is a cycle (with possible parallel edges, which are inevitable as there are (n-1)^{2} arcs). As the main result of this paper, we show that the conjecture is true in this case. Interestingly, although the structure seems simple, the conjecture turned out to be much more difficult to prove than in previously settled cases. In addition to the main theorem, we also show an interesting corollary about systems of distinct representatives of a family of intervals on the cycle. We proceed by introducing the notation and formal definitions, followed by a description of the results. We use the notation [k]=\{1,\dots,k\} . Let (V,E) be a directed cycle of length n , where V=\{v_{1},\dots,v_{n}\} , e_{j}=v_{j}v_{j+1} ( j\in[n-1] ), and e_{n}=v_{n}v_{1} . We will usually consider the indices modulo n , i.e., v_{n+j}=v_{j} and e_{n+j}=e_{j} . We denote the reverse arc of e_{j} by f_{j} , that is, f_{j}=v_{j+1}v_{j} . The arcs e_{j} will be called clockwise arcs , while the arcs f_{j} are anticlockwise arcs . The graph G=(V,E\cup F) is the bidirected cycle of length n , where F=\{f_{j}:j\in[n]\} . For a set X of arcs, we denote by u(X) the set of corresponding edges in the underlying undirected graph; when X=\{e\} for a single arc e , we denote by u(e) the singleton of the underlying edge of e or the edge itself (depending on the context). A spanning arborescence A of G can be characterized by a pair of its root and the (undirected) edge that does not use in either direction. The latter will be called the missing edge of A , which is sometimes referred to as the corresponding arc of any direction. Let A_{1},\dots,A_{n-1} be spanning arborescences of G . A spanning arborescence A of G is called rainbow if we can pick arcs a_{c}\in A_{c} ( c\in[n-1] ) such that A=\{a_{1},\dots,a_{n-1}\} . We remark that deciding whether a given spanning arborescence is rainbow amounts to solving a perfect matching problem in a bipartite graph, namely the graph with classes A and [n-1] where a\in A and c\in[n-1] are joined by an edge if a\in A_{c} . Our main result is the following theorem, which states that a rainbow arborescence always exists. Theorem 1 . Let G be defined as above, and let A_{1},\dots,A_{n-1} be arbitrary spanning arborescences of G . We can pick arcs a_{c}\in A_{c} (c\in[n-1]) such that A=\{a_{1},\dots,a_{n-1}\} is a spanning arborescence of G . The theorem claims that the conjecture is true when the underlying graph is a cycle. Combining this with the argument for the case where the underlying graph is a tree 1 1 1 Suppose that v is a leaf of the underlying graph. If v has an incoming arc of some color c , then one can reduce the instance by removing v and c ; otherwise, v is the roots of all colors and then one can construct a rainbow spanning arborescence in a greedy way. For more details, see the proof of the tree case [ 3 , Theorem 3.7] . in [ 3 ] , one can easily see that this is also true when the underlying graph is a pseudotree (a connected graph having at most one cycle). Corollary 2 . The rainbow arborescence conjecture is true when the underlying graph is a pseudotree. Before proving the theorem, we present two observations. First, in contrast to the general case in [ 3 ] , deciding whether there is a rainbow arborescence with a given root r is polynomial-time solvable on a cycle, since there are n possible spanning arborescences rooted at r , and we can check for all of them whether they are rainbow or not via bipartite matching. Second, Theorem 1 implies an interesting new result on systems of distinct representatives of subsets of a cycle. Let C=(V,E) be a directed cycle of length n (here, the cycle being directed is irrelevant to the result, but it will be useful in the proof). An edge set I\subseteq E is called an interval of C if I=\emptyset , I=E , or I is a path. Given a family E_{1},\dots,E_{k} of (not necessarily distinct) subsets of E , a system of distinct representatives for E_{1},\dots,E_{k} is an edge set S\subseteq E of size k and a bijection \sigma\colon S\to[k] such that e\in E_{\sigma(e)} for every e\in S . For two sets X and Y , their symmetric difference is denoted by X\triangle Y=(X\setminus Y)\cup(Y\setminus X) . Theorem 3 . Let C=(V,E) be a directed cycle of length n , and let I_{1},\dots,I_{n} be arbitrary (not necessarily distinct) intervals of C . Then there exists an interval J^{*} of C such that the family I_{1}\triangle J^{*},\dots,I_{n}\triangle J^{*} has a system of distinct representatives. Proof. We have to show that there exist an interval J^{*} of C and a bijection \sigma\colon E\to[n] such that e\in I_{\sigma(e)}\triangle J^{*} for every e\in E . We define the bidirected cycle G=(V,E\cup F) as in the beginning of the section and use the terminology of clockwise and anticlockwise edges similarly. For each interval I_{i} ( i\in[n-1] ), we define a spanning arborescence A_{i} of G the following way. • If I_{i}=\emptyset , then A_{i} is an arbitrary anticlockwise path of length n-1 . • If I_{i}=E , then A_{i} is an