Séminaire Lotharingien de Combinatoire 83 (2021), Article B83b

MATROIDS OF COMBINATORIALLY FORMAL ARRANGEMENTS ARE NOT DETERMINED BY THEIR POINTS AND LINES

TILMAN MÖLLER

Abstract. An arrangement of hyperplanes is called formal, if the relations between the hyperplanes are generated by relations in codimension 2. Formality is not a combinatorial property, raising the question for a characterization for combinatorial formality. A sufficient condition for this is if the underlying matroid has no proper lift with the same points and lines. We present an example of a matroid with such a lift but no non-formal realization, thus showing that above condition is not necessary for combinatorial formality.

1. Introduction

Let 𝕂 be a field. An arrangement 𝒜 is a finite collection of linear subspaces of V = 𝕂^{ℓ} of codimension 1. Each hyperplane H ∈ 𝒜 is given as the kernel of a linear functional α_{H} ∈ V^{∗} that is unique up to a scalar. Let L(𝒜) be the collection of all non-empty intersections of hyperplanes in 𝒜. We require V ∈ L(𝒜) as well. The set L(𝒜) is ordered by reverse inclusion and ranked by r(X) = codim X for X ∈ L(𝒜). In fact, L(𝒜) has the structure of a geometric lattice, called the lattice of flats. It contains the combinatorial data of the arrangement 𝒜 and defines the underlying matroid M(𝒜). Two arrangements are called (combinatorially) isomorphic if their underlying matroids are equal up to isomorphism. Any property that is invariant under such an isomorphism is called combinatorial. Consider a vector space 𝕂^{𝒜} := ⨁_{H∈𝒜} 𝕂e_{H} with a basis indexed by the hyperplanes in 𝒜

and the linear map Φ : 𝕂^{𝒜} → V^{∗} defined by Φ(e_{H}) = α_{H}. If ker Φ is generated by its elements of weight at most three, i.e., vectors with 3 or fewer non-zero entries, 𝒜 is called formal, see [FR86]. In [Yuz93], Yuzvinsky showed that formality is not combinatorial, so it is natural to ask whether matroids that admit only formal arrangements can be characterized intrinsically. A matroid is called taut if it is not a proper quotient of a matroid with the same points and lines, see Definition 2.9. An arrangement with an underlying taut matroid is necessarily formal. For a survey on this topic, see [Fal02, Ch. 3]. In loc. cit., Falk asked whether there is a non-taut matroid that only admits formal arrangements as realizations. In this paper we give such an example, thus showing the following.

Theorem 1.1. There is a realizable matroid M that is not taut such that every realization of M is formal as an arrangement.

Key words and phrases. matroid, arrangement, formality, weak map image, free erection.

2. Recollections and Preliminaries

Let E be a finite set. A matroid M on the ground set E is a collection B of subsets of E subject to

(i) B ≠ ∅ and

(ii) for all B, B′ ∈ B and every f ∈ B′\B there is e ∈ B\B′ such that (B′ \ {f})∪{e} ∈ B.

An element B ∈ B is called a basis or a base of M. Note that all bases have the same cardinality. Any subset of a base is an independent set of M. Subsets of E that are not independent are dependent, the minimal dependent sets are called circuits.

The rank rk(X) of a subset X ⊂ E is the size of a maximal independent subset of X, and the rank of M is defined by rk(M) = rk(E). There is a notion of closure on M sending subsets to their maximal supersets of the same rank, i.e.,

cl(X) := \overline{X} := \{e ∈ E | rk(X) = rk(X ∪ \{e\})\} .

A set X ⊂ E is called closed or a flat of M if X = \overline{X}. The set L = L(M) of all flats is partially ordered by inclusion. It has the structure of a geometric lattice and is called the lattice of flats. Flats of rank one (respectively two) are called points (respectively lines) of M. An element e ∈ E that is dependent on its own is called a loop, two dependent elements {i, j} are called parallel. A matroid is called simple if it has no loops or parallel elements. A matroid is completely determined by its bases, circuits, rank function, closure or the lattice of flats.

