Abstract 1 Introduction 2 Preliminaries 3 Proximity Theorem for Sparse Paving Matroids 4 Proximity Theorem for at Most 4 Forbidden Labels 5 Proximity for Multiple Labelings 6 Conclusion References Appendix A CNF formulation of finding a non-SIBO matroid

Towards the Proximity Conjecture on Group-Labeled Matroids

Dániel Garamvölgyi MTA-ELTE Matroid Optimization Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Ryuhei Mizutani Faculty of Science and Technology, Keio University, Yokohama, Japan Taihei Oki ORCID Institute for Chemical Reaction Design and Discovery (ICReDD), Hokkaido University, Sapporo, Japan
Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
Tamás Schwarcz ORCID Department of Mathematics, London School of Economics and Political Science, UK Yutaro Yamaguchi Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University, Japan
Abstract

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.

Keywords and phrases:
sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelings
Category:
Track A: Algorithms, Complexity and Games
Funding:
Ryuhei Mizutani: Supported by JSPS KAKENHI Grant Number JP23KJ0379 and JST SPRING Grant Number JPMJSP2108.
Taihei Oki: Supported by JST ERATO Grant Number JPMJER1903, JST CREST Grant Number JPMJCR24Q2, JST FOREST Grant Number JPMJFR232L, JSPS KAKENHI Grant Numbers JP22K17853 and 24K21315, and Start-up Research Funds in ICReDD, Hokkaido University.
Tamás Schwarcz: Supported by EPSRC grant EP/X030989/1. Most of this work was done while this author was affiliated to the HUN-REN–ELTE Egerváry Research Group.
Yutaro Yamaguchi: Supported by JSPS KAKENHI Grant Numbers 20K19743, 20H00605, and 25H01114, by JST CRONOS Japan Grant Number JPMJCS24K2, and by Start-up Program in Graduate School of Information Science and Technology, Osaka University.
Copyright and License:
[Uncaptioned image] © Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Matroids and greedoids
Related Version:
Full Version: https://arxiv.org/abs/2411.06771
Supplementary Material:
Software  (Source Code): https://github.com/taiheioki/sibo [16]
  archived at Software Heritage Logo swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1
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 Puppis

1 Introduction

Let E be a finite ground set and let ψ:EΓ be a labeling from E to an abelian group Γ. A group-label constraint requires for a solution XE to satisfy ψ(X)eXψ(e)F, where FΓ is a prescribed set of forbidden labels. Such a solution X is called F-avoiding. An F-avoiding X is also called zero in the case when F=Γ{0} (i.e., ψ(X)=0), and non-zero in the case when F={0} (i.e., ψ(X)0). 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 m or the integers , and F 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 F-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, F-avoiding bases, posing the following conjecture.

Conjecture 1.1 (Proximity Conjecture [20]).

Let M be a matroid, ψ:EΓ a labeling from the ground set E of M to an abelian group Γ, and FΓ a finite collection of forbidden labels. Then, for any basis A of M, there exists an F-avoiding basis B of M such that |AB||F|, provided that at least one F-avoiding basis exists.

It is clear that ˜1.1 implies an algorithm for finding an F-avoiding basis using O((rn)|F|) independence oracle queries, where r is the rank of M and n|E|. Note that this bound is meaningful only when |F|<r since the naïve brute-force search runs in (nr)=O(nr) oracle queries. Another consequence of ˜1.1 is that the number of F-avoiding bases is at least ||/i=0|F|(ri)(nri), where is the basis family of M, provided that at least one F-avoiding basis exists.

˜1.1 is known to hold if (i) |F|2, (ii) Γ is an ordered group, (iii) Γ has prime order, (iv) |ΓF|=1 and Γ is a cyclic group with the order being a prime power or the product of two primes, or (v) M is strongly base orderable (SBO). The claim for |F|=1 essentially follows from Rieder’s characterization [43] of basis lattices, and a simpler proof can be found in [20]. The proof for |F|=2 in [20] first reduces the problem to 6-element, rank-3 matroids and then shows the claim for them, treating one special matroid M(K4) 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 |ΓF|=1 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 F. For (iv), Liu and Xu observed more generally that ˜1.1 for finite Γ with |ΓF|=1 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 M be a matroid with ground set E, basis family , and rank function ρ. Let ψ:EΓ be a labeling to an abelian group Γ and H{gΓ|g+ψ()=ψ()} the stabilizer subgroup of ψ(){ψ(B)|B}. Then,

|ψ()||H|(QΓ/Hρ(ψ1(Q))ρ(E)+1).

