|
Consider a matroid $M$ whose ground set is equipped with a labeling to an abelian group. A basis of $M$ is called $F$-avoiding if the sum of the labels of its elements is not in a forbidden label set $F$. Hörsch, Imolay, Mizutani, Oki, and Schwarcz(2024) conjectured that if an $F$-avoiding basis exists, then any basis can be transformed into an $F$-avoiding basis by exchanging at most $|F|$ elements. This \emph{proximity conjecture} is known to hold for certain specific groups; in the case where $|F| \le 2$; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where $|F| \le 4$. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam{\'a}s and Yamaguchi, Yutaro}, |
| TITLE | = | {Towards the Proximity Conjecture on Group-Labeled Matroids}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2024}, |
| NUMBER | = | {TR-2024-06} |