Séminaire Lotharingien de Combinatoire 51 (2004), Article B51g

ON THE NUMBER OF MATROIDS ON A FINITE SET

W. M. B. DUKES

Abstract. In this paper we highlight some enumerative results concerning matroids of low rank and prove the tail-ends of various sequences involving the number of matroids on a finite set to be log-convex. We give a recursion for a new, slightly improved, lower bound on the number of rank-r matroids on n elements when n = 2^{m} − 1. We also prove an adjacent result showing the point-lines-planes conjecture to be true if and only if it is true for a special subcollection of matroids. Two new tables are also presented, giving the number of paving matroids on at most eight elements.

1. Definitions

Let S_{n} be a finite set of size n. A matroid M is a pair M(S_{n}, B) such that B is a non-empty collection of subsets of S_{n} satisfying the following basis-exchange property:

∀ X, Y ∈ B, ∀x ∈ X − Y, ∃y ∈ Y − X s.t X − {x} ∪ {y} ∈ B.

S_{n} is called the ground set of the matroid and B the collection of bases. A consequence of this axiom is that all sets in B have the same cardinality, called the rank of the matroid. The collection of independent sets of M is I(M) = {I : I ⊆ B, B ∈ B(M)}. An element x ∈ S_{n} is called a loop if {x} ∉ I(M). If for every pair of distinct elements {x, y} ⊆ S_{n} there exists I ∈ I(M) s.t. I ⊇ {x, y}, then M is called a simple.

Let 𝕄_{r}^{k}(S_{n}) be the class of rank-r matroids on S_{n} with all k-element sets independent, non-empty for all 0 ⩽ k ⩽ r ⩽ n, and the union of these classes over k ⩽ r ⩽ n is denoted 𝕄^{k}(S_{n}). We say two matroids M_{1}(S_{n}, B_{1}) and M_{2}(S_{n}, B_{2}) are isomorphic if there exists a permutation π of S_{n} such that B_{2} = {π(B) : B ∈ B_{1}}. Let M_{r}^{k}(S_{n}) and M^{k}(S_{n}) be the corresponding classes of non-isomorphic matroids (i.e. ‘different’ matroids). The collections 𝕄_{r}^{0}(S_{n}), 𝕄_{r}^{1}(S_{n}) and 𝕄_{r}^{2}(S_{n}) identify the classes of rank-r matroids, loopless matroids and simple matroids, respectively, on S_{n}. 𝕄_{r}^{r−1}(S_{n}) is the class of rank-r paving matroids on S_{n} and the single matroid in 𝕄_{r}^{r}(S_{n}) is the uniform rank-r matroid on n elements. Note that 𝕄_{r}^{i+1}(S_{n}) ⊂ 𝕄_{r}^{i}(S_{n}) for all 0 ⩽ i < r. Given M ∈ 𝕄_{r}^{0}(S_{n}) and X ⊆ S_{n}, the restriction of M to X, denoted M|X, is the matroid with independent sets {I ∩ X : I ∈ I(M)}. The dual of M is the matroid M^{⋆} ∈ 𝕄_{n−r}^{0}(S_{n}) with B(M^{⋆}) := {S_{n} − B : B ∈ B(M)}.

2000 Mathematics Subject Classification. 05B35.

Key words and phrases. Matroid, enumeration, paving matroid, points-lines-planes conjecture, free erection.

Supported by EC’s Research Training Network ‘Algebraic Combinatorics in Europe’, grant HPRN-CT-2001-00272 while the author was at the Università di Roma Tor Vergata, Italy.

The rank of A ⊆ S_{n} is defined by r(A) := max{|X| : X ⊆ A, X ∈ I(M)}. We call A ⊆ S_{n} a flat if r(A ∪ {x}) = r(A) + 1 for all x ∈ S_{n} − A. We denote by F_{k}(M) the collection of rank-k flats of M and the numbers W_{k}(M) := |F_{k}(M)| are called the Whitney numbers of the second kind. We may also define a matroid in terms of its flats: the pair M(S_{n}, F = {F_{0}, F_{1}, …, F_{r}}) is a matroid if for all 0 ⩽ i < r and F_{i} ∈ F_{i}, the collection {X − F_{i} : X ∈ F_{i+1} and X ⊃ F_{i}} partitions the set S_{n} − F_{i}.

For a general matroid M, the relationship between the collection of flats and independent sets may be seen as follows: a set F is in F(M) if I ∪ {x} ∈ I(M) whenever I ⊆ F, I ∈ I(M) and x ∉ F. Conversely, a set I is in I(M) if for every x ∈ I, I − F = {x} for some F ∈ F(M).