For ease of notation, we write L_{k} for the elements of L of rank k and L_{k}^{>s} for flats of rank k and cardinality greater than s. We call L_{rk(E)−1} the set of copoints of M. In fact, the collection of copoints contains enough information to uniquely define the matroid as well.

Definition 2.1. Let M, N be two matroids on the same ground set E. If any independent set of M is independent in N, we call M a weak map image of N and write M ≺ N. If M is a weak map image of N and further L(M) ⊂ L(N), we call M a quotient of N. Note that ≺ defines a partial order on all matroids on a fixed ground set.

Let X ⊂ E. The deletion of X from M is the matroid M − X on the ground set E \ X. Its independent sets are the independent sets of M disjoint from X. The contraction of X from M is the matroid M/X on E \ X. Its circuits are the minimal non-empty sets in {C \ X | C ∈ C(M)}. A minor of M is a matroid that arises as a sequence of deletions and contractions of M.

Sometimes the dependencies in M can be realized as the linear dependencies of a set of vectors. Let rk(M) = ℓ. If there is a set A = {v_{1}, …, v_{n}} of vectors of 𝕂^{ℓ} such that B ∈ B if and only if {v_{i} | i ∈ B} is a basis of 𝕂^{ℓ}, then M is called 𝕂-linear and A is called a realization of M. Due to the next proposition, to show that a matroid M is not realizable over a certain field 𝕂, it suffices to find a minor of M that is not realizable over 𝕂.

6 4 0 5 1 3 2

(a) Fano matroid F_{7}

6 4 0 5 1 3 2

(b) non-Fano matroid F_{7}^{−}

Figure 1. Matroids from Example 2.3

Proposition 2.2 ([Oxl92, Prop. 3.2.4]). If a matroid is realizable over a field 𝕂, then all its minors are as well.

Example 2.3. Define F_{7} as the matroid of rank 3 on E = {0, …, 6} with non-trivial lines

L_{2}^{>2}(F_{7}) = {015, 024, 036, 123, 146, 256, 345},

and define F_{7}^{−} as the matroid of rank 3 on the same ground set E with non-trivial lines

L_{2}^{>2}(F_{7}^{−}) = L_{2}^{>2}(F_{7}) \ {345}.

F_{7} is called the Fano matroid and F_{7}^{−} is called the non-Fano matroid. Pictures of the two matroids are given in Figure 1. In the pictures, every point is a point of the matroid, and three points are connected by a line segment if the three points are contained in a flat of rank two. Let M ∈ {F_{7}, F_{7}^{−}} and let A = (I_{3} | X) be a representation of M over a field 𝕂, where I_{3} is the 3 × 3 identity matrix and X is a 3 × 4-matrix, such that the i-th column represents the element i ∈ {0, …, 6}. Then

X = ( \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{matrix} )

and M = F_{7} if and only if char(𝕂) = 2 (cf. [Oxl92, Prop. 6.4.8]). Thus, the Fano matroid is only realizable over fields of characteristic two and the non-Fano matroid is only realizable over fields of characteristic different from two.

Let V = 𝕂^{ℓ}. A finite set 𝒜 = {H_{1}, …, H_{n}} with H_{1}, …, H_{n} (linear) hyperplanes in V is called a (central) arrangement. Choose linear forms α_{i} ∈ V^{∗} such that ker α_{i} = H_{i}. Let M = M(𝒜) be the 𝕂-linear matroid realized by (α_{1}, …, α_{n}). It contains the combinatorial data of the arrangement 𝒜. The lattice L of M(𝒜) is canonically isomorphic to the collection of all non-empty intersections of hyperplanes of 𝒜. The rank of 𝒜 is the codimension of the intersection of all its hyperplanes, i.e., r(𝒜) = codim(⋂ H). It coincides with the rank of the underlying matroid. For a flat X ∈ L(𝒜), define the localization of 𝒜 to X as the subarrangement 𝒜_{X} = {H ∈ 𝒜 | X ⊂ H} of rank rk(X).