Schrijver and Seymour [45] showed ˜1.2 for prime-order cyclic groups, and DeVos, Goddyn, and Mohar [11] proved it for the cases when M 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 |ΓF|=1 and in [20] for general F. 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-r matroid is subsequence-interchangeably base orderable (SIBO) if every pair of bases A and B admits orderings a1,,ar of A and b1,,br of B such that (B{bi,,bj}){ai,,aj}={b1,,bi1,ai,,aj,bj+1,,br} is a basis for any pair (i,j) with 1ijr. 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 A and B be bases of a rank-r matroid M. Then, there are orderings a1,,ar of A and b1,,br of B such that {a1,,ai,bi+1,,br} and {b1,,bi,ai+1,,ar} are bases for any i=1,,r.

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-r matroid is paving if every circuit is of size either r or r+1, 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 u(n) and 𝒮u(n) be the families of all matroids and sparse paving matroids, respectively, on an unlabeled n-element ground set. Similarly, let l(n) and 𝒮l(n) be their counterparts on a labeled n-element ground set. Then,

limn|𝒮u(n)||u(n)|=limn|𝒮l(n)||l(n)|=1

holds.

Under ˜1.5, the result of [5] implies that ˜1.4 holds asymptotically.

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 |ΓF|=1 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 |F|4 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 R10. We complete the proof by showing ˜1.1 for R10 separately. For completeness, we also provide an elementary proof that R10 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 k labelings ψ1,,ψk, where each ψt is a map from E to an abelian group Γt, and k forbidden labels f1Γ1,,fkΓk, we are to find a basis B such that ψt(B)ft for all t{1,,k}. Questions with similar constraints have also been studied for paths and cycles in graphs [22, 19, 18, 7]. Note that the ψ1==ψk case corresponds to the single F-avoiding constraint with F={f1,,fk}, and the more general constraints ψ1(B)F1,,ψk(B)Fk with F1Γ1,,FkΓk reduce to this setting with t=1k|Ft| constraints ψt(B)f (t{1,,k},fFt). We pose the following conjecture.

Conjecture 1.6 (Multi-Labeled Proximity Conjecture).

There is a computable function d: such that for each k, matroid M with ground set E, group labelings ψt:EΓt, group elements ftΓt for t=1,,k, and basis A of M, there exists a basis B of M with ψt(B)ft for t=1,,k and |AB|d(k), provided that at least one such basis exists.

Note that ˜1.6 leads to a polynomial-time solvability for finding a basis satisfying k group-label constraints for any fixed k. As a lower bound, we show using uniform matroids that d(k), if exists, must be at least 2k1. ˜1.1 for |F|=1 implies that this is tight if k=1. For k=2, we show that 221=3 is tight. We further show that d(k)=(e1/2)k!1 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 d(k) 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 m for a positive integer m2, this result implies that if there exists a zero basis, then for any basis A, there exists a zero basis B such that |AB|=O(m5). This bound is weaker than the bound |AB|m1 implied by ˜1.1. Their result also implies a bound |AB|=|Γ|O(log|Γ|) 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.

Hörsch, Imolay, Mizutani, Oki, and Schwarcz [20] also posed a weighted variant of ˜1.1, which was settled for SBO matroids as well as the case when |F|=1 [20]. Extending the proofs of ˜1.1 in other cases to the weighted conjecture is left for future work.

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 |F|4, 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 k and a set S, let [k]{1,,k} and (Sk){XS||X|=k}. For a set S, xS, and yS, we abbreviate S{x} as S+x and S{y} as Sy. All groups are implicitly assumed to be abelian. We use the additive notation for the group operation. Let m be the cyclic group of order m. For a prime power q, let GF(q) be the finite field of size q. For a function c:ES and subset XE, we use the notation c[X]{c(e)|eX}. (Recall that if ψ:EΓ is labeling to a group Γ, then ψ(X)eXψ(e).)

We refer the readers to [39] for basic concepts and terminology in matroid theory. A matroid M consists of a finite ground set E(M) and a nonempty set family (M) such that for any B,B(M) and eBB, there exists fBB such that Be+f(M). Every element in (M) is called a basis (or a base). The rank of M is the size of any basis of M. The dual M of M is a matroid on the same ground set defined by (M)={E(M)B|B(M)}. For XE(M), the restriction of M to X, denoted by M|X, is a matroid on X with (M|X)={B(Xr)|BB(B(M))}, where rmaxB(M)|BX|. Also, the contraction of M by X is a matroid M/X(M|(E(M)X)). A matroid M is a minor of M if M=(M|X)/Y for some X,Y with YXE(M). Two matroids M1 and M2 are isomorphic if there exists a bijection σ:E(M1)E(M2) such that (M2)={{σ(e)|eB}|B(M1)}.

A matroid M of rank r is called uniform if (M)=(E(M)r); it is denoted by Ur,n up to isomorphism, where n=|E(M)|. A matroid M is called 𝔽-representable if for some matrix A over a field 𝔽, E(M) corresponds to the set of columns of A and (M) consists of the subsets of columns of A each of which forms a basis of the vector space spanned by the columns of A. We will use the following characterization of sparse paving matroids.