The upper truncation U_{k}(M) of M ∈ 𝕄_{r}^{0}(S_{n}) is the matroid obtained by removing the rank-i flats of M for k ⩽ i < r. The resulting matroid is a rank-k matroid. Given N ∈ 𝕄_{r}^{0}(S_{n}) and M ∈ 𝕄_{r+1}^{0}(S_{n}), we say M is an erection of N if U_{r}(M) = N.

A collection H of subsets of S_{n} is a d-partition of S_{n} if every d-set of S_{n} is contained in a unique set of H and |H| ⩾ d for all H ∈ H. We call the dpartition trivial if H = {S_{n}}.

2. Enumerative results and conjectures

Several papers and books addressing the number of matroids on a finite set have used the terms ‘number of matroids’ where ‘number of non-isomorphic matroids’ or ‘number of non-isomorphic simple matroids’ was intended. The tightest bounds on the total number of matroids (i.e., fixing n and summing over r) are to be found in Knuth [12] and Piff and Welsh [19]. Some surprising recent work gives the asymptotics for the number of binary matroids, see Wild [24]. Also, the longstanding conjecture of Welsh [23] that |M^{0}(S_{m+n})| ⩾ |M^{0}(S_{m})||M^{0}(S_{n})| has recently been proved independently by Lemos [15] and Crapo and Schmitt [8].

To resolve the confusion regarding what the term ‘number of matroids’ means, in this paper we will distinguish between the six classes: 𝕄_{r}^{0}(S_{n}) , 𝕄_{r}^{1}(S_{n}) , 𝕄_{r}^{2}(S_{n}) , M_{r}^{0}(S_{n}), M_{r}^{1}(S_{n}) and M_{r}^{2}(S_{n}).

To align our notation with the the standard literature on this subject, let us mention the following; Crapo [5] gives the first 4 numbers in the |M^{2}(S_{n})| row of the table for |M_{r}^{2}(S_{n})| in Section 5. The table for |M_{r}^{2}(S_{n})| was first given in Blackburn, Crapo and Higgs [4] and is reprinted in Welsh [21, p.306]. The table |M_{r}^{0}(S_{n})| was first given in Acketa [3], extending earlier results from Acketa [2], and is reprinted at the back of Oxley’s book [18]. The numbers enumerated in Acketa [1] were |M_{2}^{0}(S_{n})|.

Let p(i) be the number of partitions of the integer i, \left\{{n \atop i}\right\} the Stirling numbers of the second kind and b(i) the i^{th} Bell number. Through consideration of the loops and points of general matroids, we have the following relations: |M_{0}^{0}(S_{n})| = 1, |𝕄_{0}^{0}(S_{n}) | = 1, |𝕄_{1}^{1}(S_{n}) | = 1, |M_{1}^{1}(S_{n})| = 1, |𝕄_{n}^{2}(S_{n}) | = 1, |M_{n}^{2}(S_{n})| = 1,

|𝕄_{r}^{0}(S_{n}) | = ∑_{i=r}^{n} \binom{n}{i}|𝕄_{r}^{1}(S_{i}) |,

|𝕄_{r}^{1}(S_{n}) | = ∑_{i=r}^{n} \left\{{n \atop i}\right\}|𝕄_{r}^{2}(S_{i}) |,

|M_{r}^{0}(S_{n})| = ∑_{i=r}^{n} |M_{r}^{1}(S_{i})|.

Using these equalities, we have the following closed forms for certain low-rank matroids:

Theorem 2.1 (Dukes [11]). For all n ⩾ 2, (i) |M_{1}^{0}(S_{n})| = n, |M_{2}^{0}(S_{n})| = p(1) + ⋯ + p(n) − n, (ii) |𝕄_{1}^{0}(S_{n}) | = 2^{n} − 1, |𝕄_{2}^{0}(S_{n}) | = b(n + 1) − 2^{n}, (iii) |𝕄_{2}^{1}(S_{n}) | = b(n) − 1, |M_{2}^{1}(S_{n})| = p(n) − 1.

By duality we can also enumerate high-rank matroids as the following lemma shows:

Lemma 2.2. For all n ⩾ 5, (i) |𝕄_{n−1}^{2}(S_{n}) | = 2^{n} − 1 − \binom{n+1}{2}, (ii) |M_{n−1}^{2}(S_{n})| = n − 2, (iii) |𝕄_{n−2}^{2}(S_{n}) | = b(n + 1) + \binom{n+3}{4} + 2\binom{n+1}{4} − 2^{n} − \binom{n+1}{2}2^{n−1}, (iv) |M_{n−2}^{2}(S_{n})| = p(1) + … + p(n) + 6 − 4n.

