2026-07-24T03:28:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23462 2025-10-02T12:55:51Z ddc:004 open_access

Towards the Proximity Conjecture on Group-Labeled Matroids Garamvölgyi, Dániel Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Yamaguchi, Yutaro sparse paving matroid subsequence-interchangeable base orderability congruency constraint multiple labelings 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| ≤ 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| ≤ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Garamvölgyi and Ryuhei Mizutani and Taihei Oki and Tamás Schwarcz and Yutaro Yamaguchi 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.85 urn:nbn:de:0030-drops-234628 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.85 eng https://creativecommons.org/licenses/by/4.0/legalcode