Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 2, 283-289.

The Largest Intersection Lattice of a Discriminantal Arrangement

Christos A. Athanasiadis^{∗}

Department of Mathematics, University of Pennsylvania 209 South 33rd Street, Philadelphia, PA 19104-6395, USA email: athana@math.upenn.edu

Abstract. We prove a conjecture of Bayer and Brandt [J. Alg. Combin. 6 (1997), 229–246] about the “largest” intersection lattice of a discriminantal arrangement based on an essential arrangement of n linear hyperplanes in ℝ^{k}. An important ingredient in the proof is Crapo’s characterization of the matroid of circuits of the configuration of n generic points in ℝ^{k}.

1. Introduction

Let A be an arrangement of n linear hyperplanes in ℝ^{k} with normal vectors α_{i} for 1 ≤ i ≤ n. Assume that the vectors α_{i} span ℝ^{k}, so that A is essential. The discriminantal arrangement B(A) based on A (see [11], [1]) is the arrangement of linear hyperplanes in ℝ^{n} with normal vectors the distinct, nonzero vectors of the form

α_{S} = ∑_{i=1}^{k+1} (−1)^{i} det (α_{s_{1}}, …, α_{s_{i−1}}, α_{s_{i+1}}, …, α_{s_{k+1}}) e_{s_{i}},  (1)

where S = {s_{1} < s_{2} < ⋯ < s_{k+1}} ranges over all subsets of [n] := {1, 2, …, n} with k + 1 elements and the e_{j} are the standard coordinate vectors in ℝ^{n}.

We are primarily concerned with a conjecture of Bayer and Brandt [1] about the intersection lattice [13, §2.1] L(B(A)) of B(A), the main combinatorial invariant of B(A). Bayer and Brandt call A very generic if for all r, the number of elements of L(B(A)) of rank r is the largest possible for a discriminantal arrangement based on an essential arrangement of n linear hyperplanes in ℝ^{k}. They denote by P (n, k) the collection of all sets of the form {S_{1}, S_{2}, …, S_{m}}, where the S_{i} are subsets of [n], each of cardinality at least k + 1, such that

∗The present research was carried out while the author was a Hans Rademacher Instructor at the University of Pennsylvania 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

| ⋃_{i∈I} S_{i}| > k + ∑_{i∈I} (|S_{i}| − k)

for all I ⊆ [m] with |I| ≥ 2. They partially order P (n, k) by letting S ⪯ T if every subset in S is contained in some subset in T . Note that P (n, 1) is isomorphic to the lattice of partitions of [n]. The following appears as Conjecture 4.3 in [1].

Conjecture 1.1. (Bayer and Brandt [1]) Let n ≥ k + 1 ≥ 2. There exist arrangements of n hyperplanes in ℝ^{k} which are very generic. Moreover, the intersection lattice of the discriminantal arrangement based on any very generic arrangement of n hyperplanes in ℝ^{k} is isomorphic to P (n, k).

The discriminantal arrangement was originally defined when the hyperplanes of A are in general position, meaning that any k of the vectors α_{i} are linearly independent, by Manin and Schechtman [11], who initiated the study of its complement. Manin and Schechtman remarked [11, p. 292] that although B(A) depends on the original arrangement A (see also Falk [9]), its intersection lattice depends only on n and k if A lies in a Zariski open subset of the space of all arrangements of n linear hyperplanes in general position in ℝ^{k}. They gave a description of this lattice, which we denote by L(n, k), for k + 1 ≤ n ≤ k + 3 ([11, p. 292], see also [13, p. 205]) and implicitly suggested the problem of describing L(n, k) for other values of n.

