Towards the Proximity Conjecture on Group-Labeled Matroids

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 $|\mathrm{\Gamma }\setminus 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|\le 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 $R_{10}$. We complete the proof by showing ˜1.1 for $R_{10}$ separately. For completeness, we also provide an elementary proof that $R_{10}$ 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 ${\psi }_1,\mathrm{\dots },{\psi }_k$, where each ${\psi }_t$ is a map from $E$ to an abelian group ${\mathrm{\Gamma }}_t$, and $k$ forbidden labels $f_1\in {\mathrm{\Gamma }}_1,\mathrm{\dots },f_k\in {\mathrm{\Gamma }}_k$, we are to find a basis $B$ such that ${\psi }_t(B)\ne f_t$ for all $t\in \{1,\mathrm{\dots },k\}$. Questions with similar constraints have also been studied for paths and cycles in graphs [22, 19, 18, 7]. Note that the ${\psi }_1=\mathrm{\cdots }={\psi }_k$ case corresponds to the single $F$-avoiding constraint with $F=\{f_1,\mathrm{\dots },f_k\}$, and the more general constraints ${\psi }_1(B)\notin F_1,\mathrm{\dots },{\psi }_k(B)\notin F_k$ with $F_1\subseteq {\mathrm{\Gamma }}_1,\mathrm{\dots },F_k\subseteq {\mathrm{\Gamma }}_k$ reduce to this setting with ${\sum }_{t=1}^k|F_t|$ constraints ${\psi }_t(B)\ne f$ $(t\in \{1,\mathrm{\dots },k\},f\in F_t)$. We pose the following conjecture.

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 $2^k-1$. ˜1.1 for $|F|=1$ implies that this is tight if $k=1$. For $k=2$, we show that $2^2-1=3$ is tight. We further show that $d(k)=\lfloor (e-1/2)k!\rfloor -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.

Eisenbrand, Rohwedder, and Węgrzycki [13] showed a proximity result on basis pairs of integer-labeled matroids. For a matroid labeled with ${\mathbb{Z}}_m$ for a positive integer $m\ge 2$, this result implies that if there exists a zero basis, then for any basis $A$, there exists a zero basis $B$ such that $|A\setminus B|=O(m^5)$. This bound is weaker than the bound $|A\setminus B|\le m-1$ implied by ˜1.1. Their result also implies a bound $|A\setminus B|={|\mathrm{\Gamma }|}^{O(\log |\mathrm{\Gamma }|)}$ for a matroid labeled with a finite abelian group $\mathrm{\Gamma }$. 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.

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|\le 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.

If there exists $1\le k\le r$ such that $\psi ({\widehat{B}}_{1,k})\notin F$, then $(i,j)=(1,k)$ is indeed a desired pair. Otherwise, as $|F|=r-1$, there exists a pair $(k_1,k_2)$ by the pigeonhole principle such that and $\psi ({\widehat{B}}_{1,k_1})=\psi ({\widehat{B}}_{1,k_2})$. We then have $\psi ({\widehat{B}}_{k_1+1,k_2})=\psi (B)\notin F$, which means that the pair $(i,j)=(k_1+1,k_2)$ is a desired one. $◀$

Suppose, to the contrary, that ˜1.1 does not hold for a sparse paving matroid $M$ on the ground set $E$, a labeling $\psi :E\to \mathrm{\Gamma }$, and a forbidden label set $F\subseteq \mathrm{\Gamma }$. 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 $A≔E\setminus B$ is also a basis (with $\psi (A)\in F$). Clearly, $|F|\ge 1$.

