Metraipolis › archive › dc_2e09cf3358f4

Rainbow paths in directed graphs — arXiv:2609.06706

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06706
License (as archived)
CC0-1.0
Archived
2026-10-16T14:48:37.682Z
SHA-256 of the archived text
7b920dad160c4845a54053011710e9cd94e047ab3f6240b5988329091ccc1077
Stable URL of this page
https://metraipolis.com/documento/dc_2e09cf3358f4

How to cite

Rainbow paths in directed graphs — arXiv:2609.06706 — arXiv (en), https://arxiv.org/abs/2609.06706 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2e09cf3358f4 (Metraipolis archive dc_2e09cf3358f4, sha256 7b920dad160c4845a54053011710e9cd94e047ab3f6240b5988329091ccc1077)
BibTeX
@misc{dc2e09cf3358f4,
  title = {Rainbow paths in directed graphs — arXiv:2609.06706},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06706},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2e09cf3358f4; sha256 7b920dad160c4845a54053011710e9cd94e047ab3f6240b5988329091ccc1077},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06706. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

An old problem in combinatorial group theory asks, given a group $\Gamma$ and a subset $S \subseteq \Gamma$, when does there exist an ordering $s_1, \cdots, s_k$ of the elements of $S$ such that the partial products $\prod_{i = 1}^j s_i$, $1 \leq j \leq 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 $\Gamma$ and any subset $S \subseteq \Gamma$, there exists a rearrangeable set $S' \subseteq 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 $\Gamma$ with (not necessarily generating) set $S$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.06706 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:32:29.798Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).