Proof. A matroid M ∈ 𝕄_{n−1}^{2}(S_{n}) is specified by a unique circuit of length k for some 3 ⩽ k ⩽ n, the elements not contained in this circuit are the isthmuses of M. If B(M^{⋆}) = {{x_{1}}, …, {x_{k}}} then this circuit is C = {x_{1}, …, x_{k}} and the number of ways to choose such a circuit is simply the number of subsets of S_{n} of size at least 3, hence |𝕄_{n−1}^{2}(S_{n}) | = 2^{n} − 1 − n − \binom{n}{2}. The corresponding non-isomorphic number is |M_{n−1}^{2}(S_{n})| = (n + 1) − 3 = n − 2.

If M ∈ 𝕄_{2}^{0}(S_{n}) then M^{⋆} ∈ 𝕄_{n−2}^{0}(S_{n}). Suppose F_{0}(M) = {F_{0}} and F_{1}(M) = {H_{1}, …, H_{k}}. Let F_{i} = H_{i} − F_{0} for all 1 ⩽ i ⩽ k. Then {F_{0}, F_{1}, …, F_{k}} partitions the set S_{n}. M^{⋆} is not simple iff there exists X ∈ \binom{S_{n}}{n−2} such that for all (f_{i}, f_{j}) ∈ F_{i} × F_{j} with 0 < i < j, {f_{i}, f_{j}} ⊄ X. It transpires that M^{⋆} is not simple if

• k = 2 and (|F_{1}| = 1, |F_{2}| ⩾ 1) or (|F_{1}| = 2, |F_{2}| ⩾ 2),
• k = 3, |F_{1}| = |F_{2}| = 1 and |F_{3}| ⩾ 1,

and relabellings thereof. Enumerating this class of matroids whose duals are not simple gives:

∑_{i=0}^{n−2} \binom{n}{i}(n − i) − \binom{n}{n − 2} + 3\binom{n}{4} + ∑_{i=5}^{n} \binom{n}{i}\binom{i}{2} + \binom{n}{3} + ∑_{i=4}^{n} \binom{n}{i}\binom{i}{2}

= \binom{n + 1}{2}2^{n−1} − \binom{n + 3}{4} − 2\binom{n + 1}{4}.

Thus

|𝕄_{n−2}^{2}(S_{n}) | = |𝕄_{2}^{0}(S_{n}) | − \{\binom{n + 1}{2}2^{n−1} − \binom{n + 3}{4} − 2\binom{n + 1}{4}\}
= b(n + 1) − 2^{n} − \binom{n + 1}{2}2^{n−1} + \binom{n + 3}{4} + 2\binom{n + 1}{4}

and the corresponding non-isomorphic number is

|M_{n−2}^{2}(S_{n})| = |M_{2}^{0}(S_{n})| − (n − 1) − (n − 3) − (n − 2)
= p(1) + … + p(n) − n − 3(n − 2).
□

A well cited conjecture (proposed by Welsh [22]) states that the number of ‘different’ matroids on S_{n} (i.e. |M_{r}^{0}(S_{n})|) is unimodal in rank. It seems unfair to restrict this conjecture to only one of the six classes of matroids so we propose;

Conjecture 2.3. The sequences {|𝕄_{r}^{0}(S_{n}) |}_{r=0}^{n}, {|𝕄_{r}^{1}(S_{n}) |}_{r=1}^{n}, {|𝕄_{r}^{2}(S_{n}) |}_{r=2}^{n}, {|M_{r}^{0}(S_{n})|}_{r=0}^{n}, {|M_{r}^{1}(S_{n})|}_{r=1}^{n} and {|M_{r}^{2}(S_{n})|}_{r=2}^{n} are unimodal and attain their maximum at r = ⌈n/2⌉.

The following theorem summarizes partial progress with this conjecture.

Theorem 2.4 (Dukes [9]). For all n ⩾ 6, (i) |𝕄_{0}^{0}(S_{n}) | ⩽ |𝕄_{1}^{0}(S_{n}) | ⩽ |𝕄_{2}^{0}(S_{n}) | ⩽ |𝕄_{3}^{0}(S_{n}) |, (ii) |M_{0}^{0}(S_{n})| ⩽ |M_{1}^{0}(S_{n})| ⩽ |M_{2}^{0}(S_{n})| ⩽ |M_{3}^{0}(S_{n})|, (iii) |𝕄_{1}^{1}(S_{n}) | ⩽ |𝕄_{2}^{1}(S_{n}) | ⩽ |𝕄_{3}^{1}(S_{n}) |, (iv) |M_{1}^{1}(S_{n})| ⩽ |M_{2}^{1}(S_{n})| ⩽ |M_{3}^{1}(S_{n})|,

(v) |𝕄_{2}^{2}(S_{n}) | ⩽ |𝕄_{3}^{2}(S_{n}) |, (vi) |M_{2}^{2}(S_{n})| ⩽ |M_{3}^{2}(S_{n})|.