Probably the most studied properties of arrangements are freeness and asphericity. Let

S = S(V^{∗}) be the symmetric algebra of V^{∗}. The product Q(𝒜) = ∏_{i=1}^{n} α_{i} ∈ S is called the

defining polynomial of 𝒜. Note that after choosing a basis (e_{1}, …, e_{ℓ}) of V and a dual basis (x_{1}, …, x_{ℓ}) of V^{∗}, we have S ≅ 𝕂[x_{1}, …, x_{ℓ}]. Let

Der(S) = {θ : S → S | θ(fg) = fθ(g) + gθ(f) for all f, g ∈ S}

be the S-module of formal derivations of S. An arrangement is called free if the S-module

D(𝒜) = {θ ∈ Der(S) | θ(Q(𝒜)) ∈ Q(𝒜)S}

is free. A complex arrangement is called aspherical if the complement ℂ^{ℓ} \ ⋃ H is a K(π, 1)- space. Whether freeness and asphericity are combinatorial properties are important open problems in arrangement theory. A comprehensive summary about arrangement theory can be found in [OT92]. Next, we define the notion of a formal arrangement, which is the main interest of this paper. It was introduced by Falk and Randell in [FR86]. They observed that formality is a necessary property for asphericity. Here, we use the equivalent definition established by Brandt and Terao in [BT94].

Definition 2.4. Let 𝕂^{𝒜} = ⨁_{H∈𝒜} 𝕂e_{H} be the vector space with basis indexed by the hyper-

planes in 𝒜 and define Φ : 𝕂^{𝒜} → V^{∗} by Φ(e_{H}) = α_{H} and linear extension. Let F ⊂ ker Φ be the subspace generated by all elements of ker Φ with at most three non-zero entries. Then 𝒜 is called formal if F = ker Φ.

In [Yuz93] it was observed, that formality does not necessarily extend to localizations. This gives rise to the stronger notion of local formality.

Definition 2.5. Let 𝒜 be an arrangement. We call 𝒜 locally formal if 𝒜_{X} is formal for all X ∈ L(𝒜).

Furthermore, Yuzvinsky proved that every free arrangement is formal. Both freeness and asphericity extend to localizations, thus we get the following.

Theorem 2.6. Let 𝒜 be an arrangement.

(i) [FR86] If 𝒜 is aspherical, then it is locally formal.

(ii) [Yuz93] If 𝒜 is free, then it is locally formal.

Formality is not a combinatorial property. The first example in the literature is due to Yuzvinsky.

Example 2.7 ([Yuz93, Ex. 2.2]). Define Q_{0} = xyz(x + y + z)(2x + y + z)(2x + 3y + z)(2x + 3y + 4z) and define arrangements 𝒜_{1} and 𝒜_{2} by Q(𝒜_{1}) = Q_{0} · (3x + 5z)(3x + 4y + 5z) and Q(𝒜_{2}) = Q_{0} · (x + 3z)(x + 2y + 3z). Then the underlying matroids of 𝒜_{1} and 𝒜_{2} are the same, but 𝒜_{1} is formal while 𝒜_{2} is not.

Since formality is not combinatorial, it makes sense to ask for a property of the matroid such that each 𝕂-representation of it is formal.

Remark 2.8. Consider the map π : V → 𝕂^{𝒜} defined by π(x) = (α_{1}(x), …, α_{n}(x))^{T}. If y = (y_{1}, …, y_{n}) ∈ ker Φ, consider the scalar product π(x)y = ∑ y_{i}α_{i}(x) = Φ(y)(x) = 0, so Im π = ker Φ^{⊥}. Thus ker Φ contains all the information of 𝒜 and 𝒜 can be reconstructed via