Proposition 2.1 (see [5]).

A matroid M of rank r is sparse paving if and only if there exists a collection ={H1,,Hk} of subsets of E(M) such that |Hi|=r for each i[k], |HiHj|r2 if ij, and (M)=(E(M)r).

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 M be a matroid, ψ:E(M)Γ a group labeling, and FΓ a finite set of forbidden labels. Assume that (M,ψ,F) is a counterexample to ˜1.1, i.e., M has an F-avoiding basis and it has a basis A with |AB||F|+1 for any F-avoiding basis B. Then, there exists a minor M of M having rank |F|+1, a labeling ψ:E(M)Γ, a set of labels FΓ with |F|=|F|, and a basis B of M such that B is the only F-avoiding basis of M and E(M)B 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 E be a finite set, ψ:EΓ a group labeling, FΓ a finite collection of labels, and A={a1,,ar} and B={b1,,br} disjoint subsets of E, where r=|F|+1. If B is F-avoiding, then there exists a pair (i,j) with 1ijr such that B^i,j(B{bi,,bj}){ai,,aj}={b1,,bi1,ai,,aj,bj+1,,br} is F-avoiding. Furthermore, if ψ(B^1,j)F for every j1, then there exists a pair with i>1 such that ψ(B^i,j)=ψ(B).

Proof.

If there exists 1kr such that ψ(B^1,k)F, then (i,j)=(1,k) is indeed a desired pair. Otherwise, as |F|=r1, there exists a pair (k1,k2) by the pigeonhole principle such that 1k1<k2r and ψ(B^1,k1)=ψ(B^1,k2). We then have ψ(B^k1+1,k2)=ψ(B)F, which means that the pair (i,j)=(k1+1,k2) 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 M is a sparse paving matroid.

Proof.

Suppose, to the contrary, that ˜1.1 does not hold for a sparse paving matroid M on the ground set E, a labeling ψ:EΓ, and a forbidden label set FΓ. Then, as minors of sparse paving matroids are sparse paving by Proposition 2.2, we may assume by Lemma 2.3 that M has rank r=|F|+1, it contains exactly one F-avoiding basis B, and AEB is also a basis (with ψ(A)F). Clearly, |F|1.

We first consider the case when |ψ[E]|r+1. Suppose that B is rainbow, i.e., no two elements in B have the same label. Fix an element eA such that B+e is still rainbow, and consider the sets Ae+f for fB. Then, by Proposition 2.1, at least r1=|F| of these r sets are bases. Since B+e is rainbow, these bases and A, each of which is obtained by adding an element of B+e to Ae, have distinct labels, thus at least one of these bases or A is F-avoiding. This contradicts that B is the only F-avoiding basis.

Next, suppose that B is not rainbow. As there are r+1 elements of different labels, we can take a set XE with |X|=r and an element eAX such that X+e is rainbow. We consider r sets X+ef for fX in addition to X itself. Then, by Proposition 2.1, at least r=|F|+1 of these r+1 sets are bases, and none of them is B as they are all rainbow. Since X+e is rainbow, these bases have distinct labels, thus at least one of them is F-avoiding. This contradicts that B is the only F-avoiding basis.

From now on, let us assume |ψ[E]|r. To complete the proof, we first prove three lemmas. For each gΓ, we call ψ1(g)ψ1({g})={eE|ψ(e)=g} the label class of g.

Lemma 3.2.

For any XE with |X|=r, ψ(X)F, and XB, one of the following holds:

  1. 1.

    X is the union of label classes, or

  2. 2.

    |BX|=1, BX is a label class, and XB is the union of label classes.

Proof.

Assume that X is not the union of label classes, i.e., there exists a pair of eX and fX with ψ(e)=ψ(f). Now X is not a basis as B is the only F-avoiding basis. Since M is sparse paving, Xe+f is a basis and ψ(Xe+f)=ψ(X)F, which implies that Xe+f=B. This holds for any pair (e,f) and the pair (e,f) is indeed unique as {e,f}=XB, completing the proof.

Lemma 3.3.

One of the following holds:

  1. 1.

    B is the union of label classes, or

  2. 2.

    there exists gΓ such that |ψ1(g)B|=|ψ1(g)(EB)|=1 and Bψ1(g) is the union of label classes.

Proof.

Assume that B is not the union of label classes, i.e., there exists a pair of eB and fB with ψ(e)=ψ(f). Let XBe+f. Then, X is not a basis as ψ(X)=ψ(B)F and B is the only F-avoiding basis. Thus, Lemma 3.2(2) implies statement 2 here.