In problems involving unimodal sequences, it is sometimes easier to show a sequence to be log-concave and therefore unimodal. It is not clear that the sequences {|𝕄_{r}^{0}(S_{n}) |}_{r=0}^{n}, {|𝕄_{r}^{1}(S_{n}) |}_{r=1}^{n}, {|𝕄_{r}^{2}(S_{n}) |}_{r=2}^{n}, {|M_{r}^{0}(S_{n})|}_{r=0}^{n}, {|M_{r}^{1}(S_{n})|}_{r=1}^{n} and {|M_{r}^{2}(S_{n})|}_{r=2}^{n} are log-concave. The evidence in the tables would seem to suggest log-concavity. However, this is only the case for n small. We exhibit the following theorem which shows the beginning (in some cases the end) of these sequences to be log-convex once n is sufficiently large. First we require two lower bounds to aid the proof.

Theorem 2.5 (Dukes [10]). For all 2 < r < n, |𝕄_{r}^{r−1}(S_{n}) | > 2^{\binom{n}{r}/2n} and |M_{r}^{r−1}(S_{n})| > \frac{1}{n!}2^{\binom{n}{r}/2n}.

Theorem 2.6. The matroid numbers satisfy the following inequalities (i) |𝕄_{0}^{0}(S_{n}) ||𝕄_{2}^{0}(S_{n}) | > |𝕄_{1}^{0}(S_{n}) |^{2} for all n ⩾ 4, (ii) |M_{0}^{0}(S_{n})||M_{2}^{0}(S_{n})| > |M_{1}^{0}(S_{n})|^{2} for all n ⩾ 9, (iii) |𝕄_{1}^{1}(S_{n}) ||𝕄_{3}^{1}(S_{n}) | > |𝕄_{2}^{1}(S_{n}) |^{2} for all n ⩾ 94, (iv) |M_{1}^{1}(S_{n})||M_{3}^{1}(S_{n})| > |M_{2}^{1}(S_{n})|^{2} for all n ⩾ 67,

(v) |𝕄_{n−2}^{2}(S_{n}) ||𝕄_{n}^{2}(S_{n}) | > |𝕄_{n−1}^{2}(S_{n}) |^{2} for all n ⩾ 11, (vi) |M_{n−2}^{2}(S_{n})||M_{n}^{2}(S_{n})| > |M_{n−1}^{2}(S_{n})|^{2} for all n ⩾ 8.

Proof. Each follows from combining known closed forms, and in some cases inequalities, for the numbers and using induction. The first and second inequalities follow directly from Theorem 2.1. The third inequality follows since

|𝕄_{1}^{1}(S_{n}) ||𝕄_{3}^{1}(S_{n}) | > |𝕄_{3}^{2}(S_{n}) | > 2^{(n−1)(n−2)/12},

by using Theorem 2.5 with r = 3. It can then be verified that

2^{(n−1)(n−2)/12} > (b(n) − 1)^{2} = |𝕄_{2}^{1}(S_{n}) |^{2}

for all n ⩾ 94. Similarly, the fourth inequality follows from applying the same method but by using the non-isomorphic lower bound of Theorem 2.5. The final two inequalities follow from Lemma 2.2. Some of the inequalities also hold for smaller values of n. □

The above sequences are much more likely to resemble the sequence \{2^{\binom{n}{r}}\}_{r=0}^{n} which is log-convex at both ends of the sequence and has a log-concave ‘cap’ in the middle.

3. Lower bound on the number of paving matroids

The tightest asymptotic lower bound for the number of matroids was given in Knuth [12]. The method involved proving a lower bound on the number of rank- ⌊n/2⌋ paving matroids on S_{n}. Theorem 2.5 showed his lower bound inequality to hold for 2 < r < n ( [12] proved the case r = ⌊n/2⌋) giving a lower bound on the number of (r − 1)-partitions of S_{n}. The class of non-trivial (r − 1)-partitions corresponds directly to the class of rank-r paving matroids. It was noted in Dukes [10] that experimental results suggested a particular class of the partitions to be larger than each of the other classes. The following lemma gives a recursion for the enumeration of this class, hence the tightest lower bound possible using this approach when the size of the ground set is of the form 2^{m} − 1.

Theorem 3.1. If n = 2^{m} − 1 for some m ∈ ℕ, then |𝕄_{r}^{r−1}(S_{n}) | ⩾ 2^{|U(r,n)|} for all r ⩾ 4 where |U(r, n)| satisfies the recursion:

|U(r + 1, n)| = \frac{1}{r + 1} (\binom{n}{r} − |U(r, n)| − (n − r + 1)|U(r − 1, n)|)

with initial values |U(3, n)| = \binom{n}{3}/(n − 2) and |U(4, n)| = \binom{n}{4}/(n − 2).