𝒜 ≅ {ker Φ^{⊥} ∩ {x_{i} = 0} | i = 1, …, n}.

The same construction for F yields 𝒜_{F} := {F^{⊥} ∩ {x_{i} = 0} | i = 1, …, n}, the formalization of 𝒜. Clearly, r(𝒜) ≤ r(𝒜_{F}) and r(𝒜) = r(𝒜_{F}) if and only if 𝒜 is formal. Furthermore, it is easy to see that M(𝒜) is a quotient of M(𝒜_{F}) with the same points and lines. This construction first appears in [Yuz93].

Definition 2.9 ([Fal02, Def. 3.5]). A matroid M on E is called taut if it is not a quotient of any matroid of higher rank with the same points and lines. Call M locally taut if for every X ∈ L(M), the localization M − (E \ X) is taut.

Because of Remark 2.8, a 𝕂-representation of a (locally) taut matroid is always (locally) formal, since its formalization cannot admit it as a proper quotient. This paper is dedicated to showing that the reverse implication is false, which answers a question raised by Falk in [Fal02]. This also gives a partially negative answer to Problem 3.7 of [FR00], since the matroid we present is of rank 3, where formality and local formality coincide. It remains an open problem whether or not matroids of free respectively aspherical arrangements are determined by their points and lines.

To validate our claim, we use the theory about erections of matroids established in [Cra70].

Definition 2.10. Let M be a matroid on E of rank r > 1. The truncation of M is the (unique) matroid T of rank r − 1 with L(T) = L_{<r}(M) ∪ E. Thus, T ≺ M. A matroid N is an erection of M if the truncation of N is isomorphic to M. We further say M is the trivial erection of itself.

Note that while the truncation is uniquely defined, there can be many erections of a matroid. Let E(M) be the collection of erections of M.

Theorem 2.11 ([Cra70, Thm. 9]). Let M be a matroid. Then the set E(M) together with the relation ≺ from Definition 2.1 has the structure of a geometric lattice. Its minimal element is the trivial erection M. Define the free erection of M as the maximal element of E(M).

Let M be a matroid on E and let k ∈ ℕ. A subset X ⊂ E is k-closed if it contains the closures of all its k-element subsets. We say X spans M if \overline{X} = M. The following theorem characterizes erections of M by their copoints.

Theorem 2.12 ([Cra70, Thm. 2]). Let M be a matroid of rank r on E. A set F of subsets (called blocks) of E is the set of copoints of an erection of M if and only if

(i) each block spans M;

(ii) each block is (r − 1)-closed;

(iii) each basis of M is contained in a unique block.

3. Proof of Theorem 1.1

Let M be the simple matroid on E = {0, …, 12} of rank 3 with the following non-trivial flats in rank 2:

L_{2}^{>2}(M) = \{ \begin{matrix}\{0, 3, 9\}, & \{0, 4, 7\}, & \{0, 5, 6\}, & \{8, 9, 10\}, & \{7, 10, 11\}, \\ \{1, 4, 9\}, & \{1, 3, 7\}, & \{1, 5, 8\}, & \{6, 9, 11\}, & \{6, 10, 12\}, \\ \{2, 5, 9\}, & \{2, 3, 6\}, & \{2, 4, 8\}, & \{7, 9, 12\}, & \{8, 11, 12\} \end{matrix} \} .

For a picture of M see Figure 2. Note that for X = {0, …, 8} ⊂ E, M contains the underlying matroid of Example 2.7 as a minor. For the subset Y = {6, …, 12} the non-Fano matroid F_{7}^{−} is also a minor of M, see Figure 3.

3 0 5 2 4 1 6 7 8 9 10 11 12

Figure 2. The matroid M.

9 7 10 6 12 8 11

(a) non-Fano matroid F_{7}^{−}

3 0 5 2 4 1 6 7 8