As in Lemma 2.4, under fixed orderings a1,,ar of A and b1,,br of B, for each pair (i,j) with 1ijr, we define B^i,j(B{bi,,bj}){ai,,aj}={b1,,bi1,ai,,aj,bj+1,,br}.

Lemma 3.4.

Let C be a set and c:EC be a coloring. If |c[A]|+|c[B]|r+1, then there are orderings a1,,ar of A and b1,,br of B such that B^i,j is not the union of color classes for any pair (i,j) with 1ijr and (i,j)(1,r).

Proof.

We construct the desired orderings by fixing ai and bi for each i=1,,r1 in this order so that there exists aA{a1,,ai} with c(a)=c(ai) or bB{b1,,bi} with c(b)=c(bi). 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 (i,j) such that B^i,j is the union of color classes. If j<r, then there exists k>j such that c(ak)=c(aj) or c(bk)=c(bj). Since B^i,j is the union of color classes, {aj,ak} or {bj,bk} must be included in or disjoint from B^i,j, but {aj,ak,bj,bk}B^i,j={aj,bk} by definition, a contradiction. Otherwise, j=r and hence 1<i(j). Then, similarly, there exists ki such that c(ak)=c(ai1) or c(bk)=c(bi1), but {ai1,ak,bi1,bk}B^i,r={ak,bi1}, a contradiction. Thus, the above construction is sufficient.

Now we show that we can fix ai and bi for each i=1,,r1 so that the above condition is satisfied. The proof is done by induction on r. The base case when r=1 is trivial.

Suppose that r2. If |c[A]|+|c[B]|=r+1, then by the pigeonhole principle (as |A|+|B|=2r), there exists an element aA such that c(a)c(a) for any aA{a} or bB such that c(b)c(b) for any bB{b}. By symmetry, we may assume that c(b)c(b) for any bB{b}, and then by the pigeonhole principle (as |A|=r and |c[A]|=r+1|c[B]|r1), there exist two distinct elements a,aA with c(a)=c(a). In this case, by setting a1=a and b1=b, the condition for i=1 is satisfied as aA{a1} and c(a)=c(a1), and that for i2 can be satisfied by applying the induction hypothesis to the remaining part A=A{a1}, B=B{b1}, and c:(AB)C, where c is the restriction of c and satisfies |c[A]|+|c[B]|=|c[A]|+|c[B]|1=r.

The remaining case is when |c[A]|+|c[B]|r. Then, since |c[A]|r|c[B]|r1, we have two distinct elements a,aA with c(a)=c(a), and by setting a1=a and arbitrarily choosing b1B, the condition for i=1 is satisfied as aA{a1} with c(a)=c(a1) and that for i2 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 B is the union of label classes; this implies |ψ[A]|+|ψ[B]|=|ψ[E]|r. Let us regard ψ as a coloring and apply Lemma 3.4 to get orderings a1,,ar of A and b1,,br of B. We then apply the first statement of Lemma 2.4 to these orderings to get a pair (i,j) with 1ijr such that B^i,j is F-avoiding. We have (i,j)(1,r) since ψ(B^1,r)=ψ(A)F. Then, B^i,j is F-avoiding but is not the union of label classes, thus BB^i,j is a label class by Lemma 3.2. This is a contradiction since B is the union of label classes.

(2)  Otherwise, there exists gΓ such that ψ1(g)B={e} and ψ1(g)A={f} for some eB and fB, and Be is the union of label classes. We define a coloring c:EΓ{} by c(e)ψ(e) for eEf and c(f). Now we have |c(A)|+|c(B)|=|ψ[E]|+1r+1 since Af is also the union of label classes. Hence we can apply Lemma 3.4 to c and we get orderings a1,,ar of A and b1,,br of B, and then by Lemma 2.4, we obtain a pair (i,j) with 1ijr such that B^i,j is F-avoiding but is not the union of color classes. We have (i,j)(1,r) since ψ(B^1,r)=ψ(A)F. We apply Lemma 3.2 to X=B^i,j. (1) is impossible because the color classes refine the label classes. In case of (2), by the assumption of Lemma 3.3(2), BX={e,f}, implying that X 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 R10 does not have an SI-ordering. R10 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 K5. The ground set of this matroid is the edge set of K5 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 R10 as the even-cycle matroid of the complete graph K5 on vertex set {v1,,v5}. Then, for any two disjoint bases A and B of R10, there exists an automorphism of R10 mapping A and B to the 5-cycles {vivi+1|i[5]} and {vivi+2|i[5]} of K5, respectively, where indices are meant in a cyclic order (e.g., v6=v1).

We show the following using Lemma 4.1.

Theorem 4.2.

R10 is not SIBO.

Proof.