We first consider the case when $|\psi [E]|\ge r+1$. Suppose that $B$ is rainbow, i.e., no two elements in $B$ have the same label. Fix an element $e\in A$ such that $B+e$ is still rainbow, and consider the sets $A-e+f$ for $f\in B$. Then, by Proposition 2.1, at least $r-1=|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 $A-e$, 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 $X\subseteq E$ with $|X|=r$ and an element $e\in A\setminus X$ such that $X+e$ is rainbow. We consider $r$ sets $X+e-f$ for $f\in X$ 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 $|\psi [E]|\le r$. To complete the proof, we first prove three lemmas. For each $g\in \mathrm{\Gamma }$, we call ${\psi }^{-1}(g)≔{\psi }^{-1}(\{g\})=\{e\in E|\psi (e)=g\}$ the label class of $g$.

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

Assume that $B$ is not the union of label classes, i.e., there exists a pair of $e\in B$ and $f\notin B$ with $\psi (e)=\psi (f)$. Let $X≔B-e+f$. Then, $X$ is not a basis as $\psi (X)=\psi (B)\notin 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 $a_1,\mathrm{\dots },a_r$ of $A$ and $b_1,\mathrm{\dots },b_r$ of $B$, for each pair $(i,j)$ with $1\le i\le j\le r$, we define ${\widehat{B}}_{i,j}≔(B\setminus \{b_i,\mathrm{\dots },b_j\})\cup \{a_i,\mathrm{\dots },a_j\}=\{b_1,\mathrm{\dots },b_{i-1},a_i,\mathrm{\dots },a_j,b_{j+1},\mathrm{\dots },b_r\}$.

We construct the desired orderings by fixing $a_i$ and $b_i$ for each $i=1,\mathrm{\dots },r-1$ in this order so that there exists $a\in A\setminus \{a_1,\mathrm{\dots },a_i\}$ with $c(a)=c(a_i)$ or $b\in B\setminus \{b_1,\mathrm{\dots },b_i\}$ with $c(b)=c(b_i)$. 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 ${\widehat{B}}_{i,j}$ is the union of color classes. If , then there exists $k>j$ such that $c(a_k)=c(a_j)$ or $c(b_k)=c(b_j)$. Since ${\widehat{B}}_{i,j}$ is the union of color classes, $\{a_j,a_k\}$ or $\{b_j,b_k\}$ must be included in or disjoint from ${\widehat{B}}_{i,j}$, but $\{a_j,a_k,b_j,b_k\}\cap {\widehat{B}}_{i,j}=\{a_j,b_k\}$ by definition, a contradiction. Otherwise, $j=r$ and hence . Then, similarly, there exists $k\ge i$ such that $c(a_k)=c(a_{i-1})$ or $c(b_k)=c(b_{i-1})$, but $\{a_{i-1},a_k,b_{i-1},b_k\}\cap {\widehat{B}}_{i,r}=\{a_k,b_{i-1}\}$, a contradiction. Thus, the above construction is sufficient.

Now we show that we can fix $a_i$ and $b_i$ for each $i=1,\mathrm{\dots },r-1$ 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 $r\ge 2$. If $|c[A]|+|c[B]|=r+1$, then by the pigeonhole principle (as $|A|+|B|=2r$), there exists an element $a\in A$ such that $c(a)\ne c(a^{\prime })$ for any $a^{\prime }\in A\setminus \{a\}$ or $b\in B$ such that $c(b)\ne c(b^{\prime })$ for any $b^{\prime }\in B\setminus \{b\}$. By symmetry, we may assume that $c(b)\ne c(b^{\prime })$ for any $b^{\prime }\in B\setminus \{b\}$, and then by the pigeonhole principle (as $|A|=r$ and $|c[A]|=r+1-|c[B]|\le r-1$), there exist two distinct elements $a,a^{\prime }\in A$ with $c(a)=c(a^{\prime })$. In this case, by setting $a_1=a$ and $b_1=b$, the condition for $i=1$ is satisfied as $a\in A\setminus \{a_1\}$ and $c(a)=c(a_1)$, and that for $i\ge 2$ can be satisfied by applying the induction hypothesis to the remaining part $A^{\prime }=A\setminus \{a_1\}$, $B^{\prime }=B\setminus \{b_1\}$, and $c^{\prime }:(A^{\prime }\cup B^{\prime })\to C$, where $c^{\prime }$ is the restriction of $c$ and satisfies $|c^{\prime }[A^{\prime }]|+|c^{\prime }[B^{\prime }]|=|c[A]|+|c[B]|-1=r$.