From a different perspective, unkown in the literature of discriminantal arrangements, the matroid of circuits of the configuration of n points α_{1}, α_{2}, …, α_{n} in ℝ^{k}, realized by the vectors α_{S}, has been introduced by Crapo [4]. Crapo characterized this matroid M(n, k) when the coordinates of the vectors α_{i} are generic indeterminates [5] as the Dilworth completion D_{k}(B_{n}) of the kth lower truncation of the Boolean algebra of rank n (see e.g. Crapo and Rota [6, §7], Mason [12] or Brylawski [3, §7]). The lattice L(n, k) is the geometric lattice of flats of M(n, k). For recent related work, see Crapo and Rota [7].

In the present paper we first define precisely the Zariski open set O(n, k) that the hypothesis of Manin and Schechtman on A refers to, in order to clarify this point (see [9, p. 1222]). We refer to an arrangement A in O(n, k) as sufficiently general. We use ideas from matroid theory [10] to show (Theorem 2.3) that any arrangement A in O(n, k) is very generic and moreover, that it maximizes the f-vector of B(A) or, equivalently, the f-vector of the corresponding fiber zonotope [2, §4]. It follows that very generic arrangements exist and that the lattice which Conjecture 1.1 refers to coincides with L(n, k). Finally we show (Theorem 3.2) that Crapo’s characterization [5, §6] of M(n, k) implies that its lattice of flats L(n, k) is isomorphic to P (n, k). Equivalently, the lattice of flats of the Dilworth completion D_{k}(B_{n}) is isomorphic to P (n, k). This has been observed earlier for k = 1 ([6, Prop. 7.9], [12, §2.5]) and completes the proof of Conjecture 1.1.

Ch. A. Athanasiadis: The largest intersection lattice of a discriminantal arrangement 285

2. Sufficiently general arrangements

Let A be an essential arrangement of n linear hyperplanes in ℝ^{k}, as in the beginning of the introduction, with normal vectors α_{i} = (α_{ij})_{j=1}^{k} for 1 ≤ i ≤ n. For each set S = {S_{1}, S_{2}, …, S_{m}} of (k+1)-subsets of [n] with m ≤ n, we denote by A_{S} the m×n matrix whose (r, j) entry is the jth coordinate of the vector α_{S_{r}} in ℝ^{n}. Let p_{S} be the sum of the squares of the m × m minors of the matrix A_{S}, considered as a polynomial in the indeterminates α_{ij}. Thus p_{S} is an element of the ring ℝ[x_{ij}] and p_{S}(α_{ij}) = 0 if and only if the vectors α_{S_{1}}, α_{S_{2}}, …, α_{S_{m}} are linearly dependent.

Definition 2.1. We call A sufficiently general if p_{S}(α_{ij}) ≠ 0 for all S for which the polynomial p_{S} is not identically zero. We denote by O(n, k) the space of sufficiently general arrangements.

The set O(n, k) is a nonempty Zariski open subset of the space of all arrangements of n linear hyperplanes in general position in ℝ^{k}. Apparently, and in view of the following easy proposition, it is the Zariski open set that Manin and Schechtman refer to.

Proposition 2.2. If A is restricted in the set O(n, k) then the matroid realized by the vectors α_{S}, and hence the intersection lattice L(n, k) as well as the f-vector of B(A), depend only on n and k.

Proof. Indeed, a set S = {S_{1}, S_{2}, …, S_{m}} indexes an independent subset of the set of vectors {α_{S}} if and only if the polynomial p_{S} is not identically zero. □

We now use the idea of weak maps of matroids [10] to show that any arrangement in O(n, k) is very generic, in the sense of Bayer and Brandt. A different application of the same technique was recently given by Edelman [8].

Theorem 2.3. If A is in O(n, k) then B(A) has maximum f-vector and intersection lattice with all rank sets of maximum size among all discriminantal arrangements based on an essential arrangement of n linear hyperplanes in ℝ^{k}.