(b) matroid from Example 2.7

Figure 3. Two minors of M.

A realization of M over ℚ is given by

A = ( \begin{matrix}1 & 4 & 4 & 8 & 4 & 2 & 1 & 0 & 0 & 4 & 4 & 4 & 4 \\ 1 & −2 & 1 & −1 & 1 & −1 & 0 & 1 & 0 & −5 & −5 & 5 & 5 \\ 1 & 5 & −10 & 10 & 4 & −1 & 0 & 0 & 1 & 6 & −6 & −6 & 6 \end{matrix} ) ,

where the i-th column of A belongs to the element i ∈ E. We mention that no realization of M can be free (since its characteristic polynomial does not factor). Furthermore, as a complex arrangement A is not aspherical, since it has a simple triangle (cf. [FR86, Cor. 3.3]). We have not verified whether other realizations of M are not aspherical, yet we mention that there are realizations of M that do not admit a simple triangle.

Next we define the matroid N of rank 4 with the same points and lines as M. The non-trivial flats of rank 3 are given by

L_{3}^{>3}(N) = \{ \begin{matrix}\{0, 1, 3, 4, 7, 9, 12\}, & \{0, 4, 5, 6, 7\}, & \{0, 4, 7, 10, 11\}, & \{0, 8, 11, 12\}, \\ \{0, 2, 3, 5, 6, 9, 11\}, & \{1, 2, 3, 6, 7\}, & \{1, 3, 7, 10, 11\}, & \{1, 6, 10, 12\}, \\ \{1, 2, 4, 5, 8, 9, 10\}, & \{0, 1, 5, 6, 8\}, & \{0, 5, 6, 10, 12\}, & \{2, 7, 10, 11\}, \\ \{6, 7, 8, 9, 10, 11, 12\}, & \{2, 3, 4, 6, 8\}, & \{2, 3, 6, 10, 12\}, & \{3, 8, 11, 12\}, \\ \{0, 3, 8, 9, 10\}, & \{0, 2, 4, 7, 8\}, & \{1, 5, 8, 11, 12\}, & \{4, 6, 10, 12\}, \\ \{1, 4, 6, 9, 11\}, & \{1, 3, 5, 7, 8\}, & \{2, 4, 8, 11, 12\}, & \{5, 7, 10, 11\}, \\ \{2, 5, 7, 9, 12\} \end{matrix} \} .

Furthermore, L_{3}(N) also contains every three-element subset of E that is not in L_{2}(N) = L_{2}(M) or a subset of a flat in L_{3}^{>3}(N), i.e.,

L_{3}^{=3}(N) = \{ \begin{matrix}\{0, 1, 10\}, & \{0, 2, 12\}, & \{3, 4, 10\}, & \{3, 5, 12\}, \\ \{0, 2, 10\}, & \{1, 2, 12\}, & \{3, 5, 10\}, & \{4, 5, 12\}, \\ \{0, 1, 11\}, & \{0, 1, 2\}, & \{3, 4, 11\}, & \{3, 4, 5\}, \\ \{1, 2, 11\}, & & \{4, 5, 11\} \end{matrix} \}

Note that L_{3}(N) satisfies the conditions from Theorem 2.12, so N is an erection of M. This implies that M is not taut. Next we show that N is the only non-trivial erection of M.

Lemma 3.1. We have E(M) = {M, N}.

Proof. Suppose N′ ≠ M is an erection of M. Then, the copoints of N′ have to fulfil the conditions (i)–(iii) from Theorem 2.12. The 2-closed sets with respect to M that span M and are proper subsets of E are precisely L_{3}(N) ∪ S, where

S = \{ \begin{matrix}\{0, 1, 12\}, & \{3, 4, 12\}, & \{0, 1, 2, 10\}, & \{3, 4, 5, 10\}, \\ \{0, 2, 11\}, & \{3, 5, 11\}, & \{0, 1, 2, 11\}, & \{3, 4, 5, 11\}, \\ \{1, 2, 10\}, & \{4, 5, 10\}, & \{0, 1, 2, 12\}, & \{3, 4, 5, 12\}, \\ \{6, 7, 8\} \end{matrix} \} .