We consider R10 as the even-cycle matroid of the complete graph K5 on vertex set {v1,,v5}. Let A and B be disjoint bases of R10; we show that A and B do not have an SI-ordering. For this, suppose to the contrary that there exists an SI-ordering a1,,a5 of A and b1,,b5 of B. By Lemma 4.1, we may assume A={vivi+1|i[5]} and B={vivi+2|i[5]}.

We may assume by symmetry that a1=v1v2. Using that (a1,b1) is a symmetric exchange between A and B, it follows that b1=v3v5. By symmetry, we may assume that a2{v2v3,v3v4}. As (a2,b2) is a symmetric exchange between Aa1+b1 and Bb1+a1, it follows that

(a2,b2){(v2v3,v2v4),(v3v4,v1v3)}.

If (a2,b2)=(v2v3,v2v4), then Aa2+b2={v1v2,v2v4,v3v4,v4v5,v5v1} contains the 4-cycle {v1v2,v2v4,v4v5,v5v1}, a contradiction. We conclude that (a2,b2)=(v3v4,v1v3).

Using that a3A{a1,a2}={v2v3,v4v5,v5v1} and (a3,b3) is a symmetric exchange between (A{a1,a2}){b1,b2}={v1v3,v3v5,v2v3,v4v5,v5v1} and (B{b1,b2}){a1,a2}={v1v2,v3v4,v2v4,v4v1,v5v2}, it follows that

(a3,b3){(v2v3,v1v2),(v4v5,v1v4),(v1v5,v2v5)}.

It is clear that (a3,b3)(v2v3,v1v2) as v1v2=a1. If (a3,b3)=(v4v5,v1v4), then Aa3+b3={v1v2,v3v4,v1v4,v2v3,v5v1}, which contains the 4-cycle {v1v2,v2v3,v3v4,v4v1}, a contradiction. Otherwise, (a3,b3)=(v1v5,v2v5), and then Aa3+b3={v1v2,v3v4,v2v5,v2v3,v4v5}, which contains the 4-cycle {v2v3,v3v4,v4v5,v5v2}, 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 M be a matroid of rank at most 5, and (A,B) a basis pair of M not having an SI-ordering. Then, A and B are disjoint and the restriction M|(AB) is isomorphic to R10.

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 R10 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 |F|4.

Proof.

Suppose otherwise and let (M,ψ,F) be a counterexample. We may assume by Lemma 2.3 that M has rank r=|F|+1, it contains exactly one F-avoiding basis B, and AE(M)B is also a basis (with ψ(A)F).

If the basis pair (A,B) has an SI-ordering, then we obtain by Lemma 2.4 an F-avoiding basis other than B, a contradiction. Otherwise, as M has rank |F|+15, Proposition 4.3 implies that M is isomorphic to R10, which we regard as the even-cycle matroid of the complete graph K5 on the vertex set {v1,,v5}. By Lemma 4.1, we may assume that A={vivi+2|i[5]} and B={vivi+1|i[5]}. Fix k[5] and define orderings

(a1,,a5) (vk+2vk+4,vkvk+2,vk+4vk+6,vk+3vk+5,vk+1vk+3)
(b1,,b5) (vkvk+1,vk+2vk+3,vk+3vk+4,vk+1vk+2,vk+4vk+5)

of A and B, respectively (see Figure 1). Then, it can be checked that for indices 1ij5, the set B^i,j{b1,,bi1,ai,,aj,bj+1,,b5} is a basis if and only if (i,j)(3,3). In particular, B^1,j is a basis for each j1, and hence ψ(B^1,j)F, as B is the only F-avoiding basis. Thus, by Lemma 2.4, we have ψ(B^i,j)=ψ(B)F for some (i,j), which must be (3,3) as B is the only F-avoiding basis, again. That is, ψ(vk+3vk+4)=ψ(b3)=ψ(a3)=ψ(vk+4vk+6). Since this holds for every k[5], we get that

ψ(B)=k=15ψ(vk+3vk+4)=k=15ψ(vk+4vk+6)=ψ(A),

which contradicts that ψ(B)F and ψ(A)F.

Figure 1: Labeling the elements of the matroid R10 such that for indices 1ij5, the set B^i,j is a basis if and only if (i,j)(3,3). Recall that bases are the sets of size 5 containing no 4-cycle of K5.

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 d in ˜1.6 must satisfy d(k)2k1 for each k1, even for uniform matroids.

Example 5.1.

Let k be a positive integer. Let r=2k1, and let Ur,2r denote the uniform matroid of rank r on some ground set E of size 2r. We show that there exist group labelings ψt:EΓt for t[k], and a basis A of Ur,2r such that BEA is the only basis of M satisfying ψt(B)0 for all t[k].

Let us fix a set AE of size r. We set Γk=, and Γt=2t for t[k1]. Finally, we define the group labelings by