Proof. Let A′ be any essential arrangement of n linear hyperplanes in ℝ^{k} with corresponding data α′_{i}, α′_{ij} and α′_{S}. The map α_{S} → α′_{S} defines a weak map [10] of the matroids M and M′, realized by the sets of vectors {α_{S}} and {α′_{S}} respectively. Indeed, if the {α′_{S}} for S ∈ S are linearly independent then p_{S}(α′_{ij}) ≠ 0, so p_{S} is not identically zero and hence the {α_{S}} for S ∈ S are also linearly independent. The result follows from the fact that the Whitney numbers of both kinds of M′ are bounded above by those of M whenever there is a weak map of matroids M → M′ (see Proposition 9.3.3 and Corollary 9.3.7 in [10]). □

3. The intersection lattice

We first recall some useful notation from [7]. A set S = {S_{1}, S_{2}, …, S_{m}} of subsets of [n] is an antichain if none of the subsets contains another. For such an antichain S we let

Δ(S) = ν ( ⋃_{S∈S} S) − ∑_{S∈S} ν (S),

where ν (S) = max(0, |S| − k). Thus S ∈ P (n, k) if each S_{i} has cardinality at least k + 1 and Δ(F) > 0 for all F ⊆ S with |F| ≥ 2. If T = {T_{1}, T_{2}, …, T_{p}} is another antichain, we let S ⪯ T if for each i there exists a j such that S_{i} ⊆ T_{j}.

We assume that A is in O(n, k) and think of L(n, k) as the geometric lattice spanned by the vectors α_{S}. The matroid M(n, k) realized by these vectors, to which we have referred in Proposition 2.2, has been characterized by Crapo [5, §6] and was shown to be isomorphic to the Dilworth completion D_{k}(B_{n}) ([6, §7], [12]) of the kth lower truncation of the Boolean algebra of rank n. The Dilworth completion D_{k}(B_{n}) is a matroid on the set of all (k + 1)-subsets of [n] which can be described explicitly in terms of its bases, independent sets and circuits. We keep our discussion as self-contained as possible. The following result is equivalent to Theorem 2 in [5, §6].

Theorem 3.1. (Crapo [5]) Let S_{1}, S_{2}, …, S_{m} be (k + 1)-subsets of [n]. The vectors α_{S_{1}}, α_{S_{2}}, …, α_{S_{m}} are linearly independent if and only if

| ⋃_{i∈I} S_{i}| ≥ k + |I|  (2)

for all I ⊆ [m] or, in other words, if S = {S_{1}, S_{2}, …, S_{m}} satisfies Δ(F) ≥ 0 for all F ⊆ S.

Proof. The elegant argument in the proof of Theorem 2 in [5, §6] shows that α_{S} := {α_{S_{1}}, α_{S_{2}}, …, α_{S_{m}}} is a basis if and only if Δ(F) ≥ 0 for all F ⊆ S and m = n − k. It suffices to show that if S satisfies (2) then α_{S} is contained in a basis. This follows by an application of Hall’s marriage theorem to the sets S_{i} − [k]. □

In the remaining of this section we show that this characterization of M(n, k) implies that its lattice of flats L(n, k) is isomorphic to the poset P (n, k), defined in the introduction. For an antichain S = {S_{1}, S_{2}, …, S_{m}} of subsets of [n] we denote by V_{S} the linear span of the vectors α_{S} for all (k + 1)-subsets S of [n] such that S ⊆ S_{i} for some 1 ≤ i ≤ m. If S = {S}, where S has any cardinality, we write V_{S} instead of V_{S}. Note that dim V_{S} = ν (S), which clearly implies the “only if” direction of Theorem 3.1. We let φ(S) = V_{S} if S ∈ P (n, k).

Theorem 3.2. The map φ : P (n, k) → L(n, k) is an isomorphism of posets.

We give the proof after having established a few lemmas.

Lemma 3.3. Let S be an antichain with the properties |S| ≥ k + 1 for all S ∈ S, Δ(F) ≥ 0 for all F ⊆ S and V_{S} = ⨁_{S∈S} V_{S}. If S is not in P (n, k) then there exists an antichain S′ with the same three properties as S and such that V_{S′} = V_{S}, |S′| < |S| and S ≺ S′.