We argue that no element of S can be a copoint of N′, thus implying our statement. First assume that X ∈ S is of cardinality 3. Then X is a basis of M, thus by Theorem 2.12(iii) there is a unique block Z ∈ L_{3}(N) with X ⊂ Z. So if X is a copoint of N′, then Z is not. Now observe that for every choice of X, there are bases B of M with B ⊂ Z that are not a subset of any other possible block in L_{3}(N) ∪ S. For completeness, we specify a base for each of the seven choices for X:

• if X = {0, 1, 12} or X = {3, 4, 12}, then Z = {0, 1, 3, 4, 7, 9, 12} and B = {0, 1, 3}.

• if X = {0, 2, 11} or X = {3, 5, 11}, then Z = {0, 2, 3, 5, 6, 9, 11} and B = {0, 2, 3}.

• if X = {1, 2, 10} or X = {4, 5, 10}, then Z = {1, 2, 4, 5, 8, 9, 10} and B = {1, 2, 4}.

• if X = {6, 7, 8}, then Z = {6, 7, 8, 9, 10, 11, 12} and B = {7, 8, 9}.

Finally assume that Y ∈ S is of cardinality 4. This case reduces to the first one since there always is a X ∈ S with X ⊊ Y, so with the same reasoning as before, Y is not a copoint of N′. Thus N′ = N. □

Lemma 3.2. The matroid N is not realizable over any field 𝕂.

Proof. First, observe that the deletion N − {0, …, 5} is the non-Fano matroid F_{7}^{−}, so by Proposition 2.2 and Example 2.3, N is realizable only over fields of characteristic different from 2. Furthermore, it turns out that F_{7} is a minor of N as well. To see this, consider the contraction P = N/{6} and consider parallel elements as a single point. The points of P then are

L_{1}(P) = {[0, 5], [1], [2, 3], [4], [7], [8], [9, 11], [10, 12]} ,

and the non-trivial lines of P are

L_{2}^{>2}(P) = \{ \begin{matrix}\{[0, 5], [1], [8]\}, & \{[1], [2, 3], [7]\}, \\ \{[0, 5], [2, 3], [9, 11]\}, & \{[1], [4], [9, 11]\}, \\ \{[0, 5], [4], [7]\}, & \{[2, 3], [4], [8]\}, \\ \{[7], [8], [9, 11], [10, 12]\} \end{matrix} \} .

Thus, F_{7} = P − {[10, 12]} is a minor of N, so again by Proposition 2.2 and Example 2.3, N is not realizable over any field. □

Since N is the only non-trivial erection of M, and N is not realizable over any field, by Remark 2.8 it must be that M(𝒜) = M(𝒜_{F}) for every arrangement 𝒜 realizing M.

Corollary 3.3. Every realization of the matroid M is formal.

This completes the proof of Theorem 1.1.

4. An algorithmic approach

In this section, we explain how this example was obtained. In [Knu75], Knuth describes an algorithm to generate matroids on a fixed ground set by iteratively specifying dependent subsets – or, in other words, nontrivial flats – in every rank. Every matroid can be obtained in this way, see [Knu75, Ch. 5]. Knuth’s algorithm is described as follows.

Step 1 – Initialization. Start with E = {0, …, n − 1}, r = 0 and L_{0} = {∅}.

Step 2 – Generate covers. Set L_{r+1} = {X ∪ {e} | X ∈ L_{r}, e ∈ E \ X}.

Step 3 – Enlarge. Do the following any number of times: pick any X, Y ∈ L_{r+1} and replace them by X ∪ Y. This step is indeterminate.

