Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06771 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 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.