Proof. Let n = 2^{m}−1. Given an integer i, let i⃗ be its binary representation. Given two integers i, j, let i ⊕ j be binary addition in ℤ_{2}. In this proof we assume the set S_{n} = {1, 2, …, n}. Let U(r, n) := {{i_{1}, ⋯, i_{r}} ⊂ S_{n} : i⃗_{1} ⊕⋯⊕i⃗_{r} = 0}. Since n = 2^{m}−1, all possible binary vectors, except the 0 vector, of length m are possible in U(r, n). It is clear that if A, B ∈ U(r, n) and A ≠ B, then |A ∩ B| ⩽ r − 2. For otherwise there must exist i_{1}, …, i_{r−1}, i_{r}, i_{r+1} such that A = {i_{1}, …, i_{r−1}, i_{r}} and B = {i_{1}, …, i_{r−1}, i_{r+1}}. This gives i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r−1} = i⃗_{r} = i⃗_{r+1}. But since i_{r} and i_{r+1} are distinct, this is a contradiction.

Thus if we take any subset V ⊆ U(r, n), and then insert into V all those r − 1 element subsets of S_{n} which are not contained in any member of V, the resulting collection will be a (r − 1)-partition of S_{n} and hence represents the hyperplanes of a rank-r paving matroid on S_{n}. There are 2^{|U(r,n)|} choices for V, hence we have |𝕄_{r}^{r−1}(S_{n}) | ⩾ 2^{|U(r,n)|}. It is now required to find |U(r, n)|,

|U(r + 1, n)|
= |{{i_{1}, ⋯, i_{r+1}} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r+1} = 0}|
= \frac{1}{r + 1}|\{\{i_{1}, ⋯, i_{r}\} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r} = z⃗, z ∈ S_{n} − \{i_{1}, …, i_{r}\}\}|
= \frac{1}{r + 1} (|\{\{i_{1}, ⋯, i_{r}\} ⊂ S_{n}\}|
−|{{i_{1}, ⋯, i_{r}} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r} = z⃗, z ∈ {0, i_{1}, …, i_{r}}}|)
= \frac{1}{r + 1} (\binom{n}{r} − |\{\{i_{1}, ⋯, i_{r}\} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r} = 0\}|
−|{{i_{1}, ⋯, i_{r}} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r} = z⃗, z ∈ {i_{1}, …, i_{r}}}|)
= \frac{1}{r + 1} (\binom{n}{r} − |U(r, n)|
−(n − (r − 1))|{{i_{1}, ⋯, i_{r−1}} ⊂ S_{n} : i⃗_{1} ⊕ ⋯ ⊕ i⃗_{r−1} = 0}|)
= \frac{1}{r + 1} (\binom{n}{r} − |U(r, n)| − (n − r + 1)|U(r − 1, n)|) .

The initial conditions for this recursion are |U(3, n)| = \binom{n}{3}/(n−2) and |U(4, n)| = \binom{n}{4}/(n−2). U(3, n) of course corresponds to certain 2-partitions of S_{n}, which are the hyperplanes of rank-3 paving matroids. □

4. Concerning the points-lines-planes conjecture

The following conjecture is stated in Seymour [20]. Originally Welsh [21, p.289] introduced the phrase ‘Points-lines-planes conjecture’ for the k = 2 instance of Mason [16, Conjecture 1C]. In the current form it is actually the k = 2 instance of the slightly more general Mason [16, Conjecture 1D].

Conjecture 4.1 (Points-Lines-Planes). For all M ∈ 𝕄_{4}^{2}(S_{n}),

W_{2}(M)^{2} ⩾ \frac{3(W_{1}(M) − 1)}{2(W_{1}(M) − 2)}W_{1}(M)W_{3}(M),

with equality if and only if F_{3}(M) = \binom{S_{n}}{3}.

The most general case proven so far is:

Theorem 4.2 (Seymour [20]). The points-lines-planes conjecture is true for all {M ∈ 𝕄_{4}^{2}(S_{n}) : |F | ⩽ 4 for all F ∈ F_{2}(M)}.

Let us also mention that in related work, Kung [14] proved that if M is a simple matroid of rank at least 5, in which all lines contain the same number of points, then W_{2}(M) ⩽ W_{3}(M).

The purpose of this section is to prove that the points-lines-planes conjecture is true for all simple rank-4 matroids if and only if it is true for a special subcollection of them.

Let us briefly outline Knuth’s [13] algorithm for constructing all matroids on the finite set S_{n} (i.e., for constructing the class ∪_{r=1}^{n}𝕄_{r}^{1}(S_{n})). We restate the algorithm in a slightly different way to the original paper. Let T be a collection of subsets of S_{n}. Let Expand(T ) := {A ∪ a : A ∈ T and a ∈ S_{n} − A}. Let Random(T ) be a collection of random sets where each random set properly contains some member of T . Let Refine(T , T′) be the collection of sets T obtained after applying the following:

Repeat until A ∩ B ⊆ C for some C ∈ T′ for all A, B ∈ T : if A, B ∈ T , A ≠ B and A ∩ B ⊈ C for any C ∈ T′ then replace A and B in T by the set A ∪ B.

Knuth’s random matroids algorithm

(1) Let r = 0 and F_{0} = {∅}.

(2) Let A = Expand(F_{r}) ∪ Random(F_{r}).
(3) Let F_{r+1} = Refine(A, F_{r}).

(4) If S_{n} ∈ F_{r+1} then let F = F_{0} ∪ … ∪ F_{r+1} and Stop. Otherwise let r = r + 1 and go to step (2).

Theorem 4.3 (Knuth [13]).

(i) The resulting collection F is the collection of flats of a matroid on S_{n}. (ii) The resulting matroid obtained from the algorithm does not depend on the

order of replacements in Refine(A, F_{r}). (iii) Every matroid in ∪_{r=1}^{n}𝕄_{r}^{1}(S_{n}) is obtainable using this algorithm.

Let M be a simple rank-(r + 1) matroid on S_{n} with hyperplanes F_{r}, and let F′_{r+1} = Refine(Expand(F_{r}) ∪ Random(F_{r}), F_{r}). The matroid M′ with flats F(M) ∪ F′_{r+1} is an erection of M. If M′ = M (this happens if F′_{r+1} = {S_{n}}) then M′ is the trivial erection. If Random(F_{r}) = ∅, then the resulting matroid M′ is termed the free erection of M, denoted Free(M).

The free erection was first defined in Crapo [6] and an alternative construction of it can be found in Nguyen [17]. We prove the following result using the operations defined above. An alternative proof may be given using the results and terminology of [6, 17].

Theorem 4.4. The points-lines-planes conjecture is true if and only if it is true for the class of rank-4 matroids that are the free erection of some rank-3 matroid.

Proof. If the points-lines-planes conjecture is true, then clearly it is true for all those rank-4 matroids that are the free erection of some rank-3 matroid, i.e. {Free(M) : M ∈ 𝕄_{3}^{2}(S_{n}), Free(M) ≠ M} ⊂ 𝕄_{4}^{2}(S_{n}).

Conversely, suppose the points-lines-planes conjecture is true for all {Free(M) : M ∈ 𝕄_{3}^{2}(S_{n}), Free(M) ≠ M}. Every matroid N ∈ 𝕄_{4}^{2}(S_{n}) is the erection of some M ∈ 𝕄_{3}^{2}(S_{n}), that is to say, if M = U_{3}(N) then there exists a collection Random(F_{2}(M)) (not necessarily unique) such that

F_{3}(N) = Refine(Expand(F_{2}(M)) ∪ Random(F_{2}(M)), F_{2}(M)).

We now show that for all matroids M ∈ 𝕄_{3}^{2}(S_{n}),

|Refine(Expand(F_{2}(M)) ∪ Random(F_{2}(M)), F_{2}(M))| ⩽ |F_{3}(Free(M))|.

Let M ∈ 𝕄_{3}^{2}(S_{n}) with F_{2}(M) = F_{2}, so that

F_{3}(N) := Refine(Expand(F_{2}) ∪ Random(F_{2}), F_{2}).

Consider the collections Refine(Expand(F_{2}) ∪ Random(F_{2}), F_{2}) and Refine(Expand(F_{2}), F_{2}). Let Expand(F_{2}) = {E_{1}, …, E_{m}} and define E′_{i} = E_{i} for all 1 ⩽ i ⩽ m. For each 1 ⩽ i ⩽ m, if X ∈ Random(F_{2}) and X ⊇ E_{i}, then let E′_{i} = E′_{i} ∪X and remove X from Random(F_{2}). Once Random(F_{2}) is empty, we have E_{i} ⊆ E′_{i} for all i.

Recall from Theorem 4.3 that if A is a well defined collection in terms of F_{2}, then Refine(A−{A_{1}, A_{2}}∪Refine({A_{1}, A_{2}}, F_{2}), F_{2}) = Refine(A−{A_{3}, A_{4}}∪ Refine({A_{3}, A_{4}}, F_{2}), F_{2}) for all A_{1}, A_{2}, A_{3}, A_{4} ∈ A s.t. A_{1} ≠ A_{2} and A_{3} ≠ A_{4}.

For each E_{i}, E_{j} ∈ Expand(F_{2}), if Refine({E_{i}, E_{j}}, F_{2}) = {E_{i} ∪ E_{j}} then Refine({E′_{i} ∪ E′_{j}}, F_{2}) = {E′_{i} ∪ E′_{j}} since E_{i} ∩ E_{j} ⊆ E′_{i} ∩ E′_{j}. Hence, Refine({E_{1}, …, E_{m}}, F_{2}) has at least as many sets as