Proof. By assumption, Δ(F) = 0 for some F ⊆ S with at least two elements. Let U be the union of the elements of F. Since V_{F} ⊆ V_{U} for all F ∈ F, the sum of the V_{F} is direct and their dimensions ν (F) sum to the dimension ν (U) of V_{U}, we have

V_{U} = ⨁_{F ∈F} V_{F} .

Replace the subsets F ∈ F in S with their union U to get the desired antichain S′. The property Δ(E) ≥ 0 for all E ⊆ S′ follows from the corresponding property of S and the fact that ν (U) = ∑_{F ∈F} ν (F). □

Lemma 3.4. If S and T are any antichains with S ⪯ T and Δ(F) ≥ 0 for all F ⊆ S, then

∑_{S∈S} ν (S) ≤ ∑_{T ∈T} ν (T).

Proof. We induct on the cardinality of S. Choose a set T ∈ T so that the subfamily F = {F ∈ S : F ⊆ T } is nonempty. Then

∑_{S∈S} ν (S) = ∑_{F ∈F} ν (F) + ∑_{S ∈ S−F} ν (S) ≤ ν ( ⋃_{F ∈F} F) + ∑_{S∈S−F} ν (S) ≤

≤ ν (T) + ∑_{S ∈ S−F} ν (S).

Since S − F ⪯ T − {T }, induction completes the proof. □

Lemma 3.5. If S ∈ P (n, k), T is a subset of [n] with |T | ≥ k + 1 and {R} ⪯ S for all R ⊆ T with |R| = k + 1, then {T } ⪯ S.

Proof. This follows from the definition of P (n, k) by an easy induction. □

We now prove Theorem 3.2 and thus complete the proof of Conjecture 1.1.

Proof of Theorem 3.2. The map φ is clearly order preserving. We first show that it is surjective. Let V be a linear space in L(n, k). Choose a basis {α_{S_{1}}, α_{S_{2}}, …, α_{S_{m}}} of V, where the S_{i} are (k + 1)-subsets of [n] and let S = {S_{1}, S_{2}, …, S_{m}}, so that V = V_{S}. If S ∈ P (n, k) then φ(S) = V. If not, then Lemma 3.3 applies and produces a sequence of antichains S ≺ S_{1} ≺ S_{2} ≺ ⋯ with V = V_{S_{1}} = V_{S_{2}} = · · ·. Since this procedure reduces m at each step, it terminates. The last antichain T in the sequence is in P (n, k) and satisfies φ(T ) = V.

Next we show that φ is injective. Suppose on the contrary that φ(S) = φ(T ) for two distinct families S, T ∈ P (n, k). We may assume that T ⪯ S is invalid. By Lemma 3.5 there exists a (k + 1)-set R contained in some subset in T but not contained in any S ∈ S. Since α_{R} ∈ V_{S}, we can choose a minimal family F ⪯ S of (k + 1)-subsets such that {α_{F} : F ∈ F} is independent and α_{R} lies in its span. Theorem 3.1 and the minimality of F imply that

ν (( ⋃_{F ∈F} F) ∪ R) < |F| + 1.

On the other hand

ν ( ⋃_{F ∈F} F) ≥ |F|,

by independence of the α_{F}. Hence R ⊆ ⋃_{F ∈F} F and

ν ( ⋃_{F ∈F} F) = |F|.

Let E be the subfamily consisting of the subsets E ∈ S which contain some F ∈ F and E′ be the family obtained from E by intersecting all sets in E with ⋃_{F ∈F} F, so that F ⪯ E′. We have

ν ( ⋃_{E′∈E′} E′) = ν ( ⋃_{F ∈F} F) = ∑_{F ∈F} ν (F) ≤ ∑_{E′∈E′} ν (E′),  (3)

where the inequality follows from Lemma 3.4. It follows that

ν ( ⋃_{E∈E} E) ≤ ∑_{E∈E} ν (E),  (4)

