{'fraction_non_alphanumeric': 0.061058668897120326, 'fraction_numerical': 0.019416895686461943, 'mean_word_length': 3.503362927091741, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse paving matroids, basis-exchange properties, and cyclic flats

We provide evidence for five long-standing, basis-exchange conjectures for matroids by proving them for the enormous class of sparse paving matroids. We also explore the role that these matroids may play in the following problem: as a function of the size of the ground set, what is the greatest number of cyclic flats that a matroid can have?


INTRODUCTION
A matroid is paving if the closure of each nonspanning circuit is a hyperplane; it is sparse paving if each nonspanning circuit is a hyperplane. Thus, a matroid M of rank r is sparse paving if and only if each r-subset of E(M ) is either a basis or a circuit-hyperplane. It follows that the class of sparse paving matroids is dual-closed. It is easy to show that this class is also minor-closed. Sparse paving matroids can also be characterized as the matroids M for which both M and its dual, M * , are paving.
While paving and sparse paving matroids have received increasing attention recently (see, e.g., [12,17,21,22,23]), they have long played important roles in matroid theory. For instance, D. Knuth [20] constructed at least 2 ( n ⌊n/2⌋ )/2n n! nonisomorphic sparse paving matroids of rank ⌊n/2⌋ on n elements; with the upper bound by M. Piff [26], it follows that the number g n of nonisomorphic simple matroids on n elements satisfies (1.1) n − 3 2 log 2 n + O(log 2 log 2 n) ≤ log 2 log 2 g n ≤ n − log 2 n + O(log 2 log 2 n), with sparse paving matroids accounting for the lower bound. Taking this further, in [21], D. Mayhew If E(M ) is the disjoint union of two bases of M , then G(M ) is isomorphic to the basiscobasis graph studied by R. Cordovil and M. Moreira [8]. The following conjecture was posed by M. Farber [9], who proved it for transversal matroids. (In [10], M. Farber, B. Richter and H. Shank proved it for graphic and cographic matroids.) Conjecture 1.1. The basis pair graph of any matroid is connected.
The second conjecture involves a family of graphs that we can associate with a matroid. Fix an integer k ≥ 2. Let M be a matroid of rank r and let S be a multiset of size kr with elements in E(M ). Define the graph G M (S) as follows: the vertices of G M (S) are all multisets of k bases of M whose multiset union is S; two vertices are adjacent if one can be obtained from the other by one symmetric exchange among one pair of bases in one of the vertices. Thus, vertices (This graph may be empty.) The conjecture below is due to N. White [28,Conjecture 12].
A counting argument shows that inequality (1.2) holds if M is cyclically orderable. Recent progress on this conjecture was made by J. van den Heuvel and S. Thomassé [15] The fifth conjecture was first raised as a problem by H. Gabow [11] and has been pursued in [8,15,18]. To match our work below, we state the conjecture in the case of disjoint bases; it is easy to show that this implies its counterpart for arbitrary bases. Conjecture 1.5. If B 1 and B 2 are disjoint bases of a rank-r matroid M , then some cycle and has each set of r cyclically-consecutive elements being a basis of M .
It is not hard to show that if this conjecture holds for M , then it holds for M * and for all minors of M . H. Gabow [11] noted that the conjecture holds for transversal matroids. It has also been proven for graphic matroids [8,18]. A. de Mier [24] observed that this conjecture holds for strongly base-orderable matroids. Recall that a matroid is strongly base-orderable if for each pair of bases B 1 and B 2 of M , there is a bijection φ : B 1 → B 2 such that for every subset X ⊆ B 1 , both (B 1 − X) ∪ φ(X) and (B 2 − φ(X)) ∪ X are bases. If M is strongly base-orderable, then listing the elements of B 1 in any order followed by their images under φ, in the corresponding order, gives the required cycle. The class of strongly base-orderable matroids is both minor-closed and dual-closed, and it strictly contains the class of all gammoids (which include transversal matroids).
In Section 2, we prove Conjectures 1.1-1.5 for sparse paving matroids. Section 3 treats another aspect of these matroids as we study the greatest number of cyclic flats in any matroid on n elements. We give an upper bound on this number and note that a lower bound follows from work of R. Graham and N. Sloane [13] which, in a different setting, essentially constructs sparse paving matroids. The gap between these bounds is similar to that in inequality (1.1). We provide the relevant background on cyclic flats in that section.

PROOFS OF CONJECTURES 1.1-1.5 IN THE CASE OF SPARSE PAVING MATROIDS
We will use the lemmas below. The first follows easily from the definition of sparse paving. Although we will not use it, we note that the following strengthening of Lemma 2.1 is easy to prove: a matroid M of rank r is sparse paving if and only if whenever H and B are two r-subsets of E(M ) with |H△B| = 2 and H is not a basis, then B is a basis. (We remark that the analogous condition on discrete polymatroids winds up being too restrictive to be of interest.) Proof. The lemma follows since, by Lemma 2.1, at most one set (B − a) ∪ x with x ∈ X, and at most one set (B ′ − x ′ ) ∪ a with x ′ ∈ X, is a circuit-hyperplane.
We now turn to Conjecture 1.1. Proof. We first prove the result when E(M ) is the disjoint union of two bases; we will then reduce the general case to this one. In this case, vertices have the form (B 1 , B 2 , ∅), which we simplify to (B 1 , B 2 ) in the next two paragraphs. We must show that for each pair (A 1 , A 2 ) and (B 1 , B 2 ) of vertices in G(M ) with |A 1 △B 1 | ≥ 4, there is a path between them. For this, it suffices to show that there is a path from (B 1 , In the remaining case, If any of the following four symmetric exchanges yields only bases, it would provide the desired vertex Thus, we may assume that each pair contains a circuit-hyperplane. By symmetry, we may assume that ( For all four sets just identified to be circuit-hyperplanes, we must have r(M ) ≥ 3, so there is an element x in B 1 ∩ A 1 . By comparison with the four known circuit-hyperplanes, it follows that each set in the following symmetric exchanges is a basis: exists. In the general case, for two vertices A = (A 1 , A 2 , A 3 ) and (B 1 , B 2 , B 3 ) of G(M ), we will show that there is a path in G(M ) from A to a vertex of the form (C 1 , C 2 , B 3 ); the theorem then follows by applying the case just treated to the basis pair graph of M \B 3 . (Recall that the third set in these triples need not be a basis.) Assume |A 3 △B 3 | ≥ 4. By symmetry, we may assume By iterating the argument above, it now suffices to treat the case is a basis of M , then the claim holds, so assume instead that this set is a circuit-hyperplane. By symmetrically exchanging any element Proof. Let M be a sparse paving matroid. We prove that G M (S) is connected by induction on k, where |S| = k r(M ). The base case k = 1 is trivial: G M (S) is connected since it has at most one vertex. For k ≥ 2, we claim that for any two vertices Proving this claim gives the result by induction since having a path from A to B in G M (S) follows from having a path from By symmetry, we may assume that the sum of the multiplicities of the elements in A 1 − B 1 in S is at least as large as the corresponding sum for B 1 − A 1 . It follows that some basis in B, say B 2 , has more elements from We now address the case with B 2 ∩ (A 1 △B 1 ) = {a 1 , a 2 , b 3 }, thereby completing the argument for i ≥ 3. If we can symmetrically exchange one of a 1 , a 2 in B 2 for one of b 1 , b 2 in B 1 to get bases, then statement (*) holds. Assume that none of these four symmetric exchanges yields only bases. An argument like that in the third paragraph of the proof of Theorem 2.3 shows that we may assume that are circuit-hyperplanes. In order to have |A 1 △B 1 | ≤ |A 1 △B 2 | given that Now assume i = 2. By symmetry, there are two cases: We may assume a 1 ∈ B 2 . If a 1 in B 2 can be symmetrically exchanged with either b 1 or b 2 in B 1 to yield two bases, then statement (*) holds, so assume this fails. By symmetry, can be assumed to be circuit-hyperplanes. Since |A 1 △B 1 | ≤ |A 1 △B 2 |, there are least two elements, say z 2 and z 3 , in We now address the case with B 2 ∩ {b 1 , b 2 } = {b 1 }, thus completing the argument for i = 2. Note that B 2 must also contain a 1 and a 2 . Statement (*) holds if b 2 in B 1 can be symmetrically exchanged with either a 1 or a 2 in B 2 to yield two bases. If neither exchange yields only bases, then, by symmetry, we may assume that can symmetrically exchange x ∈ B h with some y ∈ B 2 (which cannot be a 1 ) to yield two bases; with statement (A), this allows us to exchange b 1 in B 1 with a 1 in (B 2 − y) ∪ x to yield statement (*). Thus, we may assume imply that the sum of the multiplicities of the elements in X in the sets in B is |X|(k − t − 1) + (|X| − 1)t, that is, |X|(k − 1) − t. By statement (A), X ∪ b 1 is not in A , so the sum of the multiplicities of the elements in X in the sets in A is at most |X|(k − t − 2) + (|X| − 1)(t + 1), that is, |X|(k − 1) − t − 1, which, as desired, contradicts the equality A∈A A = B∈B B.
We now prove a general connection between Conjectures 1.1, 1.2, and 1.3.

Theorem 2.5. Let M be a matroid for which the basis pair graph of each of its minors is connected. For k ≥ 2, let S be a multiset of size k r(M ) with elements in E(M ). If
, . . . , A σ(k) ). Since every permutation is a composition of transpositions, we focus on a transposition σ, say permuting i and j with i < j. The desired result follows if we show that there is a path from A to A σ in which all bases but the i-th and j-th are fixed. This follow by noting that the sequence of symmetric exchanges that gives a path from in the basis pair graph of the minor M |(A i ∪ A j )/(A i ∩ A j ) also gives the desired path from A to A σ in G ′ M (S). For Conjecture 1.4, we start with a lemma. A k-interval in a cycle σ is a set of k cyclically-consecutive elements, that is, {x, σ(x), σ 2 (x), . . . , σ k−1 (x)} for some x. Proof. As noted after Conjecture 1.4, inequality (1.2) holds in every cyclically orderable matroid. The conjecture is easy to verify for all sparse paving matroids that have rank or nullity at most two (this includes all disconnected sparse paving matroids, i.e., U 0,n , U n,n , U n−1,n ⊕ U 1,1 , U 1,n ⊕ U 0,1 , and U 1,2 ⊕ U 1,2 ; this also includes all cases in which inequality (1.2) fails), so below we assume that M has rank and nullity at least three.
If H 2 is a basis, then σ 2 is the cycle we want. Thus, assume that H 2 is a circuit-hyperplane.
We repeatedly apply this type of argument below. For brevity, for each cycle we list its r-intervals that differ from their counterparts in σ 1 and, when possible, the circuithyperplanes that, with Lemma 2.1, show that these intervals are bases. For brevity, we omit the r-interval {i, 5, 6, . . . , r + 3}, with i = 4, which is a basis (compare it to H 1 ). Since the permutations σ i below differ from σ 1 in at most four consecutive places, the assumption that the nullity of M is at least three implies that an r-interval in σ i cannot differ from its counterpart in σ 1 at both ends.
Consider . . , c i−1 } is a basis; such cycles are said to start properly. We say that a problem occurs at c i if {c i , c i+1 , . . . , c r , b 1 , . . . , b i−1 } is not a basis; clearly, i > 1. We will show how, if a problem occurs at c i , then we can switch a few elements so that the number of problems decreases and the cycle starts properly; iterating this procedure produces the desired cycle.
First assume 1 < i < r. We will show that one of the following cycles starts properly and has fewer problems (we underline the few elements that are permuted): . . , c i−1 }, is a basis, then σ 2 starts properly and has fewer problems than σ, so we may assume that S 2 is also a circuithyperplane. Four r-intervals in σ 3 differ from their counterparts in σ, namely, and their complements. Each of these sets is a basis by Lemma 2.1 since each symmetric difference T 1 △S 0 , T 2 △S 0 , (E(M ) − T 1 )△S 1 , and (E(M ) − T 2 )△S 2 has two elements, so σ 3 starts properly and has fewer problems than σ. Now assume i = r, so S 0 = {c r , b 1 , . . . , b r−1 } is a circuit-hyperplane. Consider An argument similar to that above shows that σ 1 starts properly and has fewer problems than σ unless S 1 = {b r , c 1 , c 2 , . . . , c r−2 , c r } is a circuit-hyperplane; likewise, σ 2 starts properly and has fewer problems than σ unless S 2 = {b r−1 , c 1 , c 2 , . . . , c r−1 } is a circuithyperplane. Assume both S 1 and S 2 are circuit-hyperplanes. Only four r-intervals in σ 3 differ from their counterparts in σ, namely:

