Towards the Proximity Conjecture on Group-Labeled Matroids
Abstract
Consider a matroid whose ground set is equipped with a labeling to an abelian group. A basis of is called -avoiding if the sum of the labels of its elements is not in a forbidden label set . Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an -avoiding basis exists, then any basis can be transformed into an -avoiding basis by exchanging at most elements. This proximity conjecture is known to hold for certain specific groups; in the case where ; 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 . 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.
Keywords and phrases:
sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelingsCategory:
Track A: Algorithms, Complexity and GamesFunding:
Ryuhei Mizutani: Supported by JSPS KAKENHI Grant Number JP23KJ0379 and JST SPRING Grant Number JPMJSP2108.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Mathematics of computing Matroids and greedoidsSupplementary Material:
Software (Source Code): https://github.com/taiheioki/sibo [16]archived at

Acknowledgements:
The authors thank anonymous referees for careful reading. The authors are grateful to the organizers of the 16th Emléktábla Workshop, where the collaboration of the authors started. The authors thank Kristóf Bérczi, Siyue Liu, and Chao Xu for several helpful discussions.Funding:
This research has been implemented with the support provided by the Lendület Programme of the Hungarian Academy of Sciences – grant number LP2021-1/2021.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Let be a finite ground set and let be a labeling from to an abelian group . A group-label constraint requires for a solution to satisfy , where is a prescribed set of forbidden labels. Such a solution is called -avoiding. An -avoiding is also called zero in the case when (i.e., ), and non-zero in the case when (i.e., ). Several constraints in combinatorial optimization, such as parity, congruency, and exact-weight constraints, are representable as group-label constraints by letting be a cyclic group or the integers , and be the complement of a singleton. These constraints have been studied for many classical combinatorial optimization problems, including matching [40, 36, 1, 14, 25], arborescence[2], submodular function minimization [17, 37], minimum cut [38], and independent sets or bases in a matroid [6, 12, 43]. Also, the non-zero and -avoiding constraints have been particularly well-studied for path and cycle problems on graphs [9, 8, 23, 27, 29, 42, 49, 50, 47].
In this paper, we study group-label constraints on matroid bases. This line of research was initiated by Liu and Xu [32], who addressed the problem of finding a zero basis. Hörsch, Imolay, Mizutani, Oki, and Schwarcz [20] considered non-zero bases, and more generally, -avoiding bases, posing the following conjecture.
Conjecture 1.1 (Proximity Conjecture [20]).
Let be a matroid, a labeling from the ground set of to an abelian group , and a finite collection of forbidden labels. Then, for any basis of , there exists an -avoiding basis of such that , provided that at least one -avoiding basis exists.
It is clear that ˜1.1 implies an algorithm for finding an -avoiding basis using independence oracle queries, where is the rank of and . Note that this bound is meaningful only when since the naïve brute-force search runs in oracle queries. Another consequence of ˜1.1 is that the number of -avoiding bases is at least , where is the basis family of , provided that at least one -avoiding basis exists.
˜1.1 is known to hold if (i) , (ii) is an ordered group, (iii) has prime order, (iv) and is a cyclic group with the order being a prime power or the product of two primes, or (v) is strongly base orderable (SBO). The claim for essentially follows from Rieder’s characterization [43] of basis lattices, and a simpler proof can be found in [20]. The proof for in [20] first reduces the problem to 6-element, rank-3 matroids and then shows the claim for them, treating one special matroid separately. Case (ii) was also proven in [20], where an ordered group is a group equipped with a total order consistent with the group operation, such as the integers and the reals .
˜1.1 for (iii) and (iv) was shown by Liu and Xu [32]. They showed (iii) with using an additive combinatorics result by Schrijver and Seymour [45] (which is ˜1.2 below for prime-order cyclic groups), and it immediately extends to general . For (iv), Liu and Xu observed more generally that ˜1.1 for finite with holds if the following long-standing conjecture by Schrijver and Seymour [45] is met for every subgroup of .
Conjecture 1.2 (Schrijver and Seymour [45]; see also [11]).
Let be a matroid with ground set , basis family , and rank function . Let be a labeling to an abelian group and the stabilizer subgroup of . Then,
Schrijver and Seymour [45] showed ˜1.2 for prime-order cyclic groups, and DeVos, Goddyn, and Mohar [11] proved it for the cases when is obtained from a uniform matroid by adding parallel elements and when is one of the groups in (iv).
Case (v) was shown in [32] for and in [20] for general . SBO matroids are a class of matroids that admit a certain basis exchange property and includes gammoids (so in particular, uniform, partition, laminar, and transversal matroids); see, e.g., [44, Section 42.6c]. As mentioned in the full version [21] of [20], the same proof works if we only assume a weaker property called subsequence-interchangeable base orderability (cf. Lemma 2.4). Following Baumgart [3], we say that a rank- matroid is subsequence-interchangeably base orderable (SIBO) if every pair of bases and admits orderings of and of such that is a basis for any pair with . For each pair of bases, we call such a pair of orderings an SI-ordering. Baumgart [3] posed the following conjecture.
Conjecture 1.3 (Baumgart [3]).
Every graphic matroid is SIBO.
By case (v) above, ˜1.3 would imply ˜1.1 for graphic matroids. Let us note that ˜1.3 is a strengthening of the graphic matroid case of the following celebrated conjecture.
Conjecture 1.4 (Gabow [15], see also [48, 10]).
Let and be bases of a rank- matroid . Then, there are orderings of and of such that and are bases for any .
In contrast to ˜1.3, ˜1.4 is known to hold for graphic matroids [48, 26, 10], regular matroids [4], and sparse paving matroids [5], which are the focus of this paper. A rank- matroid is paving if every circuit is of size either or , and is sparse paving if it and its dual are both paving. It is believed that asymptotically almost all matroids are sparse paving, formally stated as follows.
Conjecture 1.5 (Mayhew, Newman, Welsh, and Whittle [34]).
Let and be the families of all matroids and sparse paving matroids, respectively, on an unlabeled -element ground set. Similarly, let and be their counterparts on a labeled -element ground set. Then,
holds.
Our contributions.
Our first main result is a proof of ˜1.1 for sparse paving matroids. Together with ˜1.5, it would imply that ˜1.1 holds in an asymptotic sense. In addition, sparse paving matroids are significant in matroid theory as they have been used in hardness proofs for several algorithmic problems [12, 21, 24, 33] as well as counterexamples of conjectures. In fact, sparse paving matroids were used in [20] to disprove a strengthening of ˜1.1 for posed in the initial preprint version [31] of [32]. Given these contexts, our positive result for sparse paving matroids provides further evidence supporting ˜1.1.
We also show ˜1.1 for using a computer-aided proof. First, we use an observation from [21] (see Lemma 2.3) to reduce to the case of matroids on at most 10 elements having rank at most 5. By checking all such matroids using a SAT solver, it turns out that all of them are SIBO, except for a single matroid called . We complete the proof by showing ˜1.1 for separately. For completeness, we also provide an elementary proof that is not SIBO. This is noteworthy, as it serves as the first example of a non-SIBO matroid and shows that ˜1.3 does not extend to regular matroids.
As the second main thread of the paper, we consider an analog of ˜1.1 for multiple group labelings. In this setting, given labelings , where each is a map from to an abelian group , and forbidden labels , we are to find a basis such that for all . Questions with similar constraints have also been studied for paths and cycles in graphs [22, 19, 18, 7]. Note that the case corresponds to the single -avoiding constraint with , and the more general constraints with reduce to this setting with constraints . We pose the following conjecture.
Conjecture 1.6 (Multi-Labeled Proximity Conjecture).
There is a computable function such that for each , matroid with ground set , group labelings , group elements for , and basis of , there exists a basis of with for and , provided that at least one such basis exists.
Note that ˜1.6 leads to a polynomial-time solvability for finding a basis satisfying group-label constraints for any fixed . As a lower bound, we show using uniform matroids that , if exists, must be at least . ˜1.1 for implies that this is tight if . For , we show that is tight. We further show that suffices for SIBO matroids. We combine an extension of this result with a result of [20] (Theorem 5.6) to show the existence of such a function for matroids representable over a fixed, finite field. Finally, we prove an analogous result for sparse paving matroids using a similar method, but relying on a new structural observation on sparse paving matroids instead of Theorem 5.6.
Related work.
Eisenbrand, Rohwedder, and Węgrzycki [13] showed a proximity result on basis pairs of integer-labeled matroids. For a matroid labeled with for a positive integer , this result implies that if there exists a zero basis, then for any basis , there exists a zero basis such that . This bound is weaker than the bound implied by ˜1.1. Their result also implies a bound for a matroid labeled with a finite abelian group . The paper [13] additionally provided an FPT algorithm for finding a zero basis of a matroid labeled with a finite abelian group when parameterized by group size.
Organization.
The rest of this paper is organized as follows. Section 2 describes preliminaries. Sections 3 and 4 prove ˜1.1 for sparse paving matroids and the case when , respectively. Section 5 gives proximity results in the setting of multiple labelings. Finally, in Section 6, we conclude the paper with several open questions.
2 Preliminaries
For a nonnegative integer and a set , let and . For a set , , and , we abbreviate as and as . All groups are implicitly assumed to be abelian. We use the additive notation for the group operation. Let be the cyclic group of order . For a prime power , let be the finite field of size . For a function and subset , we use the notation . (Recall that if is labeling to a group , then .)
We refer the readers to [39] for basic concepts and terminology in matroid theory. A matroid consists of a finite ground set and a nonempty set family such that for any and , there exists such that . Every element in is called a basis (or a base). The rank of is the size of any basis of . The dual of is a matroid on the same ground set defined by . For , the restriction of to , denoted by , is a matroid on with , where . Also, the contraction of by is a matroid . A matroid is a minor of if for some with . Two matroids and are isomorphic if there exists a bijection such that .
A matroid of rank is called uniform if ; it is denoted by up to isomorphism, where . A matroid is called -representable if for some matrix over a field , corresponds to the set of columns of and consists of the subsets of columns of each of which forms a basis of the vector space spanned by the columns of . We will use the following characterization of sparse paving matroids.
Proposition 2.1 (see [5]).
A matroid of rank is sparse paving if and only if there exists a collection of subsets of such that for each , if , and .
Since the class of sparse paving matroids is closed under taking restrictions and duals, we also have the following proposition.
Proposition 2.2.
The class of sparse paving matroids is minor-closed.
In an indirect approach to ˜1.1, the following lemma is useful. It is similar to [32, Corollary 4.4] and is obtained from [21, Lemmas 5.35 and 5.36].
Lemma 2.3 (see [21]).
Let be a matroid, a group labeling, and a finite set of forbidden labels. Assume that is a counterexample to ˜1.1, i.e., has an -avoiding basis and it has a basis with for any -avoiding basis . Then, there exists a minor of having rank , a labeling , a set of labels with , and a basis of such that is the only -avoiding basis of and is a basis.
The following observation was essentially noted in [21, Remark 5.16]; we include a proof for completeness.
Lemma 2.4 (see [21]).
Let be a finite set, a group labeling, a finite collection of labels, and and disjoint subsets of , where . If is -avoiding, then there exists a pair with such that is -avoiding. Furthermore, if for every , then there exists a pair with such that .
Proof.
If there exists such that , then is indeed a desired pair. Otherwise, as , there exists a pair by the pigeonhole principle such that and . We then have , which means that the pair is a desired one.
3 Proximity Theorem for Sparse Paving Matroids
In this section, we prove the following theorem.
Theorem 3.1.
˜1.1 is true when is a sparse paving matroid.
Proof.
Suppose, to the contrary, that ˜1.1 does not hold for a sparse paving matroid on the ground set , a labeling , and a forbidden label set . Then, as minors of sparse paving matroids are sparse paving by Proposition 2.2, we may assume by Lemma 2.3 that has rank , it contains exactly one -avoiding basis , and is also a basis (with ). Clearly, .
We first consider the case when . Suppose that is rainbow, i.e., no two elements in have the same label. Fix an element such that is still rainbow, and consider the sets for . Then, by Proposition 2.1, at least of these sets are bases. Since is rainbow, these bases and , each of which is obtained by adding an element of to , have distinct labels, thus at least one of these bases or is -avoiding. This contradicts that is the only -avoiding basis.
Next, suppose that is not rainbow. As there are elements of different labels, we can take a set with and an element such that is rainbow. We consider sets for in addition to itself. Then, by Proposition 2.1, at least of these sets are bases, and none of them is as they are all rainbow. Since is rainbow, these bases have distinct labels, thus at least one of them is -avoiding. This contradicts that is the only -avoiding basis.
From now on, let us assume . To complete the proof, we first prove three lemmas. For each , we call the label class of .
Lemma 3.2.
For any with , , and , one of the following holds:
-
1.
is the union of label classes, or
-
2.
, is a label class, and is the union of label classes.
Proof.
Assume that is not the union of label classes, i.e., there exists a pair of and with . Now is not a basis as is the only -avoiding basis. Since is sparse paving, is a basis and , which implies that . This holds for any pair and the pair is indeed unique as , completing the proof.
Lemma 3.3.
One of the following holds:
-
1.
is the union of label classes, or
-
2.
there exists such that and is the union of label classes.
Proof.
Assume that is not the union of label classes, i.e., there exists a pair of and with . Let . Then, is not a basis as and is the only -avoiding basis. Thus, Lemma 3.2(2) implies statement 2 here.
As in Lemma 2.4, under fixed orderings of and of , for each pair with , we define .
Lemma 3.4.
Let be a set and be a coloring. If , then there are orderings of and of such that is not the union of color classes for any pair with and .
Proof.
We construct the desired orderings by fixing and for each in this order so that there exists with or with . We first show that this is sufficient for our purpose, and then show that this is indeed possible.
Suppose to the contrary that for orderings satisfying the above condition, there exists a pair such that is the union of color classes. If , then there exists such that or . Since is the union of color classes, or must be included in or disjoint from , but by definition, a contradiction. Otherwise, and hence . Then, similarly, there exists such that or , but , a contradiction. Thus, the above construction is sufficient.
Now we show that we can fix and for each so that the above condition is satisfied. The proof is done by induction on . The base case when is trivial.
Suppose that . If , then by the pigeonhole principle (as ), there exists an element such that for any or such that for any . By symmetry, we may assume that for any , and then by the pigeonhole principle (as and ), there exist two distinct elements with . In this case, by setting and , the condition for is satisfied as and , and that for can be satisfied by applying the induction hypothesis to the remaining part , , and , where is the restriction of and satisfies .
The remaining case is when . Then, since , we have two distinct elements with , and by setting and arbitrarily choosing , the condition for is satisfied as with and that for can be satisfied by applying the induction hypothesis as well. Thus, we complete the proof.
We turn back to the proof of Theorem 3.1. We discuss the two cases in Lemma 3.3 separately.
(1) Suppose that is the union of label classes; this implies . Let us regard as a coloring and apply Lemma 3.4 to get orderings of and of . We then apply the first statement of Lemma 2.4 to these orderings to get a pair with such that is -avoiding. We have since . Then, is -avoiding but is not the union of label classes, thus is a label class by Lemma 3.2. This is a contradiction since is the union of label classes.
(2) Otherwise, there exists such that and for some and , and is the union of label classes. We define a coloring by for and . Now we have since is also the union of label classes. Hence we can apply Lemma 3.4 to and we get orderings of and of , and then by Lemma 2.4, we obtain a pair with such that is -avoiding but is not the union of color classes. We have since . We apply Lemma 3.2 to . (1) is impossible because the color classes refine the label classes. In case of (2), by the assumption of Lemma 3.3(2), , implying that is the union of color classes, a contradiction.
4 Proximity Theorem for at Most 4 Forbidden Labels
We first observe that ˜1.3 does not hold for regular matroids: a pair of disjoint bases of the matroid does not have an SI-ordering. is the matroid appearing in Seymour’s fundamental decomposition theorem of regular matroids [46], and it can be defined as the even-cycle matroid of the complete graph . The ground set of this matroid is the edge set of and its bases are the sets of five edges forming a subgraph containing exactly one odd cycle and no even cycle. It is not difficult to check the following statement; see also the proof of [4, Proposition 5.5].
Lemma 4.1.
Consider as the even-cycle matroid of the complete graph on vertex set . Then, for any two disjoint bases and of , there exists an automorphism of mapping and to the 5-cycles and of , respectively, where indices are meant in a cyclic order (e.g., ).
We show the following using Lemma 4.1.
Theorem 4.2.
is not SIBO.
Proof.
We consider as the even-cycle matroid of the complete graph on vertex set . Let and be disjoint bases of ; we show that and do not have an SI-ordering. For this, suppose to the contrary that there exists an SI-ordering of and of . By Lemma 4.1, we may assume and .
We may assume by symmetry that . Using that is a symmetric exchange between and , it follows that . By symmetry, we may assume that . As is a symmetric exchange between and , it follows that
If , then contains the 4-cycle , a contradiction. We conclude that .
Using that and is a symmetric exchange between and , it follows that
It is clear that as . If , then , which contains the 4-cycle , a contradiction. Otherwise, , and then , which contains the 4-cycle , a contradiction. This finishes the proof.
Using a computer program, we verified that this is the only example of a basis pair not having an SI-ordering up to rank 5.
Proposition 4.3.
Let be a matroid of rank at most 5, and a basis pair of not having an SI-ordering. Then, and are disjoint and the restriction is isomorphic to .
Giving a human-readable proof of Proposition 4.3 seems difficult, as even ˜1.4 was verified only up to rank 4 [30]. (Note that is known to satisfy ˜1.4 [4], thus Proposition 4.3 implies that the conjecture holds up to rank 5.) Up to rank 4, one can check the validity of Proposition 4.3 by using one of the existing databases of small matroids [35]. As the list (or number) of rank-5 matroids on 10 elements is unknown and expected to be very large [35], we used a different approach: we encoded a basis pair of a matroid of given rank not having an SI-ordering as a Boolean formula, with variables encoding which subsets are bases, and decided the satisfiability with a SAT solver; see Appendix A for details. We note that a similar but much more sophisticated approach has been used to study Rota’s basis conjecture [28].
We are ready to prove the following theorem.
Theorem 4.4.
˜1.1 is true when .
Proof.
Suppose otherwise and let be a counterexample. We may assume by Lemma 2.3 that has rank , it contains exactly one -avoiding basis , and is also a basis (with ).
If the basis pair has an SI-ordering, then we obtain by Lemma 2.4 an -avoiding basis other than , a contradiction. Otherwise, as has rank , Proposition 4.3 implies that is isomorphic to , which we regard as the even-cycle matroid of the complete graph on the vertex set . By Lemma 4.1, we may assume that and . Fix and define orderings
of and , respectively (see Figure 1). Then, it can be checked that for indices , the set is a basis if and only if . In particular, is a basis for each , and hence , as is the only -avoiding basis. Thus, by Lemma 2.4, we have for some , which must be as is the only -avoiding basis, again. That is, . Since this holds for every , we get that
which contradicts that and .
5 Proximity for Multiple Labelings
In this section, we verify ˜1.6 for various classes of matroids. We begin with an example showing that the function in ˜1.6 must satisfy for each , even for uniform matroids.
Example 5.1.
Let be a positive integer. Let , and let denote the uniform matroid of rank on some ground set of size . We show that there exist group labelings for , and a basis of such that is the only basis of satisfying for all .
Let us fix a set of size . We set , and for . Finally, we define the group labelings by
Note that for all . It is easy to see that for all , where . Hence, we only need to show that for each , any set obtained by exchanging elements of into is zero in at least one of the labelings.
Let be the largest for which divides . Note that . Moreover, as , we have . Now if , then
On the other hand, if , then , and in this case
Next, we show the existence of as in ˜1.6 for several matroid classes. The proofs will be based on the following lemma.
Lemma 5.2.
Let be group labelings on a finite set and group elements for . Let be a subset with for all . Let and be pairwise disjoint nonempty subsets. For , let
If , there are indices such that for all .
Proof.
Let denote the smallest integer such that whenever are labelings, group elements, and are subsets as in the theorem and holds, then there exist indices such that for all . If no such integer exists, then define to be infinite. Observe that .
Claim 5.3.
holds for .
Proof.
Assume for contradiction that , that is, there exist labelings , group elements , and subsets as required with such that there exist no indices such that for all . In particular, for each , there exists such that . Since , this implies that there exists with . We may assume that , and let be indices with . Define and for , and for . Observe that and hold for ; thus
Using the definition of , we get that there exist indices such that for all . By defining and , we get and
This proves that for all , a contradiction.
˜5.3 implies that and . We improve the latter bound by one.
Claim 5.4.
.
Proof.
Assume for contradiction that , and let be labelings, group elements, and subsets as in the proof of ˜5.3 such that there exist no indices such that for all . We have that holds for all , as otherwise we get a contradiction using the proof of ˜5.3 and . This implies that
(1) |
By symmetry, we also get
(2) |
We may assume that . Let denote the unique indices such that and . If , then
thus , a contradiction. We conclude that . Let be the unique index with . Then, from (1) and (2), we get that and . Then,
thus . This contradicts (2) and finishes the proof.
Using induction we obtain that . Indeed, it holds for by ˜5.4, and using ˜5.3 and induction we get
The statement of the lemma follows by using that .
Theorem 5.5.
Let be a basis of a matroid on ground set , and group labelings and group elements for . Assume that has at least one basis with for all .
-
1.
If is SIBO, then it has a basis with for all and .
-
2.
If , then has a basis with , , and .
Proof.
Let be a basis of such that for all and is minimum. Assume that . If is SIBO, then there exist orderings of and of such that is a basis for . Then, using Lemma 5.2 with and for , we get a contradiction to and being closest. This proves 1. For proving 2, assume that and is not SIBO. Observe that in this case . Let be a basis of with and . Then, has rank 4 and hence is SIBO by Proposition 4.3. Thus, there exist orderings of and of such that is a basis for . This contradicts and being closest by Lemma 5.2.
Example 5.1 shows that for , the bound 3 in Theorem 5.52 is tight. Observe that this differs from the case where the tight bound is 2 [20].
Finally, we derive the validity of ˜1.6 for matroids representable over a fixed finite field and sparse paving matroids. For positive integers and , we define a matroid to be weakly -base orderable if for every ordered basis pair of with , there exist pairwise disjoint nonempty subsets and such that is a basis for each . The following was shown in [20].
Theorem 5.6 (Hörsch, Imolay, Mizutani, Oki, Schwarcz [20]).
There is a computable function such that for every prime power , every -representable matroid is weakly -orderable for any .
Following the terminology of [20], for a basis of a matroid , we say that a minor of is a -minor if for some with . In this case, . We show the following result, which is related to results of [41].
Theorem 5.7.
Let be an integer and a sparse paving matroid of rank . If , then for each basis , has a -minor isomorphic to .
Proof.
We prove this by induction on . The statements clearly hold for , so assume that it holds for . Let , , and . Then, by Proposition 2.1, holds for all with . Since , by induction there exist with such that is isomorphic to . Note that has rank , thus .
Let and . Observe that for each . This together with Proposition 2.1 implies that for each set , there exists at most one with , implying . Since for and , there exists . Let . We claim that is isomorphic to , i.e., for each subset with , is a basis of . Indeed, if , then being a basis follows from being isomorphic to . If , then , thus follows from . This shows that is indeed isomorphic to .
Let and . Observe that for each . Then, by Proposition 2.1, for each set , there exists at most one with , implying . Since for and , there exists with . Let . We claim that is isomorphic to , i.e., for each subset with , is a basis of . Indeed, if , then being a basis follows from being isomorphic to . If , then , thus follows from . Therefore, is indeed isomorphic to , finishing the proof.
Remark 5.8.
We note that Pendavingh and van der Pol [41] showed that for a fixed , asymptotically almost all matroids contain as a minor. If is a sparse paving matroid, then a counting argument found in [41, Lemma 4.7] combined with the observation implies that if and hold, then contains as a minor. It is not clear whether a similar argument can be used to give a simple proof of the existence of such a -minor for any basis as in Theorem 5.7.
Corollary 5.9.
Every sparse paving matroid is -weakly base orderable for any .
Proof.
Let and be bases of a sparse paving matroid with , and let . Then, is a sparse paving matroid having rank and , thus Theorem 5.7 implies that has a -minor isomorphic to , that is, there exist with such that is isomorphic to . Observe that has size as it is a basis of , and so does as . Let and . Then, is a basis for each , showing that is -weakly base orderable.
Remark 5.10.
Following the terminology of [20], the proof of Corollary 5.9 also shows that sparse paving matroids are elementarily -weakly base orderable for , that is, the sets and in the definition of -weak base orderability can be chosen to be singletons. Moreover, a proof similar to that of Theorem 5.7 shows that sparse paving matroids are even elementarily -weakly base orderable for .
Theorem 5.6, Corollary 5.9, and Lemma 5.2 immediately verify ˜1.6 for matroids representable over a fixed, finite field and sparse paving matroids.
Corollary 5.11.
Let be the class of (1) -representable matroids for a fixed prime power or (2) sparse paving matroids. Then, there is a computable function such that if , are group labelings, are group elements for , and is a basis of , then has a basis with for all and , provided that has at least one basis with for all .
Proof.
(1) Suppose that is -representable. Let be the function provided by Theorem 5.6, and define . Let be a basis with for all such that is minimum. If , then by the definition of , for , there exist pairwise disjoint nonempty subsets and such that is a basis for each . Then, we get a contradiction by Lemma 5.2 to and being closest.
(2) By Corollary 5.9 sparse paving matroids are -weakly base orderable for each . Therefore, as with Case (1), we get the desired function .
6 Conclusion
In this paper, we have proven ˜1.1 for the case where the matroid is sparse paving or , and settled ˜1.6 for and some classes of matroids. We conclude this paper by making a new conjecture and a question.
Conjecture 6.1.
Every sparse paving matroid is SIBO.
We have checked the validity of the conjecture up to rank 6 using a SAT solver. If true, ˜6.1 would give another proof of Theorem 3.1. Unfortunately, the proof [5] of ˜1.4 for sparse paving matroids does not seem to generalize to this conjecture.
We also pose the following refinement of ˜1.6 in light of our lower bound on . We state it in the form of a question rather than a conjecture as we do not expect it to hold for general matroids, whereas it is more likely to hold for uniform, SBO, and SIBO matroids.
Question 6.2.
Let be a matroid with the ground set , a group labeling, and a group element for . Then, if at least one such basis exists, for any basis of , is there a basis of with for and ?
References
- [1] Stephan Artmann, Robert Weismantel, and Rico Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC ’17), pages 1206–1219, 2017. doi:10.1145/3055399.3055473.
- [2] Francisco Barahona and William R. Pulleyblank. Exact arborescences, matchings and cycles. Discrete Applied Mathematics, 16(2):91–99, 1987. doi:10.1016/0166-218x(87)90067-9.
- [3] Matthias Baumgart. Ranking and ordering problems of spanning trees. PhD thesis, Technische Universität München, Munich, 2009.
- [4] Kristóf Bérczi, Bence Mátravölgyi, and Tamás Schwarcz. Reconfiguration of basis pairs in regular matroids. arXiv preprint, 2023. doi:10.48550/arXiv.2311.07130.
- [5] Joseph E. Bonin. Basis-exchange properties of sparse paving matroids. Advances in Applied Mathematics, 50(1):6–15, 2013. doi:10.1016/j.aam.2011.05.006.
- [6] Paolo M. Camerini, Giulia Galbiati, and Francesco Maffioli. Random pseudo-polynomial algorithms for exact matroid problems. Journal of Algorithms, 13(2):258–273, 1992. doi:10.1016/0196-6774(92)90018-8.
- [7] Vera Chekan, Colin Geniet, Meike Hatzel, Michał Pilipczuk, Marek Sokołowski, Michał T. Seweryn, and Marcin Witkowski. Half-integral Erdős–Pósa property for non-null - paths. arXiv preprint, 2024. arXiv:2408.16344.
- [8] Maria Chudnovsky, William H. Cunningham, and Jim Geelen. An algorithm for packing non-zero -paths in group-labelled graphs. Combinatorica, 28:145–161, 2008. doi:10.1007/s00493-008-2157-8.
- [9] Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis Goddyn, Michael Lohman, and Paul Seymour. Packing non-zero -paths in group-labelled graphs. Combinatorica, 26(5):521–532, 2006. doi:10.1007/s00493-006-0030-1.
- [10] Raul Cordovil and M. Leonor Moreira. Bases-cobases graphs and polytopes of matroids. Combinatorica, 13(2):157–165, 1993. doi:10.1007/bf01303201.
- [11] Matt DeVos, Luis Goddyn, and Bojan Mohar. A generalization of Kneser’s Addition Theorem. Advances in Mathematics, 220(5):1531–1548, 2009. doi:10.1016/j.aim.2008.11.003.
- [12] Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Lower bounds for matroid optimization problems with a linear constraint. In Proceedings of the 51th International Colloquium on Automata, Languages, and Programming (ICALP ’24), pages 56:1–56:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.56.
- [13] Friedrich Eisenbrand, Lars Rohwedder, and Karol Węgrzycki. Sensitivity, proximity and FPT algorithms for exact matroid problems. In Proceedings of the 65th Annual Symposium on Foundations of Computer Science (FOCS ’24), pages 1610–1620, 2024. doi:10.1109/FOCS61266.2024.00100.
- [14] Nicolas El Maalouly, Raphael Steiner, and Lasse Wulf. Exact matching: Correct parity and FPT parameterized by independence number. In 34th International Symposium on Algorithms and Computation (ISAAC 2023), pages 28:1–28:18, 2023. doi:10.4230/LIPICS.ISAAC.2023.28.
- [15] Harold Gabow. Decomposing symmetric exchanges in matroid bases. Mathematical Programming, 10(1):271–276, 1976. doi:10.1007/bf01580672.
- [16] Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi. Code for finding a non-SIBO matroid. Software, swhId: swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1 (visited on 2025-06-13). URL: https://github.com/taiheioki/sibo, doi:10.4230/artifacts.23553.
- [17] Michel X. Goemans and V.S. Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15(4):499–513, 1995. doi:10.1007/BF01192523.
- [18] J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, and Sang-il Oum. A unified half-integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups. Journal of the London Mathematical Society, 109(1):e12858, 2024. doi:10.1112/jlms.12858.
- [19] J. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, and Youngho Yoo. A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups. arXiv preprint, 2022. arXiv:2209.09488.
- [20] Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on group-labeled matroid bases. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP ’24), pages 86:1–86:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.86.
- [21] Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on group-labeled matroid bases. arXiv preprint, 2024. doi:10.48550/arXiv.2402.16259.
- [22] Tony Huynh, Felix Joos, and Paul Wollan. A unified Erdős–Pósa theorem for constrained cycles. Combinatorica, 39(1):91–133, 2019. doi:10.1007/s00493-017-3683-z.
- [23] Yoichi Iwata and Yutaro Yamaguchi. Finding a shortest non-zero path in group-labeled graphs. Combinatorica, 42(S2):1253–1282, 2022. doi:10.1007/s00493-021-4736-x.
- [24] Per M. Jensen and Bernhard Korte. Complexity of matroid property algorithms. SIAM Journal on Computing, 11(1):184–190, 1982. doi:10.1137/0211014.
- [25] Xinrui Jia, Ola Svensson, and Weiqiang Yuan. The exact bipartite matching polytope has exponential extension complexity. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 1635–1654. SIAM, 2023. doi:10.1137/1.9781611977554.ch61.
- [26] Yoji Kajitani, Shuichi Ueno, and Hiroshi Miyano. Ordering of the elements of a matroid such that its consecutive elements are independent. Discrete Mathematics, 72(1–3):187–194, 1988. doi:10.1016/0012-365x(88)90209-9.
- [27] Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi. Finding a path with two labels forbidden in group-labeled graphs. Journal of Combinatorial Theory, Series B, 143:65–122, 2020. doi:10.1016/j.jctb.2019.12.001.
- [28] Markus Kirchweger, Manfred Scheucher, and Stefan Szeider. A SAT attack on Rota’s Basis Conjecture. In 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), pages 4:1–4:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPICS.SAT.2022.4.
- [29] Yusuke Kobayashi and Sho Toyooka. Finding a shortest non-zero path in group-labeled graphs via permanent computation. Algorithmica, 77(4):1128–1142, 2017. doi:10.1007/s00453-016-0142-y.
- [30] Daniel Kotlar and Ran Ziv. On serial symmetric exchanges of matroid bases. Journal of Graph Theory, 73(3):296–304, 2013. doi:10.1002/jgt.21675.
- [31] Siyue Liu and Chao Xu. On the congruency-constrained matroid base. arXiv preprint, 2023. arXiv:2311.11737v1.
- [32] Siyue Liu and Chao Xu. On the congruency-constrained matroid base. In Proceedings of the 25th Integer Programming and Combinatorial Optimization (IPCO ’24), pages 280–293, 2024. doi:10.1007/978-3-031-59835-7_21.
- [33] László Lovász. The matroid matching problem. In László Lovász and Vera T. Sós, editors, Algebraic methods in graph theory, volume 25 of Colloquia Mathematica Societatis János Bolyai, pages 495–517. North-Holland, Amsterdam, 1981.
- [34] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle. On the asymptotic proportion of connected matroids. European Journal of Combinatorics, 32:882–890, 2011. doi:10.1016/j.ejc.2011.01.016.
- [35] Dillon Mayhew and Gordon F. Royle. Matroids with nine elements. Journal of Combinatorial Theory, Series B, 98:415–431, 2008. doi:10.1016/j.jctb.2007.07.005.
- [36] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105–113, 1987. doi:10.1007/bf02579206.
- [37] Martin Nägele, Benny Sudakov, and Rico Zenklusen. Submodular minimization under congruency constraints. Combinatorica, 39(6):1351–1386, 2019. doi:10.1007/s00493-019-3900-1.
- [38] Martin Nägele and Rico Zenklusen. A new contraction technique with applications to congruency-constrained cuts. Mathematical Programming, 183(1):455–481, 2020. doi:10.1007/s10107-020-01498-x.
- [39] James Oxley. Matroid Theory. Oxford University Press, Oxford, second edition, 2011. doi:10.1093/acprof:oso/9780198566946.001.0001.
- [40] Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM, 29(2):285–309, 1982. doi:10.1145/322307.322309.
- [41] Rudi Pendavingh and Jorn van der Pol. On the number of bases of almost all matroids. Combinatorica, 38(4):955–985, 2018. doi:10.1007/s00493-016-3594-4.
- [42] Bruce Reed. Mangoes and blueberries. Combinatorica, 2(19):267–296, 1999. doi:10.1007/s004930050056.
- [43] Jörg Rieder. The lattices of matroid bases and exact matroid bases. Archiv der Mathematik, 56:616–623, 1991. doi:10.1007/bf01246778.
- [44] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin, 2003.
- [45] Alexander Schrijver and Paul D. Seymour. Spanning trees of different weights. In William J. Cook and Paul D. Seymour, editors, Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 281–288. DIMACS/AMS, 1990. doi:10.1090/DIMACS/001/21.
- [46] Paul D. Seymour. Decomposition of regular matroids. Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980. doi:10.1016/0095-8956(80)90075-1.
- [47] Robin Thomas and Youngho Yoo. Packing cycles in undirected group-labelled graphs. Journal of Combinatorial Theory, Series B, 161:228–267, 2023. doi:10.1016/j.jctb.2023.02.011.
- [48] Doug Wiedemann. Cyclic base orders of matroids. Manuscript, 1984.
- [49] Paul Wollan. Packing non-zero -paths in an undirected model of group labeled graphs. Journal of Combinatorial Theory, Series B, 100(2):141–150, 2010. doi:10.1016/j.jctb.2009.05.003.
- [50] Paul Wollan. Packing cycles with modularity constraints. Combinatorica, 31(1):95–126, 2011. doi:10.1007/s00493-011-2551-5.
Appendix A CNF formulation of finding a non-SIBO matroid
In this section, we describe how we can reduce the problem of finding a -elements, rank-, non-SIBO matroid to SAT by describing a CNF (conjunctive normal form) formulation.
Let be the ground set. We prepare Boolean variables indexed by . We build a CNF such that forms the basis family of a matroid, and are bases, and has no SI-ordering by collecting the following clauses.
- Basis exchange property:
-
for every and ,
(3) - Fixed basis:
-
(4) - Fixed basis:
-
(5) - No SI-ordering:
-
for every permutation of and of ,
(6)
Note that if a non-disjoint basis pair of a matroid has no SI-ordering, then has no SI-ordering as well in . Thus, we can restrict our attention to the disjoint basis pair by verifying the unsatisfiability of the CNF from small .
Our Python script to solve the above SAT instance is available at https://github.com/taiheioki/sibo.