Step 4 – Superpose. For each pair X, Y ∈ L_{r+1}, if there is no C ∈ L_{r} such that X ∩ Y ⊂ C, replace X, Y ∈ L_{r+1} by X ∪ Y. Repeat this process until no such pair X ≠ Y with X, Y ∈ L_{r+1} exists anymore.

Step 5 – Test for completion. If E ∈ L_{r+1}, quit. Otherwise, increase r by 1 and go to Step 2.

The algorithm yields the set L = L_{0} ∪ ⋯ ∪ L_{r} .

Remark 4.1. To see that L defines a matroid on E, consider the following characterization of the lattice of flats, as seen in [Oxl92, Ex. 1.4.11]:

A collection of subsets L ⊂ 2^{E} is the lattice of flats of a matroid M on E if and only if the following conditions hold:

(i) E ∈ L.

(ii) If X, Y ∈ L then X ∩ Y ∈ L.

(iii) If X ∈ L and {Y_{1}, …, Y_{k}} cover X in L via inclusion, then {Y_{1} \ X, …, Y_{k} \ X} is a partition of E \ X.

Note that the initial set of covers in Step 2 fulfills condition (iii). The replacement operations in Step 3 and Step 4 respect condition (iii), and Step 4 ensures that condition (ii) is met. Step 5 ensures that condition (i) holds. Thus, Knuth’s algorithm indeed yields the lattice of flats of a matroid on E.

Procedure 4.2. By enlarging L_{r} in different ways in Step 3, we have control over the generated matroid. In fact, when given a matroid, we can use Knuth’s algorithm to test whether there are any nontrivial erections of it, and compute all of them. The free erection of a given matroid can be computed with Knuth’s algorithm in the following way, see also [Knu75, Ch. 7]:

Let M be a matroid on E of rank m and let L̃ = L̃_{0} ∪ ⋯ ∪ L̃_{m} be its lattice of flats. For r = 0, …, m − 2, in Step 3, enlarge L_{r+1} in such a way that L_{r+1} = L̃_{r+1} holds. Next, do not perform any enlargements on L_{m}. If the algorithm quits with L_{m} = {E}, then M has no nontrivial erection. Otherwise, we obtain the free erection of M by enlarging L_{m+1} such that L_{m+1} = {E}. The other erections of M can be obtained by performing different enlargements on L_{m}.

A matroid of rank 3 is, by definition, taut if and only if it has no nontrivial erection. Since Knuth’s algorithm can find all erections of a given matroid, we searched for a realizable matroid with a single nontrivial not realizable erection. The underlying matroid of the arrangements from Yuzvinsky’s Example 2.7 has only a single nontrivial erection. From there, we tested several extensions that maintained the triangular symmetry which can be seen in Figure 3(B) until we found the presented example.

Appendix: Verifying the Computations in SAGE

Here, we provide to the reader the code to verify all our calculations using the open source software SAGE, version 9.2 ([Sage]).

from sage.matroids.basis_matroid import BasisMatroid
# Initialize matroids M and N
L_M = [
  [0, 3, 9], [0, 4, 7], [0, 5, 6],
  [1, 4, 9], [1, 3, 7], [1, 5, 8], [2, 5, 9],
  [2, 3, 6], [2, 4, 8], [8, 9, 10], [6, 9, 11],
  [7, 9, 12], [7, 10, 11], [6, 10, 12], [8, 11, 12]
]
nonbases_M = [x for y in L_M for x in Combinations(y, 3)]
M = BasisMatroid(groundset = range(13), nonbases = nonbases_M)
L_N = [
  [0, 8, 11, 12], [1, 6, 10, 12], [2, 7, 10, 11], [3, 8, 11, 12],
  [4, 6, 10, 12], [5, 7, 10, 11], [0, 1, 5, 6, 8], [0, 2, 4, 7, 8],
  [0, 3, 8, 9, 10], [0, 4, 5, 6, 7], [0, 4, 7, 10, 11], [0, 5, 6, 10, 12],
  [1, 2, 3, 6, 7], [1, 3, 5, 7, 8], [1, 3, 7, 10, 11], [1, 4, 6, 9, 11],
  [1, 5, 8, 11, 12], [2, 3, 4, 6, 8], [2, 3, 6, 10, 12], [2, 4, 8, 11, 12],
  [2, 5, 7, 9, 12], [0, 1, 3, 4, 7, 9, 12], [0, 2, 3, 5, 6, 9, 11],
  [1, 2, 4, 5, 8, 9, 10], [6, 7, 8, 9, 10, 11, 12]
]
nonbases_N = [x for y in L_N for x in Combinations(y,4)]
N = BasisMatroid(groundset = range(13), nonbases = nonbases_N)
# check that M and N are well defined matroids