The remaining case is when $|c[A]|+|c[B]|\le r$. Then, since $|c[A]|\le r-|c[B]|\le r-1$, we have two distinct elements $a,a^{\prime }\in A$ with $c(a)=c(a^{\prime })$, and by setting $a_1=a$ and arbitrarily choosing $b_1\in B$, the condition for $i=1$ is satisfied as $a\in A\setminus \{a_1\}$ with $c(a)=c(a_1)$ and that for $i\ge 2$ 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 $|\psi [A]|+|\psi [B]|=|\psi [E]|\le r$. Let us regard $\psi$ as a coloring and apply Lemma 3.4 to get orderings $a_1,\mathrm{\dots },a_r$ of $A$ and $b_1,\mathrm{\dots },b_r$ of $B$. We then apply the first statement of Lemma 2.4 to these orderings to get a pair $(i,j)$ with $1\le i\le j\le r$ such that ${\widehat{B}}_{i,j}$ is $F$-avoiding. We have $(i,j)\ne (1,r)$ since $\psi ({\widehat{B}}_{1,r})=\psi (A)\in F$. Then, ${\widehat{B}}_{i,j}$ is $F$-avoiding but is not the union of label classes, thus $B△{\widehat{B}}_{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\in \mathrm{\Gamma }$ such that ${\psi }^{-1}(g)\cap B=\{e\}$ and ${\psi }^{-1}(g)\cap A=\{f\}$ for some $e\in B$ and $f\notin B$, and $B-e$ is the union of label classes. We define a coloring $c:E\to \mathrm{\Gamma }\cup \{\star \}$ by $c(e^{\prime })≔\psi (e^{\prime })$ for $e^{\prime }\in E-f$ and $c(f)≔\star$. Now we have $|c(A)|+|c(B)|=|\psi [E]|+1\le r+1$ since $A-f$ is also the union of label classes. Hence we can apply Lemma 3.4 to $c$ and we get orderings $a_1,\mathrm{\dots },a_r$ of $A$ and $b_1,\mathrm{\dots },b_r$ of $B$, and then by Lemma 2.4, we obtain a pair $(i,j)$ with $1\le i\le j\le r$ such that ${\widehat{B}}_{i,j}$ is $F$-avoiding but is not the union of color classes. We have $(i,j)\ne (1,r)$ since $\psi ({\widehat{B}}_{1,r})=\psi (A)\in F$. We apply Lemma 3.2 to $X={\widehat{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), $B△X=\{e,f\}$, implying that $X$ is the union of color classes, a contradiction. $◀$

We consider $R_{10}$ as the even-cycle matroid of the complete graph $K_5$ on vertex set $\{v_1,\mathrm{\dots },v_5\}$. Let $A$ and $B$ be disjoint bases of $R_{10}$; we show that $A$ and $B$ do not have an SI-ordering. For this, suppose to the contrary that there exists an SI-ordering $a_1,\mathrm{\dots },a_5$ of $A$ and $b_1,\mathrm{\dots },b_5$ of $B$. By Lemma 4.1, we may assume $A=\{v_i{v}_{i+1}|i\in [5]\}$ and $B=\{v_i{v}_{i+2}|i\in [5]\}$.

We may assume by symmetry that $a_1=v_1{v}_2$. Using that $(a_1,b_1)$ is a symmetric exchange between $A$ and $B$, it follows that $b_1=v_3{v}_5$. By symmetry, we may assume that $a_2\in \{v_2{v}_3,v_3{v}_4\}$. As $(a_2,b_2)$ is a symmetric exchange between $A-a_1+b_1$ and $B-b_1+a_1$, it follows that

If $(a_2,b_2)=(v_2{v}_3,v_2{v}_4)$, then $A-a_2+b_2=\{v_1{v}_2,v_2{v}_4,v_3{v}_4,v_4{v}_5,v_5{v}_1\}$ contains the 4-cycle $\{v_1{v}_2,v_2{v}_4,v_4{v}_5,v_5{v}_1\}$, a contradiction. We conclude that $(a_2,b_2)=(v_3{v}_4,v_1{v}_3)$.

Using that $a_3\in A\setminus \{a_1,a_2\}=\{v_2{v}_3,v_4{v}_5,v_5{v}_1\}$ and $(a_3,b_3)$ is a symmetric exchange between $(A\setminus \{a_1,a_2\})\cup \{b_1,b_2\}=\{v_1{v}_3,v_3{v}_5,v_2{v}_3,v_4{v}_5,v_5{v}_1\}$ and $(B\setminus \{b_1,b_2\})\cup \{a_1,a_2\}=\{v_1{v}_2,v_3{v}_4,v_2{v}_4,v_4{v}_1,v_5{v}_2\}$, it follows that

It is clear that $(a_3,b_3)\ne (v_2{v}_3,v_1{v}_2)$ as $v_1{v}_2=a_1$. If $(a_3,b_3)=(v_4{v}_5,v_1{v}_4)$, then $A-a_3+b_3=\{v_1{v}_2,v_3{v}_4,v_1{v}_4,v_2{v}_3,v_5{v}_1\}$, which contains the 4-cycle $\{v_1{v}_2,v_2{v}_3,v_3{v}_4,v_4{v}_1\}$, a contradiction. Otherwise, $(a_3,b_3)=(v_1{v}_5,v_2{v}_5)$, and then $A-a_3+b_3=\{v_1{v}_2,v_3{v}_4,v_2{v}_5,v_2{v}_3,v_4{v}_5\}$, which contains the 4-cycle $\{v_2{v}_3,v_3{v}_4,v_4{v}_5,v_5{v}_2\}$, 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.

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 $R_{10}$ 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.

Suppose otherwise and let $(M,\psi ,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 $A≔E(M)\setminus B$ is also a basis (with $\psi (A)\in 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|+1\le 5$, Proposition 4.3 implies that $M$ is isomorphic to $R_{10}$, which we regard as the even-cycle matroid of the complete graph $K_5$ on the vertex set $\{v_1,\mathrm{\dots },v_5\}$. By Lemma 4.1, we may assume that $A=\{v_i{v}_{i+2}|i\in [5]\}$ and $B=\{v_i{v}_{i+1}|i\in [5]\}$. Fix $k\in [5]$ and define orderings

of $A$ and $B$, respectively (see Figure 1). Then, it can be checked that for indices $1\le i\le j\le 5$, the set ${\widehat{B}}_{i,j}≔\{b_1,\mathrm{\dots },b_{i-1},a_i,\mathrm{\dots },a_j,b_{j+1},\mathrm{\dots },b_5\}$ is a basis if and only if $(i,j)\ne (3,3)$. In particular, ${\widehat{B}}_{1,j}$ is a basis for each $j\ge 1$, and hence $\psi ({\widehat{B}}_{1,j})\in F$, as $B$ is the only $F$-avoiding basis. Thus, by Lemma 2.4, we have $\psi ({\widehat{B}}_{i,j})=\psi (B)\notin F$ for some $(i,j)$, which must be $(3,3)$ as $B$ is the only $F$-avoiding basis, again. That is, $\psi (v_{k+3}{v}_{k+4})=\psi (b_3)=\psi (a_3)=\psi (v_{k+4}{v}_{k+6})$. Since this holds for every $k\in [5]$, we get that

which contradicts that $\psi (B)\notin F$ and $\psi (A)\in F$.

$◀$