ψt(e){2t11if eA,2t1if eA and tk,2k1if eA and t=k.

Note that r1(mod 2t) for all t[k1]. It is easy to see that ψt(B)0 for all t[k], where B=EA. Hence, we only need to show that for each [r1], any set A obtained by exchanging elements of A into B is zero in at least one of the labelings.

Let t be the largest for which 2t1 divides +1. Note that 2t11(mod 2t). Moreover, as <r=2k1, we have tk. Now if t<k, then

ψi(A) =(2t11)(r)+2t1
=(2t11)r+
(2t11)(1)+(2t11) (mod 2t)
0 (mod 2t).

On the other hand, if t=k, then =2k11, and in this case

ψk(A)=(2k11)(r)2k1=(2k11)2k12k1(2k11)=0.

Next, we show the existence of d(k) as in ˜1.6 for several matroid classes. The proofs will be based on the following lemma.

Lemma 5.2.

Let ψt:EΓt be group labelings on a finite set E and ftΓt group elements for t[k]. Let BE be a subset with ψt(B)ft for all t[k]. Let X1,,XB and Y1,,YEB be pairwise disjoint nonempty subsets. For 1ij, let

Bi,j(B(XiXj))(YiYj).

If (e1/2)k!, there are indices i,j such that ψt(Bi,j)ft for all t[k].

Proof.

Let ck denote the smallest integer such that whenever ψ1,,ψk are labelings, f1,,fk group elements, and B,X1,,X,Y1,,Y are subsets as in the theorem and ck holds, then there exist indices 1ij such that ψt(Bi,j)ft for all t[k]. If no such integer exists, then define ck to be infinite. Observe that c0=1.

Claim 5.3.

ckkck1+1 holds for k1.

Proof.

Assume for contradiction that ck>kck1+1, that is, there exist labelings ψ1,,ψk, group elements f1,,fk, and subsets B,X1,,X,Y1,,Y as required with kck1+1 such that there exist no indices 1ij such that ψt(Bi,j)ft for all t[k]. In particular, for each q[], there exists t[k] such that ψt(B1,q)=ft. Since kck1+1, this implies that there exists t[k] with |{q[]|ψt(B1,q)=ft}|ck1+1. We may assume that t=k, and let 1q0<<qck1 be indices with ψk(B1,q0)==ψk(B1,qck1)=fk. Define XiXqi1+1Xqi and YiYqi1+1Yqi for i[ck1], and Bi,j(B(XiXj))(YiYj) for 1ijck1. Observe that Yi=B1,qiB1,qi1 and Xi=B1,qi1B1,qi hold for i[ck1]; thus

ψk(Yi)ψk(Xi)=ψk(B1,qi)ψk(B1,qi1)=fkfk=0.

Using the definition of ck1, we get that there exist indices 1ijck1 such that ψt(Bi,j)ft for all t[k1]. By defining iqi1+1 and jqj, we get Bi,j=Bi,j and

ψk(Bi,j)=ψk(B)+s=ij(ψk(Ys)ψk(Xs))=ψk(B)fk.

This proves that ψt(Bi,j)ft for all t[k], a contradiction.

˜5.3 implies that c1c0+1=2 and c22c1+15. We improve the latter bound by one.

Claim 5.4.

c24.

Proof.

Assume for contradiction that c2>4, and let ψ1,,ψ4 be labelings, f1,,f4 group elements, and B,X1,,X4,Y1,,Y4 subsets as in the proof of ˜5.3 such that there exist no indices 1ij4 such that ψt(Bi,j)ft for all t[2]. We have that |{q[4]|ψt(B1,q)=ft}|2 holds for all t[2], as otherwise we get a contradiction using the proof of ˜5.3 and c12. This implies that

|{q[4]|ψ1(B1,q)=f1}|=|{q[4]|ψ2(B1,q)=f2}|=2. (1)

By symmetry, we also get

|{q[4]|ψ1(Bq,4)=f1}|=|{q[4]|ψ2(Bq,4)=f2}|=2. (2)

We may assume that ψ1(B1,4)=f1. Let p,q[3] denote the unique indices such that ψ1(B1,p)=f1 and ψ1(Bq+1,4)=f1. If p=q, then

f1+f1=ψ1(B1,p)+ψ1(Bp+1,4)=ψ1(B)+ψ1(B1,4)=ψ1(B)+f1,

thus ψ1(B)=f1, a contradiction. We conclude that pq. Let r[3] be the unique index with {p,q,r}=[3]. Then, from (1) and (2), we get that ψ1(B1,p)=ψ1(B1,4)=ψ1(Bq+1,4)=f1 and ψ2(B1,q)=ψ2(B1,r)=ψ2(Bp+1,4)=ψ2(Br+1,4)=f2. Then,

f2+f2=ψ2(B1,r)+ψ2(Br+1,4)=ψ2(B1,q)+ψ2(Bq+1,4)=f2+ψ2(Bq+1,4).

thus ψ2(Bq+1,4)=f2. This contradicts (2) and finishes the proof.

Using induction we obtain that ck(i=0k1i!12)k!. Indeed, it holds for k=2 by ˜5.4, and using ˜5.3 and induction we get

ckkck1+1k(i=0k11i!12)(k1)!+1=(i=0k1i!12)k!.

The statement of the lemma follows by using that i=01i!=e.

Theorem 5.5.

Let A be a basis of a matroid M on ground set E, and ψt:EΓt group labelings and ftΓt group elements for t[k]. Assume that M has at least one basis B with ψt(B)ft for all t[k].

  1. 1.

    If M is SIBO, then it has a basis B with ψt(B)ft for all t[k] and |AB|(e1/2)k!1.

  2. 2.

    If k=2, then M has a basis B with ψ1(A)f1, ψ2(A)f2, and |AB|3.

Proof.

Let B be a basis of M such that ψt(B)ft for all t[k] and |AB| is minimum. Assume that |AB|(e1/2)k!. If M is SIBO, then there exist orderings x1,,x of B and y1,,y of A such that (B{xi,,xj}){yi,,yj} is a basis for 1ijr. Then, using Lemma 5.2 with Xi={xi} and Yi={yi} for i[], we get a contradiction to A and B being closest. This proves 1. For proving 2, assume that k=2 and M is not SIBO. Observe that in this case |AB|(e1/2)2=4. Let A be a basis of M with AAB and |AB|=4. Then, M/(AB) has rank 4 and hence is SIBO by Proposition 4.3. Thus, there exist orderings x1,,x4 of BA and y1,,y4 of AB such that (B{xi,,xj}){yi,,yj} is a basis for 1ij4. This contradicts A and B being closest by Lemma 5.2.

Example 5.1 shows that for k=2, the bound 3 in Theorem 5.52 is tight. Observe that this differs from the case ψ1=ψ2 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 k, we define a matroid M to be weakly (α,k)-base orderable if for every ordered basis pair (A,B) of M with |AB|α, there exist pairwise disjoint nonempty subsets X1,,XkBA and Y1,,YkAB such that (BiZXi)iZYi is a basis for each Z[k]. The following was shown in [20].

Theorem 5.6 (Hörsch, Imolay, Mizutani, Oki, Schwarcz [20]).

There is a computable function h:× such that for every prime power q, every GF(q)-representable matroid is weakly (h(q,k),k)-orderable for any k.

Following the terminology of [20], for a basis B of a matroid M, we say that a minor M of M is a B-minor if M=(M|X)/Y for some X,Y with YBXE(M). In this case, (M)={BXY|BY(M)}. We show the following result, which is related to results of [41].

Theorem 5.7.

Let k0 be an integer and M a sparse paving matroid of rank r. If min{r,|E(M)|r}(2kk), then for each basis B, M has a B-minor isomorphic to Uk,2k.

Proof.

We prove this by induction on k. The statements clearly hold for k=0, so assume that it holds for k1. Let EE(M), n|E|, and (Er)(M). Then, by Proposition 2.1, |H1H2|r2 holds for all H1,H2 with H1H2. Since min{r,nr}(2k2k1), by induction there exist X,Y with YBXE such that (M|X)/Y is isomorphic to Uk1,2k2. Note that (M|X)/Y has rank r|Y|, thus |Y|=rk+1.

Let SXY and 0{H|HX,|HS|=k}. Observe that |YH|=|Y||H|+|HS|=(rk+1)r+k=1 for each H0. This together with Proposition 2.1 implies that for each set ZS, there exists at most one H0 with HS=Z, implying |0|(2k2k). Since |YH|=1 for H0 and |Y|=rk+1(2kk)k+1>(2k2k)|0|, there exists yYH0H. Let YYy. We claim that (M|X)/Y is isomorphic to Uk,2k1, i.e., for each subset ZS+y with |Z|=k, ZY is a basis of M. Indeed, if yZ, then ZY being a basis follows from (M|X)/Y being isomorphic to Uk1,2k2. If yZ, then |ZS|=k, thus Z follows from yH0H. This shows that (M|X)/Y is indeed isomorphic to Uk,2k1.

Let TXY and 1{H|YH,|HT|=k1}. Observe that |HX|=1 for each H1. Then, by Proposition 2.1, for each set ZT, there exists at most one H1 with HT=Z, implying |1|(2k1k1). Since |HX|=1 for H1 and |EX||E|rk+1(2kk)k+1>(2k1k1)|1|, there exists xEX with x(EX)H1H. Let XX+x. We claim that (M|X)/Y is isomorphic to Uk,2k, i.e., for each subset ZT+x with |Z|=k, ZY is a basis of M. Indeed, if xZ, then ZY being a basis follows from (M|X)/Y being isomorphic to Uk,2k1. If xZ, then |ZT|=k1, thus ZY follows from xH1H. Therefore, (M|X)/Y is indeed isomorphic to Uk,2k, finishing the proof.

 Remark 5.8.

We note that Pendavingh and van der Pol [41] showed that for a fixed k, asymptotically almost all matroids contain Uk,2k as a minor. If M is a sparse paving matroid, then a counting argument found in [41, Lemma 4.7] combined with the observation |(M)|rr+1(|E|r) implies that if r(2kk) and |E(M)|rk hold, then M contains Uk,2k 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 B-minor for any basis B as in Theorem 5.7.

Corollary 5.9.

Every sparse paving matroid is ((2kk),k)-weakly base orderable for any k.

Proof.

Let A and B be bases of a sparse paving matroid M with |AB|(2kk), and let NM|(AB)/(AB). Then, N is a sparse paving matroid having rank |AB|(2kk) and |E(N)|=2|AB|, thus Theorem 5.7 implies that N has a (BA)-minor isomorphic to Uk,2k, that is, there exist X,Y with YBAXE(N) such that N(N|X)/Y is isomorphic to Uk,2k. Observe that B(XY) has size k as it is a basis of N, and so does A(XY) as |E(N)|=2k. Let B(XY)={b1,,bk} and A(XY)={a1,,ak}. Then, (B{bi|iZ}){ai|iZ} is a basis for each Z[k], showing that M is ((2kk),k)-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 ((2kk),k)-weakly base orderable for k, that is, the sets X1,,Xk and Y1,,Yk in the definition of ((2kk),k)-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 (2k,k)-weakly base orderable for k.

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) GF(q)-representable matroids for a fixed prime power q or (2) sparse paving matroids. Then, there is a computable function d: such that if M, ψt:E(M)Γt are group labelings, ftΓt are group elements for t[k], and A is a basis of M, then M has a basis B with ψt(B)ft for all t[k] and |AB|d(k), provided that M has at least one basis B with ψt(B)ft for all t[k].

