Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2411.06771 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912113485676544 |
|---|---|
| author | Garamvölgyi, Dániel Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Yamaguchi, Yutaro |
| author_facet | Garamvölgyi, Dániel Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Yamaguchi, Yutaro |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06771 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards the Proximity Conjecture on Group-Labeled Matroids Garamvölgyi, Dániel Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Yamaguchi, Yutaro Combinatorics 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. |
| title | Towards the Proximity Conjecture on Group-Labeled Matroids |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.06771 |