Metraipolis › archive › dc_d6ca655ae062
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture — arXiv:2604.03735
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2604.03735
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:38:09.425Z
- SHA-256 of the archived text
4b9cb24f228668f9aa13d8bde5a20d433b90afaa9b0350fb4f17c72d21458282- Stable URL of this page
https://metraipolis.com/documento/dc_d6ca655ae062
How to cite
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture — arXiv:2604.03735 — arXiv (en), https://arxiv.org/abs/2604.03735 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d6ca655ae062 (Metraipolis archive dc_d6ca655ae062, sha256 4b9cb24f228668f9aa13d8bde5a20d433b90afaa9b0350fb4f17c72d21458282)
BibTeX
@misc{dcd6ca655ae062,
title = {Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture — arXiv:2604.03735},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2604.03735},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d6ca655ae062; sha256 4b9cb24f228668f9aa13d8bde5a20d433b90afaa9b0350fb4f17c72d21458282},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2604.03735. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study algorithmic matroid intersection coloring. Given $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color classes, where each color class is independent in all matroids. It is known that $2\chi_{\max}$ colors suffice to color the intersection of two matroids, $(2k-1)\chi_{\max}$ colors suffice for general $k$, where $\chi_{\max}$ is the maximum chromatic number of the individual matroids. However, these results are non-constructive, leveraging techniques such as topological Hall's theorem and Sperner's Lemma. We provide the first polynomial-time algorithms to color two or more general matroids where the approximation ratio depends only on $k$ and, in particular, is independent of $n$. For two matroids, we constructively match the $2\chi_{\max}$ existential bound, yielding a 2-approximation for the Matroid Intersection Coloring problem. For $k$ matroids we achieve a $(k^2-k)\chi_{\max}$ coloring, which is the first $O(1)$-approximation for constant $k$. Our approach introduces a novel matroidal structure we call a \emph{flexible decomposition}. We use this to formally reduce general matroid intersection coloring to graph coloring while avoiding the limitations of partition reduction techniques, and without relying on non-constructive topological machinery. Furthermore, we give a \emph{fully polynomial randomized approximation scheme} (FPRAS) for coloring the intersection of two matroids when $\chi_{\max}$ is large. This yields the first polynomial-time constructive algorithm for an asymptotic variant of Rota's Basis Conjecture. This constructivizes Montgomery and Sauermann's recent asymptotic breakthrough and generalizes it to arbitrary matroids.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2604.03735 — 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-11-01T02:15:28.298Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).