Cyclic ordering of split matroids
Kristóf Bérczi, Áron Jánosik, Bence Mátravölgyi · 2024
Read Cyclic ordering of split matroids by Kristóf Bérczi, Áron Jánosik, Bence Mátravölgyi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01061.txt.
Description
Abstract There is a long list of open questions rooted in the same underlying problem: understanding the structure of bases or common bases of matroids. These conjectures suggest that matroids may possess much stronger structural properties than are currently known. One example is related to cyclic orderings of matroids.
Catalog record
| CREATOR | Kristóf Bérczi, Áron Jánosik, Bence Mátravölgyi |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01061
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cyclic ordering of split matroids Kristóf Bérczi, Áron Jánosik, Bence Mátravölgyi Abstract There is a long list of open questions rooted in the same underlying problem: understanding the structure of bases or common bases of matroids. These conjectures suggest that matroids may possess much stronger structural properties than are currently known. One example is related to cyclic orderings of matroids. A rank- r r matroid is called cyclically orderable if its ground set admits a cyclic ordering such that any interval of r r consecutive elements forms a basis. In this paper, we show that if the ground set of a split matroid decomposes into pairwise disjoint bases, then it is cyclically orderable. This result answers a conjecture of Kajitani, Ueno, and Miyano in a special case, and also strengthens Gabow’s conjecture for this class of matroids. Our proof is algorithmic, hence it provides a procedure for determining a cyclic ordering in question using a polynomial number of independence oracle calls. Keywords: Cyclic ordering, Paving matroids, Sequential symmetric basis exchanges, Split matroids 1 Introduction Throughout the paper, we denote a matroid by M=(S,\mathcal{B}) , where S is a finite ground set and \mathcal{B} is the family of bases , satisfying the so-called basis axioms : (B1) \emptyset\in\mathcal{B} , and (B2) for any B_{1},B_{2}\in\mathcal{B} and e\in B_{1}-B_{2} , there exists f\in B_{2}-B_{1} such that B_{1}-e+f\in\mathcal{B} . The latter property, called the basis exchange axiom , is one of the most fundamental tools in matroid theory. Nevertheless, it only provides a local characterization of the relationship between bases, which presents a significant stumbling block to further progress. A rank- r matroid M=(S,\mathcal{B}) with |S|=n is cyclically orderable if there exists an ordering S={s_{1},\dots,s_{n}} such that {s_{i},s_{i+1},\dots,s_{i+r-1}}\in\mathcal{B} for every i\in[n] , where indices are understood in a cyclic order. While studying the structure of symmetric exchanges in matroids, Gabow [ 12 ] formulated a beautiful conjecture, stating that every matroid whose ground set decomposes into two disjoint bases is cyclically orderable. This question was raised independently by Wiedemann [ 21 ] and by Cordovil and Moreira [ 6 ] . The conjecture makes a stronger claim: for a fixed partition, the cyclic ordering can be chosen such that the elements of the two bases in the partition form contiguous intervals. Conjecture 1 (Gabow) . Let M=(S,\mathcal{B}) be a matroid and S=B_{1}\cup B_{2} be a partition of the ground set into two disjoint bases. Then, M has a cyclic ordering in which the elements of B_{1} and B_{2} form intervals. It is not difficult to see that the statement holds for strongly base orderable matroids. The conjecture was settled for graphic matroids [ 14 , 6 , 21 ] , sparse paving matroids [ 5 ] , matroids of rank at most 4 [ 16 ] and 5 [ 15 ] , split matroids [ 4 ] , and regular matroids [ 2 ] . However, the existence of a cyclic ordering remains open in general, even without the constraint of the bases forming intervals. In [ 14 ] , Kajitani, Ueno, and Miyano proposed a conjecture that would provide a full characterization of cyclically orderable matroids. A matroid M=(S,\mathcal{B}) with rank function r_{M} is called uniformly dense if |S|\cdot r_{M}(X)\geq r_{M}(S)\cdot|X| holds for every X\subseteq S . It is not difficult to see that a cyclically orderable matroid is necessarily uniformly dense as well, and the conjecture states that this condition is also sufficient. Conjecture 2 (Kajitani, Ueno, and Miyano) . A matroid is cyclically orderable if and only if it is uniformly dense. Despite the fact that the conjecture would provide entirely new insights into the structure of matroids, very little progress has been made so far. Van den Heuvel and Thomassé [ 19 ] showed that the conjecture is true if |S| and r(S) are coprimes, and Bonin’s result [ 5 ] for sparse paving matroids remains true also in this more general setting. Recently, McGuinness [ 17 ] made a significant progress by verifying the conjecture for paving matroids. It is worth taking a moment to consider the interpretation of the uniformly dense property. By the matroid union theorem of Edmonds and Fulkerson [ 7 ] , the ground set of a matroid M=(S,\mathcal{B}) can be covered by k bases if and only if k\cdot r_{M}(X)\geq|X| holds for every X\subseteq S . Using this, a matroid is uniformly dense if and only if its ground set can be covered by \lceil|S|/r_{M}(S)\rceil bases. In other words, the ground set can be decomposed in ‘almost’ disjoint bases, where almost means that the total overlapping between distinct bases is bounded by r_{M}(S)-1 . In particular, any matroid whose ground set decomposes into pairwise disjoint bases is uniformly dense. This observation motivates the following strengthening of Gabow’s conjecture. Conjecture 3 . Let M=(S,\mathcal{B}) be a matroid and S=B_{1}\cup\dots\cup B_{k} be a partition of the ground set into k pairwise disjoint bases. Then, M has a cyclic ordering in which the elements of B_{i} form an interval for each i\in[k] . To the best of our knowledge, Conjecture 3 has not been previously considered and remains open even for very restricted classes of matroids, such as strongly base orderable matroids. Our main contribution is proving the conjecture for the class of split matroids. Split matroids were first introduced by Joswig and Schröter [ 13 ] while studying matroid polytopes from a geometric point of view. Since then, this class of matroids has gained importance in many contexts, primarily due to the work of Ferroni and Schröter [ 8 , 9 , 10 , 11 ] . Theorem 1 . Conjecture 3 is true for split matroids. It is worth emphasizing that our proof is algorithmic, hence it provides a procedure for determining a cyclic ordering in question using a polynomial number of independence oracle calls. Remark 2 . In fact, we prove a slightly stronger statement: in the cyclic ordering obtained, the bases B_{1},\dots,B_{k} form intervals that follow each other in this order. The rest of the paper is organized as follows. Basic definitions and notation are introduced in Section 2 . We prove Conjecture 3 for split matroids in Section 3 . Finally, in Section 4 , we give a list of related open questions and conjectures that are subject of future research. 2 Preliminaries General notation. We denote the set of nonnegative integers by \mathbb{Z}_{+} . For k\in\mathbb{Z}_{+} , we use [k]=\{1,\dots,k\} . Given a ground set S , the difference of X,Y\subseteq S is denoted by X-Y . If Y consists of a single element y , then X-\{y\} and X\cup\{y\} are abbreviated as X-y and X+y , respectively. The symmetric difference of X and Y is denoted by X\triangle Y\coloneqq(X-Y)\cup(Y-X) . Split matroids. For basic definitions on matroids, we refer the reader to [ 18 ] . Let S be a ground set of size at least r , \mathcal{H}=\{H_{1},\dots,H_{q}\} be a (possibly empty) collection of subsets of S , and r,r_{1},\dots,r_{q} be nonnegative integers satisfying \displaystyle|H_{i}\cap H_{j}| \displaystyle\leq r_{i}+r_{j}-r\ \text{for distinct $i,j\in[q]$,} (H1) \displaystyle|S-H_{i}|+r_{i} \displaystyle\geq r\ \text{for $i\in[q]$.} (H2) Then the corresponding elementary split matroid M=(S,\mathcal{B}) is given by \mathcal{B}=\{X\subseteq S\mid|X|=r,\ |X\cap H_{i}|\leq r_{i}\ \text{for $i\in[q]$}\} ; see [ 1