Refine({E′_{1}, …, E′_{m}}, F_{2}) = Refine(Expand(F_{2}) ∪ Random(F_{2}), F_{2})

and so

W_{3}(N) = |Refine(Expand(F_{2}(M)) ∪ Random(F_{2}(M)), F_{2}(M))|
⩽ |Refine(Expand(F_{2}(M)), F_{2}(M))|
= W_{3}(Free(M)).

Since W_{2}(M) = W_{2}(N) and W_{1}(M) = W_{1}(N), the result follows. □

Let us also observe that since every plane (rank-3 flat) is determined by two unique lines (rank-2 flats), W_{3}(M) ⩽ W_{2}(M)^{2}/2. The benefit of Theorem 4.4 is apparent by considering the number of simple rank-3 matroids having non-trivial erections relative to the number of simple rank-4 matroids. Using Theorem 2.5 we have

|𝕄_{4}^{2}(S_{n}) | ⩾ |𝕄_{4}^{3}(S_{n}) | ⩾ 2^{\binom{n}{4}/2n}

and

|\{Free(M) : M ∈ 𝕄_{3}^{2}(S_{n}), Free(M) ≠ M\} | ⩽ |𝕄_{3}^{2}(S_{n}) | ⩽ 2^{\binom{n}{3}},

since all rank-3 matroids are uniquely expressible by their collection of bases, a subset of \binom{S_{n}}{3}. Hence

\frac{|\{Free(M) : M ∈ 𝕄_{3}^{2}(S_{n}), Free(M) ≠ M\} |}{|𝕄_{4}^{2}(S_{n}) |} ⩽ 2^{−(7n+3)(n−1)(n−2)/48}.

5. Numerical values

As mentioned in Section 2, the tables for |M_{r}^{2}(S_{n})| and |M_{r}^{0}(S_{n})| were first given in Blackburn, Crapo and Higgs [4] and Acketa [3], respectively. These two tables along with the tables for |𝕄_{r}^{0}(S_{n}) |, |𝕄_{r}^{1}(S_{n}) |, |M_{r}^{1}(S_{n})| and |𝕄_{r}^{2}(S_{n}) | were given in Dukes [11]. A modification to the program used to generate these gives the two new tables for the number of paving matroids, |𝕄_{r}^{r−1}(S_{n}) |, and non-isomorphic paving matroids, |M_{r}^{r−1}(S_{n})| on at most eight elements.

10 W. M. B. DUKES

|𝕄_{r}^{0}(S_{n}) |

r \ n 0 1 2 3 4  5  6  7  8
0 1 1 1 1 1  1  1  1  1
1  1 3 7 15 31  63  127  255
2  1 7 36 171 813 4012  20891
3  1 15 171 2053 33442 1022217
4  1 31 813 33442 8520812
5  1  63  4012 1022217
6  1  127  20891
7  1  255
8  1
|𝕄^{0}(S_{n}) | 1 2 5 16 68 406 3807 75164 10607540

|M_{r}^{0}(S_{n})|

r \ n 0 1 2 3 4 5 6  7  8
0 1 1 1 1 1 1 1  1  1
1  1 2 3 4 5 6  7  8
2  1 3 7 13 23 37  58
3  1 4 13 38 108 325
4  1 5 23 108 940
5  1 6 37 325
6  1  7  58
7  1  8
8  1
|M^{0}(S_{n})| 1 2 4 8 17 38 98 306 1724

|𝕄_{r}^{1}(S_{n}) |

r \ n 1 2 3 4  5  6  7  8
1 1 1 1 1  1  1  1  1
2  1 4 14 51 202  876  4139
3  1 11 106 1232 22172 803583
4  1 26 642 28367 8274374
5  1  57  3592  991829
6  1  120  19903
7  1  247
8  1
|𝕄^{1}(S_{n}) | 1 2 6 27 165 2135 55129 10094077

|M_{r}^{1}(S_{n})|

r \ n 1 2 3 4 5 6  7  8
1 1 1 1 1 1 1  1  1
2  1 2 4 6 10 14  21
3  1 3 9 25 70 217
4  1 4 18 85 832
5  1 5 31 288
6  1  6  51
7  1  7
8  1
|M^{1}(S_{n})| 1 2 4 9 21 60 208 1418