since adding elements to each E′ preserves the inequality (3). By the choice of R, E has cardinality at least 2. Hence (4) contradicts the fact that S ∈ P (n, k).

Finally we show that the inverse of φ is order preserving. Let S, T ∈ P (n, k) be such that φ(S) = V_{S} ⊆ V_{T} = φ(T ). Choose a basis {α_{S} : S ∈ S_{0}} for V_{S} and complete it to a basis {α_{S} : S ∈ T_{0}} of V_{T}, where S_{0} ⊆ T_{0} are families of (k + 1)-subsets of [n]. Apply Lemma 3.3 successively to S_{0} to find an S_{1} ∈ P (n, k) with S_{0} ⪯ S_{1} and φ(S_{1}) = V_{S} = φ(S). Then apply the same lemma to S_{1} ∪ (T_{0} − S_{0}) to find a T_{1} ∈ P (n, k) with S_{1} ⪯ T_{1} and φ(T_{1}) = V_{T} = φ(T ). By injectivity of φ we get S = S_{1} and T = T_{1} so S ⪯ T , as desired. □

The following is a corollary of Theorem 3.2 and the fact that the operation S ↦ S′ of Lemma 3.3 preserves the quantity ∑_{S∈S} ν (S).

Corollary 3.6. The poset P (n, k) is a geometric lattice with rank function

r(S) = ∑_{S∈S} ν (S).

Acknowledgement. I wish to thank Margaret Bayer, Henry Crapo, Victor Reiner, Gian-Carlo Rota and Neil White for helpful discussions and useful references.

References

[1] Bayer, M.; Brandt, K. A.: Discriminantal arrangements, fiber polytopes and formality. J. Algebraic Combin. 6 (1997), 229–246.

[2] Billera. L. J.; Sturmfels, B.: Fiber polytopes. Ann. of Math. 135 (1992), 527–549.

[3] Brylawski. T.: Constructions. Chapter 7 in: Theory of Matroids (N. White ed.), 127– 223, Encyclopedia Math. Appl. 26, Cambridge University Press, 1986.

[4] Crapo, H.: Concurrence geometries. Adv. Math. 54 (1984), 278–301.

[5] Crapo, H.: The combinatorial theory of structures. In: Matroid theory (A. Recski and L. Lovász eds.), Colloq. Math. Soc. János Bolyai 40, 107–213, North-Holland, Amsterdam-New York 1985.

[6] Crapo, H.; Rota, G.-C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries. Preliminary edition, M.I.T. Press, Cambridge, MA, 1970.

[7] Crapo, H.; Rota, G.-C.: The resolving bracket. In: Invariant methods in discrete and computational geometry (N. White ed.), 197–222, Kluwer Academic Publishers, Dordrecht 1995.

[8] Edelman, P. H.: Ordering points by linear functionals. Preprint dated March 11, 1998.

[9] Falk, M.: A note on discriminantal arrangements. Proc. Amer. Math. Soc. 122 (1994), 1221–1227.

[10] Kung, J. P. S.; Nguyen, H. Q.: Weak maps. Chapter 9 in: Theory of Matroids (N. White ed.), 254–271, Encyclopedia Math. Appl. 26, Cambridge University Press 1986.

[11] Manin, Y. I.; Schechtman. V. V.: Arrangements of hyperplanes, higher braid groups and higher Bruhat orders. In: Algebraic Number Theory – in honor of K. Iwasawa, 289–308, Adv. Stud. Pure Math. 17, 1989.

[12] Mason, J. H.: Matroids as the study of geometrical configurations. In: Higher combinatorics (M. Aigner ed.), 133–176, Reidel, Dordrecht–Boston, MA, 1977.

[13] Orlik, P.; Terao, H.: Arrangements of Hyperplanes. Grundlehren Math. Wiss. 300, Springer-Verlag, New York, NY, 1992.

Received July 6, 1998