Proof.

(1)  Suppose that M is GF(q)-representable. Let h be the function provided by Theorem 5.6, and define d(k)h(q,(e1/2)k!)1. Let B be a basis with ψt(B)ft for all t[k] such that |AB| is minimum. If |AB|>d(k), then by the definition of h, for (e1/2)k!, there exist pairwise disjoint nonempty subsets X1,,XBA and Y1,,YAB such that (BiZXi)iZYi is a basis for each Z[]. Then, we get a contradiction by Lemma 5.2 to A and B being closest.

(2)  By Corollary 5.9 sparse paving matroids are ((2kk),k)-weakly base orderable for each k1. Therefore, as with Case (1), we get the desired function d(k).

6 Conclusion

In this paper, we have proven ˜1.1 for the case where the matroid is sparse paving or |F|4, and settled ˜1.6 for k=2 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 d(k). 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 M be a matroid with the ground set E, ψt:EΓt a group labeling, and ftΓt a group element for t[k]. Then, if at least one such basis exists, for any basis A of M, is there a basis B of M with ψt(B)ft for t[k] and |AB|2k1?

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 S-T paths. arXiv preprint, 2024. arXiv:2408.16344.
  • [8] Maria Chudnovsky, William H. Cunningham, and Jim Geelen. An algorithm for packing non-zero A-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 A-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 w 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 A-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 2r-elements, rank-r, non-SIBO matroid to SAT by describing a CNF (conjunctive normal form) formulation.

Let E=[2r] be the ground set. We prepare (2rr) Boolean variables xB indexed by B(Er). We build a CNF such that {B(Er)|xB is true} forms the basis family of a matroid, [r] and E[r] are bases, and ([r],E[r]) has no SI-ordering by collecting the following clauses.

Basis exchange property:

for every A,B(Er) and eAB,

¬xA¬xBfBAxAe+f. (3)
Fixed basis:
x[r]. (4)
Fixed basis:
xE[r]. (5)
No SI-ordering:

for every permutation a1,,ar of [r] and b1,,br of E[r],

0i<jr¬x{a1,,ai,bi+1,,bj,aj+1,,ar}. (6)

Note that if a non-disjoint basis pair (A,B) of a matroid M has no SI-ordering, then (AB,BA) has no SI-ordering as well in M/(AB). Thus, we can restrict our attention to the disjoint basis pair ([r],E[r]) by verifying the unsatisfiability of the CNF from small r.

Our Python script to solve the above SAT instance is available at https://github.com/taiheioki/sibo.