|𝕄_{r}^{2}(S_{n}) |
r \ n 2 3 4 5  6  7  8
2 1 1 1 1  1  1  1
3  1 5 31 352 8389 433038
4  1 16 337 18700 7642631
5  1 42 2570 907647
6  1  99  16865
7  1  219
8  1
|𝕄^{2}(S_{n}) | 1 2 7 49 733 29760 9000402
|M_{r}^{2}(S_{n})|
r \ n 2 3 4 5 6  7  8
2 1 1 1 1 1  1  1
3  1 2 4 9 23 68
4  1 3 11 49 617
5  1 4 22 217
6  1  5  40
7  1  6
8  1
|M^{2}(S_{n})| 1 2 4 9 26 101 950
|𝕄_{r}^{r−1}(S_{n}) |  |M_{r}^{r−1}(S_{n})|
r \ n 2 3 4 5  6  7  8  2 3 4 5 6 7  8
2 1 1 1 1  1  1  1  1 1 1 1 1 1  1
3  1 5 31 352 8389 433038  1 2 4 9 23 68
4  1 6 82 6149 4464328  1 2 5 18 322
5  1  7  239  239173  1 2 5 39
6  1  8  772  1 2  6
7  1  9  1  2
8  1  1
Total 1 2 7 39 443 14787 5137322 1 2 4 8 18 50 439

The program is freely available by e-mailing the author. It is written in the C-programming language and is easily compiled on FreeBSD and Linux platforms.

Acknowledgments

The author would like to thank Francesco Brenti and the anonymous referee for helpful comments, and Christian Krattenthaler for an interesting suggestion. This work was funded by the Research Training Network ‘Algebraic Combinatorics in Europe’, grant HPRN-CT-2001-00272.

References

[1] D. M. Acketa, On the enumeration of matroids of rank-2, Zbornik radova Prirodnomatematickog fakulteta – Univerzitet u Novom Sadu., 8 (1978), 83–90.

[2] D. M. Acketa, On the construction of all matroids on 7 elements at most, Zbornik radova Prirodno-matematickog fakulteta – Univerzitet u Novom Sadu., 8 (1979), 133–152.

[3] D. M. Acketa, A construction of non-simple matroids on at most 8 elements, J. Combin. Inform. System Sci. 9 (1984), 121–132.

[4] J. E. Blackburn, H. Crapo and D. A. Higgs, A catalogue of combinatorial geometries, Math. Comp. 27 (1973), 155–166.

[5] H. Crapo, Single-Element Extensions of Matroids, J. Res. Nat. Bur. Stand. 69B (1965), 57–65.

[6] H. Crapo, Erecting Geometries, Proc. 2^{nd} Chapel Hill Conf. on Comb. Math. (1970), 74–99.

[7] H. Crapo and G.-C. Rota, Combinatorial Geometries, Preliminary edition, MIT Press, Cambridge, 1970.

[8] H. Crapo and W. Schmitt, The free product of matroids, European J. Combin., to appear.

[9] W. M. B. Dukes, On a unimodality conjecture in matroid theory, Discrete Math. Theor. Comput. Sci. 5(1) (2002), 181–190.

[10] W. M. B. Dukes, Bounds on the number of generalized partitions and some applications, Australas. J. Comb. 28 (2003), 257–262.

[11] W. M. B. Dukes, Counting and Probability in Matroid Theory, Ph.D. thesis, Trinity College Dublin, 2000.

[12] D. E. Knuth, The Asymptotic Number of Geometries, J. Combin. Theory Ser. A 16 (1974), 398–400.

[13] D. E. Knuth, Random Matroids, Discrete Math. 12 (1975), 341–358.

[14] J. P. S. Kung, On the lines-planes inequality for matroids, J. Combin. Theory Ser. A 91 (2000), 363–368.

[15] M. Lemos, On the number of non-isomorphic matroids, Adv. Appl. Math. 33 (2004), 733– 746.

[16] J. H. Mason, Matroids: Unimodal conjectures and Motzkin’s theorem, Combinatorics (D. J. A. Welsh and D. R. Woodall, eds.), Institute of Math. and Appl. (1972), 207–221.

[17] H. Q. Nguyen, Constructing the free erection of a geometry, J. Combin. Theory Ser. B 27 (1979), 216–224.

[18] J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.

[19] M. J. Piff and D. J. A. Welsh, On the number of combinatorial geometries, Bull. London. Math. Soc. 3 (1971), 55–56.

[20] P. D. Seymour, On the points-lines-planes conjecture, J. Combin. Theory Ser. B 33 (1982), 17–26.

[21] D. J. A. Welsh, Matroid Theory, Academic Press, 1976.

[22] D. J. A. Welsh, Combinatorial problems in matroid theory, in Combinatorial Mathematics and its Applications (ed. D. J. A. Welsh), Academic Press, London, 1971, 291–306.

[23] D. J. A. Welsh, A bound for the number of matroids, J. Comb. Theory 6 (1969), 313–316.

[24] M. Wild, The asymptotic number of inequivalent binary codes and nonisomorphic binary

matroids, Finite Fields Appl., 6 (2000), 192–202.

  E-mail address: dukes@labri.fr

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France.