print("M is valid:",M.is_valid())
print("N is valid:",N.is_valid())
print("M and N have the same flats:", frozenset(M.flats(2)) == frozenset(N.flats(2)))
# check that A is a realization of M
A = Matrix(QQ, 3, 13,
  [1,4,4,8,4,2,1,0,0,4,4,4,4,
  1,-2,1,-1,1,-1,0,1,0,-5,-5,5,5,
  1,5,-10,10,4,-1,0,0,1,6,-6,-6,6])
print("M and the matroid of A are isomorphic:", Matroid(A).is_isomorphic(M))
# verify that the 2-closed sets of M that span M are correct
S = [frozenset(x)
  for x in [
    [0,1,12],[0,2,11],[1,2,10],
    [3,4,12],[3,5,11],[4,5,10],
    [0,1,2,10],[0,1,2,11],[0,1,2,12],
    [3,4,5,10],[3,4,5,11],[3,4,5,12],[6,7,8]
]]
line_closed_in_M = frozenset(
  [M.k_closure(x, 2)
    for x in Combinations(range(13))
    if M.rank(x)== 3
  ]
).difference(frozenset([frozenset(range(13))]))
print("the line closed sets of M are the rank 3+ flats in N:",
    frozenset(line_closed_in_M) == frozenset(N.flats(3)).union(frozenset(S)))
# verify that N has both Fano and NonFano matroid as minors
Fano = matroids.named_matroids.Fano()
NonFano = matroids.named_matroids.NonFano()
print("N has Fano as minor:", N.has_minor(Fano, certificate = True))
print("N has NonFano as minor:", N.has_minor(NonFano, certificate = True))

Acknowledgements

The author thanks Michael Falk for helpful discussions regarding the content of this paper.

References

[BT94] K. A. Brandt and H. Terao. Free arrangements and relation spaces. Discrete Comput. Geom., 12(1):49–63, 1994.

[Cra70] H. Crapo. Erecting geometries. Ann. New York Acad. Sci., 175:89–92, 1970.

[Fal02] M. Falk. Line-closed matroids, quadratic algebras, and formal arrangements. Adv. in Appl. Math., 28(2):250271, 2002.

[FR86] M. Falk and R. Randell. On the homotopy theory of arrangements. Adv. Stud. Pure Math., 8:101– 124, 1986.

[FR00] M. Falk and R. Randell. On the homotopy theory of arrangements, II. Adv. Stud. Pure Math., 27:93–125, 2000.

[Knu75] D. E. Knuth. Random matroids. Discrete Math., 12:341–358, 1975.

[OT92] P. Orlik and H. Terao. Arrangements of Hyperplanes. Springer-Verlag, 1992.

[Oxl92] J. G. Oxley. Matroid theory. Oxford University Press, 1992.

[Sage] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.2), 2020.

       https://www.sagemath.org.

[Yuz93] S. Yuzvinsky. The first two obstructions to the freeness of arrangements. Trans. Amer. Math. Soc., 335(1):231–244, 1993.

Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780 Bochum, Germany

Email address: tilman.moeller@rub.de