Rainbow paths in directed graphs
Abstract
An old problem in combinatorial group theory asks, given a group Γ and a subset S ⊆ Γ, when does there exist an ordering s1, ⋯, sk of the elements of S such that the partial products ∏i = 1j si, 1 ≤ j ≤ k, are all distinct. If such an ordering exists, we call S rearrangeable. There have been many conjectures about rearrangeable subsets, the most general being that for every group, every subset not containing the identity element is rearrangeable. We prove an asymptotic version of this: For any Group Γ and any subset S ⊆ Γ, there exists a rearrangeable set S' ⊆ S such that |S'| = |S| − o(|S|). To do this we build upon the work of Bucić, Frederickson, Müyesser, Pokrovskiy, and Yepremyan focusing on the following problem of independent interest in Graph Theory. If G is a d-regular properly colored directed graph does there exist a rainbow path of length $d - 1$? We establish an asymptotic version of this, proving that G contains a rainbow path of length $d - o(d)$. This solves two problems given by Bucić, Frederickson, et al. and proves the above result on rearrangeable subsets of groups by considering the Cayley graph of Γ with (not necessarily generating) set S.
Related
- Rainbow Turán numbers for paths of length four
- Rainbow Hamiltonian paths in graph collections under edge-size conditions
- Weak rainbow saturation numbers of paths, stars and cycles
- Rainbow connecting $2$-colorings of super-Dirac graphs
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
BibTeX
@misc{wilson2026rainbow,
title = {{Rainbow paths in directed graphs}},
author = {Chase Wilson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06706},
eprint = {2609.06706},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06706},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rainbow paths in directed graphs
AU - Chase Wilson
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.06706
UR - https://arxiv.org/abs/2609.06706
AB - An old problem in combinatorial group theory asks, given a group Γ and a subset S ⊆ Γ, when does there exist an ordering s_1, ⋯, s_k of the elements of S such that the partial products ∏_i = 1^j s_i, 1 ≤ j ≤ k, are all distinct. If such an ordering exists, we call S rearrangeable. There have been many conjectures about rearrangeable subsets, the most general being that for every group, every subset not containing the identity element is rearrangeable. We prove an asymptotic version of this: For any Group Γ and any subset S ⊆ Γ, there exists a rearrangeable set S' ⊆ S such that |S'| = |S| − o(|S|). To do this we build upon the work of Bucić, Frederickson, Müyesser, Pokrovskiy, and Yepremyan focusing on the following problem of independent interest in Graph Theory. If G is a d-regular properly colored directed graph does there exist a rainbow path of length $d - 1$? We establish an asymptotic version of this, proving that G contains a rainbow path of length $d - o(d)$. This solves two problems given by Bucić, Frederickson, et al. and proves the above result on rearrangeable subsets of groups by considering the Cayley graph of Γ with (not necessarily generating) set S.
ER -