SPARSE PAVING MATROIDS AND THE NUMBER OF CYCLIC FLATS
A set X in a matroid M is cyclic if M |X has no coloops. Such sets are precisely the (possibly empty) unions of circuits of M . Let Z(M ) be the set of cyclic flats of M . As noted in [7], the cyclic flats, along with their ranks, determine the matroid; indeed, this data can be seen as distilling the essential geometric information about a matroid (see [2,3] for constructions that exploit this perspective). Cyclic flats play many roles in matroid theory, especially in the theory of transversal matroids (see, e.g., [4,5,7,16]).
Let z n be max{|Z(M )| : |E(M )| = n}, that is, z n is the greatest number of cyclic flats that any matroid on n elements can have. In [6], the problem of finding z n was raised. The importance of this problem stems from the fact that cyclic flats and their ranks generally provide a relatively compact description of a matroid.
To deduce a simple upper bound on z n , let a i be the number of i-element cyclic flats in a matroid M with |E(M )| = n. Note that for F ∈ Z(M ) and e ∈ F , the closure cl(F − e) is F ; also, for x ∈ E(M ) − F , the restriction M |(F ∪ x) has a unique coloop, namely x. It follows that the sets F and F − e, with F ∈ Z(M ) and e ∈ F , all differ, as do the sets Adding these inequalities gives (n + 2) |Z(M )| ≤ 2 n+1 , so z n ≤ 2 n+1 /(n + 2). We next review a construction that yields sparse paving matroids in which the number of cyclic flats is not so far from this bound. As mentioned in Section 1, Knuth [20] constructed a family of at least 2 ( n ⌊n/2⌋ )/2n /n! nonisomorphic sparse paving matroids of rank ⌊n/2⌋ on n elements. To do this, he showed that there is a sparse paving matroid of rank ⌊n/2⌋ on n elements with at least n ⌊n/2⌋ /2n circuit-hyperplanes; the circuit-hyperplane relaxations of this matroid, taking into account potential isomorphisms, give the family.
While exploring an equivalent problem in the context of coding theory, Graham and Sloane [13] generalized and strengthened Knuth's result by showing that for each rank r with r ≤ n, there is a sparse paving matroid of rank r on n elements with at least n r /n circuit-hyperplanes. Their construction, which we sketch, has the same general flavor as Knuth's. Partition the set of all 0-1 vectors (a 0 , a 1 , . . . , a n−1 ) of length n with r ones into n classes according to the remainder, modulo n, of the sum of the positions that contain ones, i.e., i a i i. They noted that any two vectors in the same class differ in at least four places. At least one of the classes has at least n r /n vectors; by interpreting these vectors as the characteristic functions of the circuit-hyperplanes, this class defines a sparse paving matroid with at least n r /n circuit-hyperplanes. The cyclic flats of a sparse paving matroid M having rank and nullity at least two are ∅, E(M ), and its circuit-hyperplanes. A routine induction (treating even n and odd n separately) shows n ⌊n/2⌋ ≥ 2 n−1 / √ n (consistent with Stirling's approximation). Thus, it follows from Graham and Sloane's work that some sparse paving matroid on n elements has at least 2 n−1 /n 3/2 + 2 cyclic flats. (For large n, the numbers of cyclic flats in these examples far surpass those mentioned in [6].) We summarize these remarks in the result below, which, if we apply log 2 to each term in the inequality, bears a strong resemblance to inequality (1.1).
To close, we note that Graham and Sloane's examples cannot be substantially improved upon within the class of sparse paving matroids. The sparse paving matroids that they construct have n ⌊n/2⌋ /n circuit-hyperplanes. It is routine to check that the right side of inequality (2.1) above is maximized when r = ⌊n/2⌋. The ratio of this upper bound to the number of circuit-hyperplanes in Graham and Sloane's examples tends to 2 as n goes to infinity. (Also see [13,Remark 2].) This supports the natural suspicion that the lower bound in Theorem 3.1 is close to optimal.