PERPENDICULAR DISSECTIONS OF SPACE

THOMAS ZASLAVSKY

Abstract. For each pair (Q_{i}, Q_{j}) of reference points and each real number r there is a unique hyperplane h ⊥ Q_{i}Q_{j} such that d(P, Q_{i})^{2} − d(P, Q_{j})^{2} = r for points P in h. Take n reference points in d-space and for each pair (Q_{i}, Q_{j}) a finite set of real numbers. The corresponding perpendiculars form an arrangement of hyperplanes. We explore the structure of the semilattice of intersections of the hyperplanes for generic reference points. The main theorem is that there is a real, additive gain graph (this is a graph with an additive real number associated invertibly to each edge) whose set of balanced flats has the same structure as the intersection semilattice. We examine the requirements for genericity, which are related to behavior at infinity but remain mysterious; also, variations in the construction rules for perpendiculars. We investigate several particular arrangements with a view to finding the exact numbers of faces of each dimension. The prototype, the arrangement of all perpendicular bisectors, was studied by Good and Tideman, motivated by a geometric voting theory. Most of our particular examples are suggested by extensions of that theory in which voters exercise finer discrimination. Throughout, we propose many research problems.

with 10 figures

1. Introduction

Choose n points Q_{1}, …, Q_{n} in d-dimensional Euclidean space and, for each pair of points, take the hyperplane which is the perpendicular bisector of their connecting line segment. Into how many regions does this arrangement of \binom{n}{2} hyperplanes dissect the space? In their article [17], Good and Tideman showed that this number is, in general, equal to

(1.1)  |s(n, n)| + |s(n, n − 1)| + |s(n, n − 2)| + ⋯ + |s(n, n − d)|.

Here s(n, k) is the Stirling number of the first kind, one of whose many definitions is that it equals (−1)^{n−k} times the number of permutations having k cycles of a set of n objects.

This geometry problem arose from a model of voter preference. Suppose there are n candidates, and d issues on which each candidate has a position indicated by a real number. A

Date: Original ms.: 1984. Revised ms.: June–July, 2000. This version: October 8, 2001. 2000 Mathematics Subject Classification. Primary 05C22, 52C35; Secondary 05A15, 05B35, 06C10, 51F99. Key words and phrases. Arrangement of hyperplanes, affinographic arrangement, deformation of Coxeter

arrangement, additive real gain graph, graphic lift matroid, concurrence of perpendiculars, Pythagorean theorem, perpendicular bisector, intersection semilattice, geometric semilattice, balanced chromatic polynomial, Whitney numbers, composed partition, fat forest.

This article is a redaction of a manuscript from 1984–85 reporting research performed originally in 1983 when I was at the Ohio State University and 1984–85 while I was a Visiting Scholar in Mathematical Research at the University of Evansville, with substantial additions (all of Sections 6 and 7.2 and parts of others) and emendations in Year 2000; then further improved upon advice from a referee. The research was supported by the National Science Foundation (through the Ohio State University) and the SGPNR. My thanks to Clark Kimberling for the important reference [8] and to Carol Nedlik for turning a remarkably messy old manuscript into a readable typescript that I could edit into presentability.

voter, who also has a (real number) position on each issue, prefers the nearer of two candidates. How many different orderings of the candidates are possible? Considering candidates i and j, represented by points Q_{i} and Q_{j} in d-space, the perpendicular bisecting hyperplane of the segment [Q_{i}, Q_{j}] divides those voters ranking i over j from those ranking j over i. The \binom{n}{2} bisecting hyperplanes together dissect the space into regions such that all voters (i.e., points) in each region have the same ranking of candidates, while different regions yield different rankings. Thus the model leads to the geometry problem described in the first paragraph and thus to the solution given by (1.1). (This account ignores pseudo-orderings, in which the voter ranks some candidates equally. Pseudo-orderings arise from voters located within bisecting hyperplanes; so to count all pseudo-orderings we should count all the cells, of all dimensions, into which the bisectors divide the space. That was also done by Good and Tideman.)

Good and Tideman proved their formula by an induction on n and d, in the course of which they proved (inductively) that for each (d − k)-dimensional flat of a special kind in the original arrangement the remaining hyperplanes form an arrangement of bisectors of n − k points. From this fact they deduced the number of i-dimensional faces of the original arrangement, for all i. (Their proof for the special (d − k)-flats contains an oversight but their numerical result is correct. We discuss this in Section 7.2.)

We present a new proof and a generalization of Good and Tideman’s formula (1.1), which explains the occurrence of the Stirling numbers. Our approach is based on the fact that one can compute the number of regions of an arrangement ℋ of hyperplanes from a knowledge of the partially ordered set ℒ(ℋ) of flats of intersection of the hyperplanes (ordered by reverse inclusion).

In broad outline: According to [27, Theorem A], ℋ has |w_{0}| + |w_{1}| + ⋯ + |w_{d}| regions, where the w_{i} are the so-called “Whitney numbers of the first kind” of ℒ(ℋ). If ℋ is the arrangement of bisectors of n points in d-space, then ℒ(ℋ) is isomorphic to the set of all partitions of n objects into at least n − d parts, ordered by refinement. (This was proved in effect by Good and Tideman. We give a new and more general proof: see Section 11.1 for the result.) Since the Whitney number w_{i} of the partition lattice equals s(n, n − i) ([14], [24, §9]), formula (1.1) follows. This proof sketch will be filled out below.

Our generalization is to allow other hyperplanes perpendicular to the lines Q_{i}Q_{j} besides the bisectors. We call these arrangements Pythagorean arrangements of hyperplanes. Then one must decide how to specify the location of the hyperplane, or, what is the same thing, of its foot P_{ij} on Q_{i}Q_{j}. Two obvious ways to do this are by specifying either the signed distance d_{ij}(P_{ij}) of the foot from the midpoint of the segment [Q_{i}, Q_{j}] (positive toward Q_{j}, negative toward Q_{i}), or the proportional distance d_{ij}(P_{ij})/d(Q_{i}, Q_{j}). The most appropriate way to locate P_{ij}, however, is neither of these. We introduce the Pythagorean coordinate of a point P with respect to Q_{i}Q_{j}: it is the value

(1.2)  ψ_{ij}(P) = d(P, Q_{i})^{2} − d(P, Q_{j})^{2} = 2 d_{ij}(P) · d(Q_{i}, Q_{j}).

The significance of this coordinate is that, when it is employed to determine the locations of perpendicular hyperplanes, then for generic reference points Q_{1}, …, Q_{n} all concurrences of perpendiculars to lines Q_{i}Q_{j} are determined in a nontrivial way by the Pythagorean coordinates of their feet (Section 5).^{1} That enables us to compute the number of regions (and bounded regions and indeed flats and faces of any dimension) of the arrangement of perpendiculars. We can also characterize (Section 7.2) the arrangement induced in each flat by the original hyperplanes. If on the other hand we locate the feet by signed distance from the midpoint, or proportional distance, or indeed any locating function of the form cψ_{ij}(P_{ij})/d(Q_{i}, Q_{j})^{α} where α ≠ 0 and c is any fixed nonzero multiplier, then (for generic reference points) there are no concurrences except those of bisectors (Section 8). Thus the formula for the number of regions becomes less richly structured, depending not at all on the exact locations of the nonbisecting perpendiculars.

With the general theory we can treat more sophisticated voters, for instance those who prefer Q_{i} to Q_{j} only when the former is significantly closer than the latter—provided “significantly closer” is interpreted so as to be a linear condition. The calculations, however, may become quite difficult. Broadened examples like this are treated in Section 11, with detailed formulas. The natural, but nonlinear, interpretation of “significantly closer” to mean d(V, Q_{i}) < d(V, Q_{j}) − δ_{ij}, where δ_{ij} > 0 is fixed, leads to a totally different problem, unstudied but interesting and difficult: a quadric analog of hyperplane dissections (Section 13.3).

We reiterate that our results apply when the reference points Q_{i} are chosen generically. A definition of this concept is that, if Q_{1}, …, Q_{n} are generic, then shifting them slightly does not change the combinatorial type of the set of intersection flats of the associated arrangement of perpendiculars. Exactly what genericity entails for the set of reference points is hard to say. It does imply simple position—that is, no d + 1 of the Q_{i} are affinely dependent—and more strongly, “ideal general position”, which includes such projective properties as that no line Q_{i}Q_{j} parallels a hyperplane determined by d of the points. However, these are not sufficient for genericity. What else it may entail is insufficiently known despite our efforts in Section 6.1.

2. Arrangements of Hyperplanes

We begin with some general theory of arrangements of hyperplanes from [27]. An arrangement ℋ is a finite set^{2} of hyperplanes in Euclidean space 𝔼^{d} or real projective space ℙ^{d}, together with the associated decomposition of the space into connected components, the faces of ℋ. The d-dimensional faces are called regions. The number of k-dimensional faces (k-faces) is f_{k}(ℋ). The number of bounded faces, in the Euclidean case, is b_{k}(ℋ). A flat of ℋ is any subspace obtained as the intersection of hyperplanes in ℋ, excluding the null subspace in the Euclidean case. The number of k-dimensional flats (k-flats) is a_{k}(ℋ). The set ℒ(ℋ) of all flats, when ordered by reverse inclusion, is a meet semilattice with ˆ0 = the whole space; in the projective case it is a lattice with ˆ1 = ⋂ ℋ. The rank function rk(x) = codim x makes ℒ(ℋ) a geometric semilattice (which is a geometric lattice with the interval over an atom deleted; see [26]) and in the projective case a geometric lattice.

Our primary interest is in Euclidean arrangements of hyperplanes perpendicular to lines, but it is easier to study them if we can also refer to their projective analogs. Let ℰ be an arrangement of N hyperplanes in 𝔼^{d}. The projectivization ℰ_{ℙ} is the arrangement of N + 1 hyperplanes in ℙ^{d} consisting of the projective closure h_{ℙ} of each hyperplane h in ℰ and additionally the ideal hyperplane h_{∞}. The flats (and faces) of ℰ_{ℙ} are those of ℰ (actually, the projective closures s_{ℙ} of all s ∈ ℒ(ℰ)) and the extra flats (and faces) in h_{∞}, which reflect parallelisms among the Euclidean flats of ℰ.

1The only other specific use of Pythagorean coordinates of which I am aware is in Cacoullos [7]; they are his δ_{ij}(X). He locates hyperplanes by proportional coordinates. However, his problem is merely to find the nearest neighbor from amongst d + 1 points and not the entire distance ranking of n points.

2In this paper all graphs and all sets of hyperplanes, flats, etc., are finite.

For a ranked partially ordered set P with zero element we write W_{i} for the number of rank i elements (the Whitney number of the second kind); thus W_{i}(ℒ(ℋ)) = a_{d−i}(ℋ). More important for our purposes are the Whitney numbers of the first kind, w_{i}. To define them we need the combinatorial Möbius function of P (see [24]), that is, μ : P × P → ℤ defined recursively for increasing y by

μ(x, y) = 0  if x ≰ y,
μ(x, x) = 1,
μ(x, y) = − ∑_{z:z<y}μ(x, z)  if x < y.

Then

w_{i} = ∑{μ(ˆ0, y) : rk(y) = i}.

We take P to be ℒ(ℋ); hence

|w_{i}(ℒ(ℋ))| = (−1)^{i}w_{i}(ℒ(ℋ)) = ∑{|μ(ˆ0, y)| : y ∈ ℒ(ℋ) and codim y = i}

by Rota’s theorem [24, §7] that (−1)^{rk(ˆ1)}μ(ˆ0, ˆ1) > 0 in a geometric lattice.

With these preliminaries behind us, we can state the key facts of enumeration for arrangement of hyperplanes [27, Thms. A, B, and C]. For a Euclidean arrangement ℰ,

(2.1a)  f_{d}(ℰ) = ∑_{i=0}^{d}|w_{i}(ℒ(ℰ))|  and

(2.1b)  b_{d}(ℰ) = |∑_{i=0}^{d}w_{i}(ℒ(ℰ))|;

the latter equals (−1)^{d} ∑_{0}^{d}w_{i}(ℒ(ℰ)) if ℰ has any 0-flats. For a nonvoid projective arrangement 𝒜,

(2.2a)  f_{d}(𝒜) = \frac{1}{2} ∑_{i=0}^{d+1} |w_{i}(ℒ(𝒜))|,

which if ⋂ 𝒜 = ∅ is

(2.2b)  = (−1)^{k} ∑_{\begin{matrix}i=0 \\ i even \end{matrix}}^{d}w_{i}(ℒ(𝒜)).

We can similarly count faces of each dimension. Letting the doubly indexed Whitney number of the first kind be w_{ij}(P) = ∑{μ(x, y) : rk x = i, rk(y) = j} (so, e.g., w_{0i} = w_{i} and w_{ii} = W_{i}), we have:

(2.3a)  f_{k}(ℰ) = ∑_{j=d−k}^{d}|w_{d−k,j}(ℒ(ℰ))|,

(2.3b)  b_{k}(ℰ) = | ∑_{j=d−k}^{d}w_{d−k,j}(ℒ(ℰ))|,

and for a projective arrangement,

(2.4a)  f_{k}(𝒜) = \frac{1}{2} ∑_{j=d−k}^{d+1}|w_{d−k,j}(ℒ(𝒜))|

provided k > codim(⋂ 𝒜); if ⋂ 𝒜 = ∅, this

(2.4b)  = (−1)^{k} ∑_{\begin{matrix}j=d−k \\ d−j even \end{matrix}}^{d}|w_{d−k,j}(ℒ(𝒜))|.

It is important in computations to remember that

sgn w_{ij} = (−1)^{j−i}

by Rota’s theorem.

With formulas (2.1–2.4) in hand we can split the task of enumeration into two parts: determining the structure of ℒ(ℋ) from a suitable description, and evaluating its Whitney numbers.

3. Perpendiculars specified by coordinates

Here is the precise problem we want to solve: We have a rule that assigns to any ntuple Q = (Q_{1}, …, Q_{n}) of distinct reference points in Euclidean d-space an arrangement of hyperplanes, ℋ = ⋃_{i<j} ℋ_{ij}, where each h_{ijk} ∈ ℋ_{ij} is perpendicular to the line Q_{i}Q_{j}. The rule consists of \binom{n}{2} sets R_{ij} of real numbers and an exponent α ∈ ℝ. Given an n-tuple (Q_{1}, …, Q_{n}), ℋ_{ij} consists of all those hyperplanes perpendicular to Q_{i}Q_{j} whose foot (the point of intersection with Q_{i}Q_{j}) is a point P for which the quantity

(3.1)  ψ_{ij}(P)d(Q_{i}, Q_{j})^{−α} ∈ R_{ij}.

(In fact, since ψ_{ij}(P)d(Q_{i}, Q_{j})^{−α} is the same for all points P ∈ h if h ⊥ Q_{i}Q_{j}, we may call ψ_{ij}(P) the Pythagorean coordinate of h as a whole.) We want to know the number of regions (and also faces and flats) of the arrangement ℋ. But since this obviously depends on the choice of (Q_{1}, …, Q_{n}), we are content to ask for the answer generically, in the sense discussed in the introduction.

(It is not necessary to assume Q_{i} and Q_{j} are distinct if there is no hyperplane h_{ijk} specified perpendicular to Q_{i}Q_{j}. However, if we allow reference points that are not distinct, we must define Q_{i}Q_{j} to be aff(Q_{i}, Q_{j}), which is a point when Q_{i} = Q_{j}.)

Particular choices for α correspond to the three ways of specifying perpendiculars we mentioned in the introduction. When α = 1, we are specifying twice the signed distance of the foot from the midpoint between Q_{i} and Q_{j}. When α = 2, we are specifying twice the proportional distance. When α = 0, we specify the Pythagorean coordinate of the foot. In each case, R_{ij} specifies the values of the chosen coordinate at which we locate the feet of perpendiculars to Q_{i}Q_{j}. We may think of α as universally fixed, with various choices of {R_{ij} : 1 ≤ i < j ≤ n} leading to various generic enumerative results. If every R_{ij} = {0}, then α is irrelevant and we have the original Good–Tideman arrangement of bisectors.

The fact that there is a unique generic answer to our numerical question, and indeed that the structure of ℒ(ℋ) itself can be determined generically, is significant. In contrast it seems intuitively clear that, if we look at the isomorphism type of the whole arrangement ℋ (as a cell complex whose cells are the faces of ℋ), there is no one generic type. I expect that, when n is large compared with d (written n ≫ d), there are many choices of Q that are generic, in the sense of being deformable without altering the isomorphism type of ℋ, and that yet yield mutually nonisomorphic arrangements. At present this is unproved; we merely offer an example. Example 3.1. In Figure 3.1 we see two generic planar arrangements of all perpendicular bisectors from 4 reference points. Their face complexes are simplicial: all regions are triangular. By comparing the bounded parts one can see that they are nonisomorphic. (The reference points have different convexity types, or oriented matroids: in the first arrangement but not the second, one point is in the convex hull of the others. This may be significant.)

**********************************************************

Place FIGURE 3.1 near EXAMPLE 3.1. **********************************************************

Research Problem 1. Fix d, {R_{ij}}_{ij}, and α. (a) Show that the face complex of ℋ, the arrangement of perpendiculars determined by these data, is (with minor exceptions) not unique even when Q is generic, if n ≫ d. (b) Estimate a lower bound, at least, for the number of distinct isomorphism types of generic face complexes. (c) How large must n be for the generic face complex to be nonunique? (I suggest n > d + 1.)

The results of Section 8 suggest that the answers depend on whether α is 0 or not, but not otherwise on its value. Research Problem 2. Is there a relationship between the structure of the face complex of ℋ and the oriented matroid structure of generic Q_{1}, …, Q_{n}? Example 3.2. (Affinographic arrangements and deformations of a Coxeter arrangement.) A special case of particular importance is that in which d = n and we choose an origin O and reference points Q_{i} so that O⃗Q_{1}, ⋯, O⃗Q_{n} are orthogonal vectors of length \sqrt{2}. These vectors determine coordinates (x_{1}, …, x_{n}). Let P have coordinate vector x. Then ψ_{ij}(P) = ∥x − \sqrt{2}e_{i}∥^{2} − ∥x − \sqrt{2}e_{j}∥^{2} = x_{j} − x_{i} (where e_{i} = O⃗Q_{i}/\sqrt{2}, the unit basis vector), so the hyperplane with Pythagorean equation ψ_{ij}(P) = α has x-equation x_{j} − x_{i} = α. A Pythagorean arrangement is therefore a system of hyperplanes given by equations of the form x_{j} − x_{i} = α for α in some fixed set R_{ij}, specified for each (i, j) with 0 < i < j ≤ n. Such an arrangement we call affinographic, since the hyperplanes are affine translates of those of the arrangement 𝒜_{n} = {x_{j}−x_{i} = 0 : 0 < i < j ≤ n}, which represents the polygon matroid of the complete graph K_{n}. Especially when the constant terms are integers, affinographic arrangements are known as deformations of the Coxeter arrangement 𝒜_{n} [2, 21, 25]. Thus our results apply to deformations of 𝒜_{n}, and conversely, known characteristic polynomials of various deformations of 𝒜_{n} can be applied to other Pythagorean arrangements as explained in Section 10 and illustrated in several examples of Section 11.

Since all affinographic hyperplanes are orthogonal to x_{1} + ⋯ + x_{n} = \sqrt{2}, we can take the cross-section of an affinographic arrangement by the latter hyperplane. This contains all the reference points, so it gives essentially the same arrangement in dimension n − 1, though without the affinographic equations x_{j} − x_{i} = α.

Figure 3.1. Two generic but nonisomorphic arrangements of bisectors in the plane.

4. Perpendiculars via gain graphs

A more convenient way to locate perpendiculars is by a gain graph. A graph Γ consists of a vertex set V = V (Γ) and an edge set E = E(Γ). Multiple edges are permitted, indeed encouraged, but normally we allow only links—that is, edges with two distinct endpoints. V (e) denotes the set of endpoints of an edge e. The (connected) components of an edge set S ⊆ E are the maximal subgraphs of (V, S) that are connected by edges of S, including any isolated vertices, which are called trivial components; c(S) is the number of components of S. A real, additive gain graph Φ (sometimes, for brevity, called here just a “gain graph”) consists of a graph Γ = (V, E) and a gain function, a mapping

φ : {(e; v_{1}, v_{2}) : e ∈ E, {v_{1}, v_{2}} = V (e)} → ℝ^{+}

satisfying

φ(e; v_{2}, v_{1}) = −φ(e; v_{1}, v_{2}).

(ℝ^{+} is the additive group of real numbers.) What this alternating property means is that the gain of e from v_{2} to v_{1} is the inverse of that of e from v_{1} to v_{2}. We define an edge set or subgraph to be balanced if, for every circle (simple closed path) in it, the gains (taken in a consistent direction) sum to 0.

There is a matroid theory of gain graphs extending that for ordinary graphs [30, Part II]. The complete lift matroid is implicit throughout our work here but we refer to it explicitly only in Sections 6 (where we state a definition), 7.2, and 11.

We must show how gain graphs are related to arrangements of perpendiculars.

In one direction, suppose we start with reference points Q = (Q_{1}, …, Q_{n}) and an arrangement ℋ of perpendiculars based on Q. We assume that each hyperplane in ℋ is associated with a specific reference line Q_{i}Q_{j}. (The association need be explicit only if two such lines are parallel, which will never happen if Q is generic.) The Pythagorean gain graph of ℋ (with respect to the given reference points), Ψ_{Q}(ℋ), has vertex set {1, 2, …, n} and an edge e(h) between vertices i and j for each hyperplane h associated with the reference line Q_{i}Q_{j}. The gain of e(h) is the Pythagorean coordinate of h:

ψ(e(h); i, j) = ψ_{Q}(e(h); i, j) = ψ_{ij}(P),

where P is any point on h.

More important is the other direction. We are given a real, additive gain graph Φ. The Pythagorean hyperplane arrangement of Φ with reference points Q_{1}, …, Q_{n}, written ℋ(Φ; Q_{1}, …, Q_{n}) or ℋ(Φ; Q), is the arrangement of perpendiculars which has, for each edge e ∈ E, a hyperplane h(e) perpendicular to Q_{i}Q_{j}, where {i, j} = V (e), whose Pythagorean coordinate on Q_{i}Q_{j} is φ(e; i, j). Thus the Pythagorean gain graph of ℋ(Φ; Q) is Φ. We think of Φ as a rule that specifies an arrangement of perpendiculars for each choice of reference points, equivalent to the real number sets R_{ij} of the previous section but (as we shall see shortly in Section 5) more natural.

More generally we may wish to specify not the Pythagorean coordinates but some modification such as signed distance or proportional coordinates. Given α ∈ ℝ and Φ, the arrangement of perpendiculars ℋ(α, Φ; Q) is defined as ℋ(Ψ; Q) where Ψ has gain function ψ(e; i, j) = d(Q_{i}, Q_{j})^{α}φ(e; i, j). Thus the Pythagorean coordinate of a hyperplane h(e) in ℋ(α, Φ; Q) is d(Q_{i}, Q_{j})^{α}φ(e; i, j) and Ψ = Ψ_{Q}(ℋ(α, Φ; Q)), the Pythagorean gain graph. We think of (α, Φ) as a modified Pythagorean rule that determines an arrangement of perpendiculars on any given reference points. Again Φ is equivalent to the real number sets of Section 3, but it is not normally the Pythagorean gain graph of the arrangement unless α = 0.

In only one place we allow loops to appear, momentarily: when we contract, in Section 7.2. A loop’s geometric interpretation depends on its gain. A loop with gain 0 corresponds to the whole space 𝔼^{d}, which one might call the “degenerate hyperplane”. If 𝔼^{d} is among the “hyperplanes” of ℋ, our convention is that there are no regions, since the complement of the hyperplanes is void; but there still are d-faces, since they are regions of the flat s = 𝔼^{d}. A loop with nonzero gain corresponds to the ideal hyperplane h_{∞}, hence to nothing in 𝔼^{d}. For that reason we always discard such loops. Example 4.1. Figure 4.1 shows a gain graph Φ, four planar reference points, and the associated Pythagorean hyperplane arrangement ℋ(Φ; Q). We write e_{ij} for an edge with endpoints i and j and, when necessary, e_{ij}(ρ) to distinguish an edge e_{ij} with gain ρ = φ(e_{ij}; i, j). Our ℋ(Φ; Q) is generic because it has the generic intersection pattern required by Theorem 5.1: since Φ has the single balanced circle e_{12}e_{24}(3)e_{14}, h(e_{12}) ∩ h(e_{24}(3)) ∩ h(e_{14}) is a multiple point of intersection; furthermore, generically there can be no other multiple points and Figure 4.1. A gain graph and an associated generic Pythagorean line arrangement. (In the gain graph, the number by an edge is its gain. The arrow indicates the direction for reading the gain, so reversing direction negates the gain. The arrow may be omitted if the gain is 0.)

no parallel flats except those implied by parallel edges like e_{24}(0) and e_{24}(3), which make h(e_{24}(0)) ∥ h(e_{24}(3)). (The fact that h(e_{24}(3)) passes through Q_{3} in this example is a coincidence that implies nothing about the hyperplane arrangement.)

**********************************************************

Place FIGURE 4.1 near EXAMPLE 4.1. **********************************************************

The foot P of a hyperplane h(e_{ij}) is positioned so that ψ_{ij}(P) = φ(e_{ij}; i, j). In practice it may be easier to locate P by its signed distance from the midpoint M_{ij} of Q_{i}Q_{j}: this is d(M_{ij}, P), taken as positive toward Q_{j} and negative toward Q_{i}. The formula for signed distance from a Pythagorean gain graph Φ is

d(M_{ij}, P) = \frac{1}{2}φ(e_{ij}; i, j)/d_{ij},

where d_{ij} = d(Q_{i}, Q_{j}).

Example 4.2. In Figure 4.2 is a generic non-Pythagorean arrangement ℋ(1, Φ; Q). It is described by a gain graph Φ interpreted as specifying twice the signed distance of h(e); that is, d(M_{ij}, P) = \frac{1}{2}φ(e; i, j). (See the previous example for notation.) In the Pythagorean gain graph Ψ = Ψ_{Q} of ℋ(1, Φ; Q), the gains are ψ(e; i, j) = d_{ij}φ(e; i, j). The only concurrence of lines is that of the three bisectors, which correspond to the balanced triangle in Ψ made up of the edges with gain 0.

**********************************************************

Place FIGURE 4.2 near EXAMPLE 4.2. **********************************************************

5. Pythagorean perpendiculars

Here is our central result. Theorem 5.1. Let n > d ≥ 1, let Φ be a real, additive gain graph on vertex set {1, …, n}, and for distinct points Q_{1}, …, Q_{n} ∈ 𝔼^{d} let ℋ = ℋ(Φ; Q_{1}, …, Q_{n}) be the arrangement of perpendiculars based on Q_{1}, …, Q_{n} with Φ as its Pythagorean gain graph. Suppose Q_{1}, …, Q_{n} are generic. Then the intersection of a subset 𝒮 ⊆ ℋ corresponding to an edge set S of Φ with n − m connected components is void if S is unbalanced or if m > d; otherwise it is a nonempty flat of dimension d − m.

Furthermore, two subsets 𝒮_{1} and 𝒮_{2} have the same nonvoid intersection if and only if S_{1} ∪ S_{2} is balanced and the connected components of S_{1} and S_{2} each partition the vertices (into at least n − d parts) in the same way.

Note that whether Q_{1}, …, Q_{n} are generic depends on the particular Φ. What we assert is that for each Φ a generic choice exists and has certain describable intersection properties.

The proof depends on several lemmas. The first two show, by demonstrating the close connection of balanced circles in Ψ_{Q}(ℋ) to nonvoid hyperplane intersections, exactly why gain graphs are such a natural way to describe Pythagorean arrangements.

In the proof we assume that Q_{i} and Q_{j} are distinct if i and j are adjacent in Φ, but we assume nothing if i and j are nonadjacent. Lemma 5.2. Suppose C is a circle in Φ and 𝒞 is the corresponding set of hyperplanes in ℋ(Φ; Q). If C is unbalanced, ⋂ 𝒞 = ∅. If C is balanced and e ∈ C, then ⋂ 𝒞 = ⋂ (𝒞 \ {h(e)}).

Proof. Take C = e_{12}e_{23} ⋯ e_{l,l+1}e_{l+1,1} and e = e_{l+1,1}. Let s = ⋂(𝒞\{h(e)}). For any point P ∈ s,

(5.1)  ψ_{l+1,1}(P) = −[ψ_{12}(P) + ⋯ + ψ_{l,l+1}(P)]

by (1.2). The numbers ψ_{i,i+1}(P) = ψ(e_{i,i+1}) for i = 1, 2, …, l by definition of h(e_{i,i+1}). If C is balanced, then by (5.1) all of s lies in h(e_{l+1,1}). If not, no point of s is in h(e_{l+1,1}). □

Figure 4.2. A gain graph Φ; an associated generic non-Pythagorean arrangement ℋ(α, Φ; Q) having n = 3, d = 2, and α = 1; and the Pythagorean gain graph Ψ = Ψ_{Q} of the arrangement. The distances among the reference points are d_{12} = 2, d_{23} = 3, and d_{13} = \frac{5}{2}.

Lemma 5.3. In the situation of Lemma 5.2, suppose Q_{1}, …, Q_{l+1} are affinely independent. If C is balanced, then ⋂ 𝒞 is a (d − l)-flat.^{3}

Proof. Because Q_{1}, …, Q_{l+1} are affinely independent, l hyperplanes perpendicular to Q_{1}Q_{2}, …, Q_{l}Q_{l+1} are linearly independent. Thus their intersection is (d − l)-dimensional. Now the lemma follows from Lemma 5.2. □

Lemma 5.4. Suppose ⋂ ℋ(Φ; Q) has nonempty intersection s. Then (a) Φ is balanced, and (b) s is the intersection of a subset 𝒮 of d − dim s hyperplanes. Any such subset corre-

3Lemmas 5.2 and 5.3 in the planar case of three vertices of a triangle with one perpendicular’s foot on each extended edge of the triangle have been known to triangle geometers. See for instance [8] and [10, §1.5, Exer. 7]. Although [8] is the earliest source I know, in Clark Kimberling’s opinion (personal information, 1984) the planar theorem is many decades older; that is not hard to believe since it has the appearance of an easy exercise.

sponds to a forest S in Φ.

Proof. For part (a), consider an unbalanced circle C in Φ. By Lemma 5.2, the hyperplanes corresponding to the edges of C have empty intersection.

For part (b), 𝒮 exists, of size codim s but no less, by the modular law of dimension in ℙ^{d} applied to s_{ℙ}. By Lemma 5.2, the minimality of 𝒮 prevents S from containing a balanced circle. □

Let p_{ij} denote the ideal point on Q_{i}Q_{j}, that is (Q_{i}Q_{j})_{(∞)}, where s_{(∞)} means s_{ℙ} ∩ h_{∞}. (If Q_{i} = Q_{j}, then p_{ij} = ∅. For the meaning of this, see Section 6.1.) Let s → s^{∗} denote the natural polarity of ideal subspaces, viz. p_{ij}^{∗} = (h_{ij})_{(∞)} for any hyperplane h_{ij} ⊥ Q_{i}Q_{j} and, for a general subspace s of h_{∞}, s^{∗} = t_{(∞)} where t is any orthogonal complement of any affine space s′ whose ideal part s′_{(∞)} equals s. We can regard the points p_{ij} as the edges of a graph on the vertex set {1, …, n}, identified with {Q_{1}, …, Q_{n}}. Let 𝒫 denote the set of all p_{ij}. Lemma 5.5. Given an n-tuple Q = (Q_{1}, …, Q_{n}) of distinct points in 𝔼^{d} and a set T ⊆ 𝒫, we have

(5.2)  dim T ≤ min(n − c(T) − 1, d − 1)

The class of n-tuples Q such that equality holds for all T has the property of genericity; that is, it is open and dense in (𝔼^{d})^{n}. It excludes all nonsimple n-tuples Q.

Proof. Let 𝒢 be the set of Q having equality in (5.2).

Consider a component T_{k} of T with vertex set {i_{1}, …, i_{r}}. It is easy to see that T_{k} spans the space t_{k} = aff(Q_{i_{1}}, …, Q_{i_{r}})_{(∞)}, whose dimension is ≤ r − 2. Summing over all components yields (5.2).

If Q is not simple, say Q_{1}, Q_{2}, …, Q_{r} are a minimal affinely dependent subset with r ≤ d + 1. Let T = {p_{12}, p_{23}, …, p_{r−1,r}}. Then dim T = dim aff(Q_{1}, …, Q_{r}) − 1 = r − 3, but n − c(T) = r − 1. So Q ∉ 𝒢.

We wish to prove that 𝒢 is open and dense. For an n-tuple Q = (Q_{1}, …, Q_{n}), let D(Q) = {T ⊆ 𝒫 : T has strict inequality in (5.2) and n − c(T) ≤ d}. If D(Q) is empty, then (5.2) holds with equality for all T ⊆ 𝒫. Moving any points of Q very slightly will not reduce the dimension of any set T; thus 𝒢 is open; furthermore, for an arbitrary Q, D(Q′) ⊆ D(Q) if Q′ is very near Q.

Suppose now that Q ∉ 𝒢. If Q is not simple, an arbitrarily slight deformation of its points Q_{1}, …, Q_{n} will make it so. Thus we can assume simplicity. So, if T_{k} is a component of T with n−c(T) ≤ d, and T_{k} has vertices i_{1}, …, i_{r}, then t_{k} = aff(Q_{i_{1}}, …, Q_{i_{r}})_{(∞)} has dimension r − 2. If T is a minimal element of D(Q) with nontrivial components T_{1}, …, T_{m}, then

dim(t_{1} ∪ ⋯ ∪ t_{m−1}) = ∑_{1}^{m−1} dim t_{k}

while

dim(t_{1} ∪ ⋯ ∪ t_{m}) < ∑_{1}^{m} dim t_{k} = dim(t_{1} ∪ ⋯ ∪ t_{m−1}) + dim(t_{m}).

But t_{m} is determined by points Q_{i_{1}}, …, Q_{i_{r}} which have no effect on t_{1} ∪ ⋯ ∪ t_{m−1}. Thus by varying these points (arbitrarily slightly) to positions Q′_{i_{1}}, …, Q′_{i_{r}} we can make the dimension of (t_{1} ∪ ⋯ ∪ t_{m−1}) ∪ t_{m} equal to its maximum value of ∑_{1}^{m} dim t_{k}. The new n-tuple Q′ will have D(Q′) ⊂ D(Q). Continuing in this way we can find Q′′ ∈ 𝒢 arbitrarily near to Q. Thus 𝒢 is dense. □

If Q = (Q_{1}, …, Q_{n}) satisfies (5.2) with equality, we say Q, or Q_{1}, …, Q_{n}, have ideal general position. This is a strong kind of affine general position, ruling out all unnecessary parallelisms. Lemma 5.5 allows us to restrict our consideration of the general form of perpendicular arrangements described by a fixed Φ to those Q in ideal general position.

We shall need the dual formulation. Recall that 𝒮_{ℙ} contains h_{∞} by definition. Lemma 5.6. Let 𝒮 ⊆ ℋ(Φ; Q), corresponding to S ⊆ E(Φ). Then

dim(⋂ 𝒮_{ℙ}) ≥ max(d − 1 − [n − c(S)], −1),

with equality if Q has ideal general position.

Proof. Dulaize Lemma 5.5. □

Lemma 5.7. Let 𝒮 ⊆ ℋ(Φ; Q) correspond to a forest S ⊆ E(Φ) with m edges where m ≤ d. Assume Q has ideal general position. Then dim(⋂ 𝒮) = d − m.

Proof. Let s = ⋂ 𝒮, s′ = ⋂{h_{ℙ} : h ∈ 𝒮}, and s′′ = ⋂ 𝒮_{ℙ}. We know dim s′′ = d − m − 1 since c(S) = n − m.

The proof is by induction on m. The base cases m = 0, 1 are trivial. Thus let 1 < m ≤ d. Choose e ∈ 𝒮 and set T = S \ {e}, 𝒯 = 𝒮 \ {h(e)}, t = ⋂ 𝒯, and t′′ = ⋂ 𝒯_{ℙ}. By induction, dim t = d − m + 1. Thus dim t′′ = d − m.

Now, either s = t, or ∅ ≠ s ⊂ t and dim s = dim t − 1, or s = ∅. The last case is impossible, for s = ∅ ⟹ s′ ⊆ h_{∞} ⟹ s′′ = s′, whence dim s′ = d − m − 1, contradictiing the fact that dim s′ ≥ dim t − 1 by the modular law. The first case is impossible because s = t ⟹ s′ = t′ ⟹ s′′ = t′′, but dim s′′ ≠ dim t′′. Therefore ∅ ≠ s ⊂ t and dim s = dim t − 1. □

Lemma 5.8. Let 𝒮 ⊆ ℋ(Φ; Q) correspond to a forest S ⊆ E(Φ) with m edges where m > d. Assume Q has ideal general position. Then dim(⋂ 𝒮) is a point or void, and for generic Q it is void.

Proof. That ⋂ 𝒮 is contained in a point follows directly from Lemma 5.7.

Let 𝒢 be the set of all Q ∈ (𝔼^{d})^{n} that have ideal general position and for which ⋂ 𝒮 = ∅. We need to show that 𝒢 is open and dense in (𝔼^{d})^{n}.

If ⋂ 𝒮 = ∅, shifting Q slightly will leave it so. Thus 𝒢 is open.

Suppose ⋂ 𝒮 is a point P. We show how to deform Q to make ⋂ 𝒮 empty. Let i be an end vertex in S, e its incident edge, j its neighbor, and T = S \ {e}. Then ⋂ 𝒯 = {P } by induction if m > d + 1 or Lemma 5.7 if m = d + 1. The hyperplane h(e) contains P; thus

d(P, Q_{i})^{2} = d(P, Q_{j})^{2} + φ(e; i, j).

If we shift Q_{j} slightly off the cylinder described by this equation, ⋂ 𝒮 becomes empty. This proves that 𝒢 is dense. □

Example 5.1. In Lemma 5.8 it is indeed possible that ⋂ 𝒮 be a point. Here is an example in the plane. Take a point P and three lines through P making small angles, say l_{1}, l_{2}, l_{3} with l_{2} between the other two lines. Choose a foot P_{2} on l_{2} at some distance from P and erect a short perpendicular segment on P_{2}, bisected by l_{2} and not intersecting either other line. Call its endpoints Q_{2} (nearer to l_{1}) and Q_{3} (nearer to l_{3}). From Q_{2} drop a perpendicular to Figure 5.1. A nongeneric arrangement of lines whose reference points nevertheless have ideal general position.

l_{1} and continue it slightly past l_{1} to a point Q_{1}. Similarly, drop a perpendicular to l_{3} from Q_{3} and continue it to Q_{4}. The reference points Q_{1}, Q_{2}, Q_{3}, Q_{4} are plainly in ideal general position; the perpendiculars l_{1}, l_{2}, and l_{3} to Q_{1}Q_{2}, Q_{2}Q_{3}, and Q_{3}Q_{4} are described by their Pythagorean gain graph Ψ which is a tree of 3 edges; yet l_{1}, l_{2}, l_{3} are concurrent.

**********************************************************

Place FIGURE 5.1 near EXAMPLE 5.1. **********************************************************

Examples like this show that Lemma 5.8 is where ideal general position ceases to be sufficient for genericity of Q. Lemma 5.9. Let Φ be a fixed Pythagorean gain graph. Let Q = (Q_{1}, …, Q_{n}) have ideal general position in 𝔼^{d}, where n > d ≥ 1. Take a subset 𝒮 ⊆ ℋ(Φ; Q), corresponding to an edge set S of Φ. Then ⋂ 𝒮 is a nonempty subspace of dimension d − (n − c(S)) if S is balanced and has c(S) ≥ n − d, it is a point or void (and it is void for generic Q) if S is balanced and c(S) < n − d, and it is void if S is unbalanced.

Proof. Suppose S contains a balanced circle. By Lemma 5.2 we can remove an edge of C from S without changing either the intersection of the hyperplanes or the number of components of S. So we may as well assume S contains no balanced circle.

If S contains an unbalanced circle, then ⋂ 𝒮 = ∅ by Lemma 5.4.

The remaining case is that of a forest, which is treated in Lemma 5.8. □

Proof of Theorem 5.1. For each S ⊆ E(Φ) let 𝒢(S) be the set of n-tuples Q for which 𝒮 has intersection as described in Lemma 5.9. There are finitely many of these sets 𝒢(S), each open and dense in (𝔼^{d})^{n}; thus their intersection 𝒢 is open and dense as well. Since every Q ∈ 𝒢 has the intersection properties in the first part of the theorem, these properties are generic, as claimed.

As for the second half of the theorem, where ⋂ 𝒮_{1} = ⋂ 𝒮_{2} ≠ ∅, this makes both intersections equal to ⋂(𝒮_{1} ∪ 𝒮_{2}). Thus S_{1} ∪ S_{2} is balanced, n − c(S_{1} ∪ S_{2}) ≤ d, and c(S_{1} ∪ S_{2}) = c(S_{1}) = c(S_{2}). The latter entails that S_{1} and S_{2} induce the same partition of the vertex set. □

We are—at last—able to state a precise definition of genericity, or “completely general position,” of Q_{1}, …, Q_{n}. Definition. Let Φ be a real, additive gain graph. Points Q_{1}, Q_{2}, …, Q_{n} have general position with respect to Φ if ℋ(Φ; Q) satisfies the criteria for genericity of Theorem 5.1. They have completely general position with respect to Φ if they have both ideal general position and general position with respect to Φ.

6. Matroids and general position

6.1. Variations on general position. Re-expressing our results in terms of matroids is technical but illuminating (for matroid theorists) and makes it possible to prove a number of interesting facts with little difficulty. The essential matroids are G(Γ), the graphic (polygon) matroid of a graph Γ, and L_{0}(Φ), the complete lift matroid of the gain graph Φ. The point set of L_{0}(Φ) is E ∪ {e_{0}}, where e_{0} ∉ E, and its rank function is rk(S) = n − c(S \ {e_{0}}) + ε for S ⊆ E ∪ {e_{0}}, where ε = 0 if S is a balanced subset of E and 1 otherwise. For more about balanced flats and L_{0} we refer to [30, §§II.2, II.3]. The geometric lattice of flats of a matroid M is denoted by Lat M and the geometric semilattice of balanced flats of L_{0}(Φ) is Lat^{b} Φ. Truncation of a matroid or of its lattice of flats to rank r is denoted by T_{r}; this means the elements of ranks r and higher, if any, are replaced by the single element ˆ1.

We begin with six definitions of general position of Q. The first four restate those already given in Sections 1 and 5. Recall that 𝒫 is the set of all ideal points p_{ij} on the reference lines Q_{i}Q_{j}. Its projective dependence matroid is M(𝒫).

• Simple position (SP):

The matroid of the reference points is the uniform matroid of rank min(n, d + 1).

• Ideal general position (IGP):

M(𝒫) ≅ T_{d}(G(K_{n})), the matroid of the complete graph truncated to rank d, under the canonical correspondence p_{ij} ↔ ij. (IGP entails that all reference points are distinct, since by our definition that Q_{i}Q_{j} = aff(Q_{i}, Q_{j}), p_{ij} = (Q_{i}Q_{j})_{(∞)} = ∅ if Q_{i} = Q_{j}. Then p_{ij} is, in effect, a matroid loop in M(𝒫), which consequently is not isomorphic to T_{d}(G(K_{n})), not even when d = 1.)

• General position with respect to Φ (GP):

ℒ(ℋ(Φ; Q)) ≅ [Lat^{b} Φ]_{0}^{d}, the geometric semilattice consisting of ranks 0 through d of Lat^{b} Φ, under the canonical correspondence h(e) ↔ e.

• Completely general position with respect to Φ (CGP):

The combination of IGP and GP.

• Projective general position with respect to Φ (PGP):

ℒ(ℋ_{ℙ}(Φ; Q)) ≅ T_{d+1}(Lat L_{0}(Φ)) under the canonical correspondence h(e) ↔ e and h_{∞} ↔ e_{0}.

• Projective completely general position with respect to Φ (PCGP): The combination of IGP and PGP.

The meaning of Theorem 5.1 is that, generically, Q has GP. We can say more. Theorem 6.1. Let Φ be a fixed real, additive gain graph on n vertices. Assume n > d ≥ 1. Generically, n reference points Q_{1}, …, Q_{n} in 𝔼^{d} have completely general position and projective completely general position with respect to Φ.

Proof. GP is a translation of Theorem 5.1 into the language of gain-graphic matroids. PGP is equivalent to GP by Theorem 6.3(ii). IGP is a generic property of n points by [18, §2.1], as we explain in the proof of Proposition 6.6. □

Proposition 6.2. If Q has ideal general position and, for every 𝒮 ⊆ ℋ that corresponds to a forest of d + 1 edges in Φ, ⋂ 𝒮 is empty, then Q has general position with respect to Φ.

Proof. This follows from Lemma 5.9 and its proof. □

We should like to say something about the relationships among these several notions of general position. We saw in Example 5.1 that IGP does not imply GP. This suggests that both are needed in the definition of completely general position. Still, IGP is redundant if Φ is complete, that is, every pair of vertices is adjacent. We call Φ separable if it has a vertex v such that Φ \ v is disconnected. Theorem 6.3. Given: a real, additive gain graph Φ on n vertices and points Q_{1}, …, Q_{n} ∈ 𝔼^{d}.

(i) Ideal general position implies simple position.

(ii) General position and projective general position with respect to Φ are equivalent. (iii) Completely general position and projective completely general position with re-

spect to Φ are equivalent. (iv) General position with respect to Φ implies ideal general position if Φ is complete,

but not if Φ is disconnected or separable.

Proof. We prove (i) by contradiction. Suppose a set D of Q_{i}’s is minimally affinely dependent and has δ = |D| ≤ d + 1. Then dim D = δ − 2 ≤ d − 1. IGP implies that 𝒫(D) = {p_{ij} : Q_{i}, Q_{j} ∈ D} has matroid T_{d}(G(K_{δ})), so dim 𝒫(D) = min(d − 1, δ − 2) = δ − 2. But 𝒫(D) ⊆ (aff D)_{(∞)}, whose dimension = dim D − 1 = δ − 3. Thus no such D can exist.

For the rest we need a basic fact from [26]. [x, y] denotes the interval from x to y.

Lemma 6.4 (Wachs and Walker [26, Thm. 3.2]). Up to isomorphism, a geometric semilattice has the form L \ [e_{0}, ˆ1] for one and only one geometric lattice L and atom e_{0} of L.

In other words, a geometric semilattice determines the whole geometric lattice of which it is a part. This is very important.

Here is how we use Lemma 6.4. Set ℋ = ℋ(Φ; Q_{1}, …, Q_{n}). First we note that [Lat^{b} Φ]_{0}^{d} = T_{d+1}(Lat L_{0}(Φ))\[e_{0}, ˆ1], so T_{d+1}(Lat L_{0}(Φ)) is determined by [Lat^{b} Φ]_{0}^{d}. Second, ℒ(ℋ) determines ℒ(ℋ_{ℙ}) since it equals ℒ(ℋ_{ℙ}) \ [h_{∞}, ˆ1]. Combining these, GP ⟹ PGP. The converse is trivial. Thus we have proved (ii) and (iii).

For (iv) the essential fact is that (Lat L_{0}(Φ))/e_{0} (the interval above e_{0}) equals Lat G(Γ) if Γ is the underlying graph of Φ. Since ℒ(ℋ_{ℙ}^{h_{∞}}), where ℋ_{ℙ}^{h_{∞}} = {h_{ℙ}∩h_{∞} : h ∈ ℋ}, is the interval [h_{∞}, ˆ1] ⊆ ℒ(ℋ_{ℙ}), we know that ℒ(ℋ_{ℙ}^{h_{∞}}) ≅ T_{d}(Lat G(Γ)) under the canonical correspondence h(e)_{(∞)} ⟷ the atom of Lat G(Γ) that contains e. If Φ is complete, Lat G(Γ) = Lat G(K_{n}), so we are done.

The assertions about disconnected and separable Φ follow from Example 6.1. □

Example 6.1. Let Φ be a gain graph that is the union of Φ_{1} and Φ_{2} where |V_{1} ∩ V_{2}| = δ ≤ 1, n_{1} = |V_{1}| ≥ 2, and n_{2} = |V_{2}| ≥ 2. Then n = |V | = n_{1} + n_{2} − δ. Choose d_{1}, d_{2} > 0 so that d = d_{1} + d_{2} satisfies n ≥ d + 3 − δ. Choose reference points Q_{1}^{(k)}, …, Q_{n_{k}}^{(k)} ∈ 𝔼^{d_{k}} for ℋ^{(k)} = ℋ(Φ_{k}; Q_{1}^{(k)}, …, Q_{n_{k}}^{(k)}) that have general position with respect to ℋ_{k}. Now embed 𝔼_{d_{1}} into 𝔼^{d} as 𝔼_{d_{1}} × {0} and embed 𝔼_{d_{2}} into 𝔼^{d} as {0} × 𝔼_{d_{2}}. If δ = 1, choose coordinates in each 𝔼^{d_{k}} so that Q_{1}^{(k)} is at the origin; then the embedding identifies Q_{1}^{(1)} and Q_{1}^{(2)}. If δ = 0, choose coordinates so no Q_{i}^{(k)} is at the origin.

There is an affinely dependent subset of Q_{1}^{(k)}, …, Q_{n_{k}}^{(k)} if n_{k} ≥ d_{k} + 2. The only way to avoid this for both k = 1 and k = 2 is to have n_{1} + n_{2} ≤ d + 2, contrary to our choice of d. Thus the set of all n reference points has nonsimple position in 𝔼^{d}.

This analysis overlooks the cases in which n_{1} or n_{2} = 1, but they are trivial. Example 6.2. It would be nice to have also an example in which the reference points have simple position as well as general position with respect to Φ but not ideal general position. Such examples exist at least for nontrivially disconnected gain graphs. We outline one such example.

The idea is to embed 𝔼^{d_{1}} and 𝔼^{d_{2}} in 𝔼^{d} as in Example 6.1 and then to find a line and parallel hyperplane h_{Q} that are affinely spanned by the reference points. To assure simple position we must take d_{k} = n_{k} −1 > 0 so d = n−2. The line is Q_{1}^{(1)}Q_{1}^{(2)}; the remaining points span the hyperplane h_{Q}. In general we expect Q_{1}^{(1)}Q_{1}^{(2)} and h_{Q} to meet in 𝔼^{d}. However, if we apply a dilatation around Q_{1}^{(2)} to 𝔼^{d_{2}} with expansion factor λ > 0, then generically there will be a choice of λ that makes Q_{1}^{(1)}Q_{1}^{(2)} ∥ h_{Q}. That precludes IGP, as Proposition 6.6 will show. Example 6.3. Let d = 2 and n ≥ 4 and take Φ = (K_{n} \ e_{12}, 0), that is, the complete graph less one edge, all edges having gain 0. The corresponding hyperplane arrangement consists of all but one of the perpendicular bisectors between n points in the plane.

Choose the reference points so that Q_{1}Q_{2} ∥ Q_{3}Q_{4} but there are no other parallelisms. The reference points do not have IGP because p_{12} = p_{34}, so M(𝒫) ≠ T_{2}(M(K_{n})). Since the arrangement of bisectors can clearly be made to have general position with respect to Φ by deforming the reference points slightly without losing the one required parallelism, we have an example in which Φ is as nearly complete as possible, yet which violates the conclusion of Theorem 6.3(iv).

However, I have not seen how to make such an example in dimension d > 2. Thus it is still possible that the hypothesis of completeness can be weakened in higher dimensions.

These examples give some idea of the interrelations between simple and ideal general position on the one hand and general position with respect to Φ on the other, but they leave us far from a complete understanding. Here are some obvious questions. Research Problem 3. (a) Is it possible to have GP and SP but not IGP with n > d + 2? If Φ is connected?

(b) Show that it is possible to have GP without IGP for inseparable gain graphs, in particular those with 2-separations (and enough vertices). Proposition 6.5. If the reference points are affinely independent, they have completely general position with respect to any gain graph of order n.

Proof. It is clear that they have ideal general position, indeed M(𝒫) = G(K_{n}). Since n ≤ d + 1, Φ cannot contain a forest of d + 1 edges. So Proposition 6.2 is vacuously satisfied. □

6.2. At infinity. It may not be clear from our definition that ideal general position has any connection with parallelism. Here we settle that. A parallelism within reference points Q_{1}, …, Q_{n} ∈ 𝔼^{d} means a pair of flats, f and g, generated by reference points so that neither is a point and ∅ ≠ f_{ℙ} ∩ g_{ℙ} ⊆ h_{∞}. Equivalently, d > dim f, dim g > 0 and dim f + dim g ≥ dim aff(f ∪ g), but f ∩ g = ∅.

Again we employ the convenient, short notation s_{(∞)} = s_{ℙ} ∩ h_{∞} for an affine flat s.

Proposition 6.6. Points Q_{1}, …, Q_{n} ∈ 𝔼^{d} have IGP if and only if they have no parallelisms.

Proof. Call a projective hyperplane singular if it contains either a reference point or the intersection of two flats that are generated by reference points and have nonempty intersection. We can interpret the existence of a parallelism as resulting from having the reference points fixed in advance and choosing the ideal hyperplane so that it is singular although it contains no reference point.

A theorem of Mason ([18, §2.1], or see [6, Prop. 7.7.8]) says that, if n points in ℙ^{d} have matroid M, then a nonsingular hyperplane intersects the lines generated by those points in a point set whose matroid is D_{1}(M), the first Dilworth lower truncation of M. In our case M = U_{d+1}(n), the uniform matroid, so D_{1}(M) = T_{d+1}(G(K_{n})). Thus if there are no parallelisms within the reference points, then M(𝒫) = T_{d}(G(K_{n})). That proves IGP.

Suppose on the other hand that the reference points have IGP (hence simple position) and yet h_{∞} is singular without containing a reference point. Say h_{∞} ⊇ f_{ℙ} ∩ t_{ℙ}, where f and g are spanned by k and l reference points, respectively, with 2 ≤ k, l ≤ d. Then dim f = k − 1, dim g = l − 1, dim(f ∪ g) = min(d, k + l − 1), and dim(f_{ℙ} ∩ g_{ℙ}) = k + l − 2 − dim(f ∪ g) = max(k+l−d−2, −1). Since f_{ℙ}∩g_{ℙ} ≠ ∅, k+l−d−2 ≥ 0; that is, k+l ≥ d+2. Now, there are \binom{k}{2} lines determined by the generators of f and \binom{l}{2} determined by the generators of g, which meet h_{∞} in a set 𝒫′ of points whose matroid, by IGP, is T_{d}(G(K_{k} ∪ K_{l})), where the union is disjoint. This matroid has rank = min(k + l − 2, d) = d, whence dim 𝒫′ = d − 1. Yet 𝒫′ lies in (f_{(∞)}) ∪ (g_{(∞)}), whose dimension is dim(f_{ℙ} ∩ h_{∞}) + dim(g_{ℙ} ∩ h_{∞}) − dim(f_{ℙ} ∩ g_{ℙ} ∩ h_{∞}) = dim f + dim g − 2 − dim(f_{ℙ}∩ g_{ℙ}) = dim(f ∪ g) − 2 ≤ d − 2. Thus IGP contradicts singularity of h_{∞}; we deduce the backward implication of the proposition. □

6.3. Ideal points. To study dissections within a flat (Section 7.2) we need more information about the set 𝒫 and especially about its subsets

𝒫(s) = {p_{ij} : ∃e for which V (e) = {i, j} and h(e) ⊇ s}

for s ∈ ℒ(ℋ(Φ; Q)) and

𝒫(S) = {p_{ij} : [i] = [j] in π(S)},

where π(S) is the partition of V induced by the edge set S in Φ. Recalling that E(s) = {e ∈ E(Φ) : h(e) ⊇ s}, it is clear that

𝒫(s) ⊆ 𝒫(E(s)).

Lemma 6.7. For a point p_{ij} ∈ 𝒫 and a flat s ∈ ℒ(ℋ(Φ; Q)), the following properties are equivalent:

(i) p_{ij} ∈ s_{(∞)}^{∗}.

(ii) There is a hyperplane h ⊥ Q_{i}Q_{j} such that h ⊇ s. (iii) Q_{i}Q_{j} ⊥ s (where we assume s is not a point).

Proof. The equivalence of (ii) and (iii) is obvious.

As for that of (i) and (ii), first note that p_{ij} ∈ s_{(∞)}^{∗} ⟺ p_{ij}^{∗} ⊇ s_{(∞)}. Now, in one direction, if h ⊥ Q_{i}Q_{j} and h ⊇ s, then p_{ij}^{∗} = h_{(∞)} ⊇ s_{(∞)}. Conversely, if p_{ij}^{∗} ⊇ s_{(∞)}, let P ∈ s, h_{ℙ} = span(p_{ij}^{∗} ∪ {P }), and h = the finite part of h_{ℙ}. Then h satisfies the conditions of (ii), because h_{(∞)} = p_{ij}^{∗} ⟺ h ⊥ Q_{i}Q_{j}. □

We write proj_{s} P for the orthogonal projection of a point P ∈ 𝔼^{d} into a flat s. Lemma 6.8. If [i] = [j] in π(E(s)), then proj_{s} Q_{i} = proj_{s} Q_{j}.

Proof. Let us first look at the case in which i and j are adjacent by an edge e ∈ E(s). Then h(e) ⊇ s, hence Q_{i}Q_{j} ⊥ s by Lemma 6.7, whence Q_{i} and Q_{j} have the same projection.

In general, [i] = [j] means that i and j are joined by a path i = i_{0}, e_{1}, i_{1}, …, e_{l}, i_{l} = j in E(s). Thus proj_{s} Q_{i_{0}} = proj_{s} Q_{i_{1}} = ⋯ = proj_{s} Q_{i_{l}}. □

Lemma 6.9. 𝒫(E(s)) ⊆ s_{(∞)}^{∗}.

Proof. p_{ij} ∈ 𝒫(E(s)) ⟺ (by definition) [i] = [j] ⟹ (by Lemma 6.8) proj_{s} Q_{i} = proj_{s} Q_{j} ⟺ Q_{i}Q_{j} ⊥ s ⟺ (by Lemma 6.7) p_{ij} ∈ s_{(∞)}^{∗}. □

Lemma 6.10. If Q has ideal general position, then span 𝒫(s) = s_{(∞)}^{∗}.

Proof. First, p_{ij} ∈ 𝒫(s) ⟺ ∃h(e) ⊇ s with V (e) = {i, j} ⟹ p_{ij} ∈ s_{(∞)}^{∗} by Lemma 6.7. Thus 𝒫(s) ⊆ s_{(∞)}^{∗}.

Now we compare dimensions. Because M(𝒫) ≅ T_{d}(G(K_{n})) (by ideal general position) and E(s) is balanced (by Lemma 5.4), dim 𝒫(s) = min(d − 1, rk E(s) − 1). If s is not a point, rk E(s) = codim s ≤ d (by Lemma 5.9) so dim 𝒫(s) = rk E(s) − 1. At the same time, dim s_{(∞)}^{∗} = d−2−dim s_{(∞)} = d−1−dim s = rk E(s)−1. Since this equals dim 𝒫(s) while also 𝒫(s) ⊆ s_{(∞)}^{∗}, 𝒫(s) spans s_{(∞)}^{∗} if s is not a point. If s is a point, then rk E(s) ≥ codim s = d (again by Lemma 5.9), so dim 𝒫(s) = d − 1. Consequently, 𝒫(s) spans h_{∞} = s_{(∞)}^{∗}. □

Proposition 6.11. Suppose Q has ideal general position and s ∈ ℒ(ℋ(Φ; Q)) but s is not a point. Then 𝒫(E(s)) = 𝒫 ∩ span 𝒫(s), the closure of 𝒫(s) in M(𝒫).

Proof. We know that span 𝒫(s) = s_{(∞)}^{∗} ⊇ 𝒫(E(s)) ⊃ 𝒫(s). Thus 𝒫(E(s)) spans s_{(∞)}^{∗}. However, it may not equal 𝒫∩span 𝒫(s) if s is a point, so we now assume dim s > 0. Therefore rk E(s)) = codim s ≤ d − 1, from which we see that dim s_{(∞)}^{∗} > d − 1 so rk 𝒫(E(s)) < d in M(𝒫). Since M(𝒫) ≅ T_{d}(G(K_{n})) and 𝒫(E(s)) (from its definition) corresponds to a flat in G(K_{n}) of rank < d, 𝒫(E(s)) is itself a flat in M(𝒫). That means 𝒫(E(s)) = 𝒫 ∩ span 𝒫(E(s)) = 𝒫 ∩ s_{(∞)}^{∗}. Because 𝒫(s) also spans s_{(∞)}^{∗}, we conclude that 𝒫(E(s)) = 𝒫 ∩ span 𝒫(s), as desired. □

Corollary 6.12. Suppose Q has ideal general position and s ∈ ℒ(ℋ(Φ; Q)) is not a point. Then proj_{s} Q_{i} = proj_{s} Q_{j} ⟺ [i] = [j] in π(E(s)).

Proof. Sufficiency is Lemma 6.8. For necessity, suppose that Q_{i} and Q_{j} have the same porjection. Then Q_{i}Q_{j} ⊥ s, so by Lemma 6.7, ij ∈ s_{(∞)}^{∗}. But then by Proposition 6.11, p_{ij} ∈ 𝒫(E(s)). That is, [i] = [j]. □

7. Cross-sections

Peering into a flat t in 𝔼^{d}, we see it dissected into pieces by the hyperplanes of ℋ(Φ; Q_{1}, …, Q_{n}) that do not contain it. Does this induced dissection result from a Pythagorean arrangement of relative hyperplanes, as Good and Tideman said of certain flats of their original arrangement? Indeed it does—and this will enable us to explain why a flaw in Good and Tideman’s proof does not invalidate their enumerative results. In order to explain how an induced arrangement is Pythagorean, we need notions of contraction and therefore of switching of a gain graph.

7.1. Switching and contraction. A switching function on a real, additive gain graph Φ is simply a function η : V (Φ) → ℝ^{+}. The secret is in how to use it. Switching Φ by η means replacing the gain function φ by φ^{η} whose definition is

φ^{η}(e; i, j) = φ(e; i, j) − η(i) + η(j).

We write Φ^{η} for the switched gain graph. (Since Φ^{η} is unaffected by adding a constant to η, we can always take η ≥ 0.) The difference between ℋ(Φ; Q) and ℋ(Φ^{η}; Q) is in the appearance of offsets in the locations of perpendiculars. Instead of being placed at ψ_{ij}(h) = φ(e; i, j), the hyperplane h(e) is now located at ψ_{ij}(h) = φ(e; i, j) − η(i) + η(j). In full, the relocated h(e) consists of the points P for which

[d(P, Q_{i})^{2} + η(i)] − [d(P, Q_{j})^{2} + η(j)] = φ(e; i, j).

Thus η modifies the location rule by offsetting h(e) along the line Q_{i}Q_{j}. Switching can change the combinatorial type of ℒ(ℋ) and therefore also of ℋ because it can put the reference points into special position with respect to Φ^{η} even though they were general with respect to Φ.

(Pythagorean arrangements of the form ℋ((K_{n}, 0)^{η}; Q) with η ≥ 0 correspond to the weighted Voronoi diagrams known as “power diagrams”. There η(i), sometimes called the “weight of Q_{i}”, is interpreted as the squared radius of a sphere S_{i} centered at Q_{i}; thus d(P, Q_{i})^{2} − η(i) = t_{i}(P)^{2}, the squared length of a tangent from P to S_{i}, provided P lies outside all spheres. The hyperplane h_{ij} is located where t_{i}(P) = t_{j}(P).^{4})

Now we define contraction of a balanced edge set in Φ. Suppose S ⊆ E(Φ) has all zero gains; that is, φ|_{S} ≡ 0. Let π(S) be the partition of the vertices implied by the connected components of (V, S) and let [i] denote the block of π(S) that contains i. The contraction Φ/S has vertex set π(S) and edge set E(Φ) \ S. An edge e with endpoints i, j in Φ has endpoints [i], [j] in Φ/S. (This process may introduce loops. We discard any loops whose gain is nonzero.) Since the definition permits us to contract only zero-gain edges, we need switching to contract an arbitrary balanced edge set S. There is always a switching function η such that φ^{η}|_{S} ≡ 0. We choose such a function, switch Φ by it, and contract S. Thus we get a contraction Φ^{η}/S of Φ. This contraction is not unique: there is a different one for each choice of η (up to an additive constant). (In that respect our definition is more refined than the standard one found, e.g., in [30, §I.5]. Usually it is enough for a gain graph to be specified up to switching; thus Φ and Φ^{η} would be equivalent and it would not matter how we switch Φ because all contractions Φ^{η}/S would also be equivalent. But that is not so here, since switching changes the hyperplane arrangement. In discarding nonzero loops our definition is cruder than the usual one; we delete them because they correspond to nothing in 𝔼^{d}.) A fact we shall have use for is that, if Φ is balanced, then Φ/S is again balanced.

4Nonnegative weights have a long history; see [3] or [12, Section 13.6]. Arbitrary real weights appear to be rare (an exception is [1]), possibly because they do not have the nice power-diagram interpretation. The literature, however, concerns only nearest reference points (as weighted, i.e., after allowing for offsets) and variations in the same spirit and consequently uses only pieces of dissecting hyperplanes instead of entire hyperplanes. It is also limited to what we should call all-zero gains.

We also need collapsing by a partition π of the vertex set [n]: we take Φ/π to be the gain graph with the same edges and the same gain function as in Φ but with all the vertices in each block of π identified to a point and with all loops removed. This is much like contraction, but for consistency with general custom we confine the latter name to contraction by an edge set.

7.2. Dissections within a flat. To describe the induced dissection of an affine flat t we still need a few short definitions. The induced arrangement in t is

ℋ^{t} = {h ∩ t : h ∈ ℋ, h ⊉ t, and h ∩ t ≠ ∅}.

Write proj_{t} P for the orthogonal projection of a point P into t and let π(t) be the partition of [n] that corresponds to the equivalence relation defined by i ∼ j if proj_{t} Q_{i} = proj_{t} Q_{j}. Set η_{t}(i) = d(Q_{i}, t)^{2}. Theorem 7.1. Take a fixed real, additive gain graph Φ of order n and points Q_{1}, …, Q_{n} ∈ 𝔼^{d}. Let ℋ = ℋ(Φ; Q_{1}, …, Q_{n}). For an affine flat t, let Q̄_{1}, …, Q̄_{k} be the distinct points proj_{t} Q_{i}; thus k = |π(t)|. Then

ℋ^{t} = ℋ(Φ^{η_{t}}/π(t); Q̄_{1}, …, Q̄_{k}).

If t is generic of codimension d′, then ℒ(ℋ^{t}) is isomorphic to the semilattice of all flats of ℋ of dimension at least d′.

Furthermore, if Q_{1}, …, Q_{n} have ideal general position, then Q̄_{1}, …, Q̄_{k} also have it. Lemma 7.2. For a hyperplane h(e) ∈ ℋ, corresponding to an edge e with V (e) = {i, j}, to have h(e) ⊇ t or h(e) ∩ t = ∅ it is necessary and sufficient that proj_{t} Q_{i} = proj_{t} Q_{j}.

(This is a version of Corollary 6.12 suitable for arbitrary affine flats.)

Proof. Let us compare a point P ∈ t to the trace in t of h(e), where V (e) = {i, j}. We write Q_{i}^{t} = proj_{t} Q_{i}. We have

d(Q_{i}, P)^{2} = d(Q_{i}, Q_{i}^{t})^{2} + d(Q_{i}^{t}, P)^{2},
d(Q_{j}, P)^{2} = d(Q_{j}, Q_{j}^{t})^{2} + d(Q_{j}^{t}, P)^{2},

so by subtracting,

ψ_{ij}(P) = ψ_{ij}^{t}(P) + d(Q_{i}, Q_{i}^{t})^{2} − d(Q_{j}, Q_{j}^{t})^{2},

where ψ_{ij}^{t} denotes the Pythagorean coordinate along Q_{i}^{t}Q_{j}^{t}. This expression, together with the fact that ψ_{ij}(P) = φ(e; i, j), shows that the correct gain for e in the Pythagorean gain graph Ψ(ℋ^{t}) is φ^{η_{t}}(e; i, j).

The calculation also proves the lemma, since h(e) ⊉ t and h(e) ∩ t ≠ ∅ if and only if t contains points that take different values of the Pythagorean coordinate ψ_{ij}, hence of ψ_{ij}^{t}; but such points exist with respect to ψ_{ij}^{t} if and only if Q_{i}^{t} ≠ Q_{j}^{t}.

The coalescence of reference points under projection shows that each block of π(t) must be identified to a vertex in Ψ(ℋ^{t}) but there should be no other identifications of reference points. The lemma shows us which edges of Φ no longer correspond to hyperplanes in ℋ^{t} so should be deleted. Thus Ψ(ℋ^{t}) is precisely the gain graph Φ^{η_{t}}/π(t).

The assertion about generic t follows because a flat s ∈ ℒ(ℋ) intersects t in the smallest dimension permitted by the modular law: in dimension dim s−codim t if that is nonnegative; otherwise the intersection is empty.

Suppose Q̄_{1}, …, Q̄_{k} fail to have ideal general position. Then they have a parallelism: flats f̄ and ḡ, generated by Q̄_{i}’s, neither one a point, such that t_{(∞)} ⊇ f̄_{ℙ} ∩ ḡ_{ℙ} ≠ ∅. Let t′ be an orthogonal complement of t: a flat such that t′ ⊥ t, t ∩ t′ is a point, and dim t + dim t′ = d. We can regard 𝔼^{d} as t × t′. Let f̂ = f̄× t′ and ĝ = ḡ× t′. Since f̄∩ ḡ = ∅, f̂∩ ĝ = ∅ as well.

Now let f = aff{Q_{i} : Q_{i} ∈ f̂} and let g be similar. Neither f nor g is a point. They are disjoint because f̂∩ ĝ = ∅, but they meet at infinity because f_{ℙ} ∩ g_{ℙ} ⊇ f̄_{ℙ} ∩ ḡ_{ℙ}. Therefore there is a parallelism within Q_{1}, …, Q_{n}.

It follows that ideal general position of Q_{1}, …, Q_{n} implies ideal general position of Q̄_{1}, …, Q̄_{k}. □

We are especially interested in what happens when we look inside a flat of the arrangement itself. If s is a flat of ℋ, we write ℋ(s) = {h ∈ ℋ : h ⊇ s} and E(s) = {e ∈ E(Φ) : h(e) ⊇ s}. E(s) is necessarily balanced, by Lemma 5.4. Theorem 7.3. Take a fixed real, additive gain graph Φ of order n and points Q_{1}, …, Q_{n} ∈ 𝔼^{d} in general position with respect to Φ. Let ℋ = ℋ(Φ; Q_{1}, …, Q_{n}). For s ∈ ℒ(ℋ) which is not a point, let Q̄_{1}, …, Q̄_{k} be the distinct points proj_{s} Q_{i}, where k = c(E(s)). Then

ℋ^{s} = ℋ(Φ^{η_{s}}/E(s); Q̄_{1}, …, Q̄_{k}).

and Q̄_{1}, …, Q̄_{k} have general position in s with respect to Φ^{η_{s}}/E(s).

Furthermore, if Q_{1}, …, Q_{n} have ideal general position, then Q̄_{1}, …, Q̄_{k} also have it.

Proof. Write S = E(s). We know that π(s) = π(S), hence k = c(S), due to Corollary 6.12. The bulk of the theorem follows from Theorem 7.1. What remains to prove is that Q̄_{1}, …, Q̄_{k} have general position.

By general position of Q_{1}, …, Q_{n} with respect to Φ, ℒ(ℋ) ≅ [Lat^{b} Φ]_{0}^{d}. Switching does not change Lat^{b} Φ. Thus ℒ(ℋ) ≅ [Lat^{b} Φ^{η_{s}}]_{0}^{d}. We also know that ℒ(ℋ^{s}) ≅ ℒ(ℋ)/s = {t ∈ ℒ(ℋ) : t ≥ s}; and this is isomorphic to [Lat^{b} Φ]_{0}^{d}/E(s) by the isomorphism of ℒ(ℋ) with Lat^{b} Φ. One further fact is needed: Lat^{b}(Φ^{η_{s}}/S) ≅ (Lat^{b} Φ^{η_{s}})/S for a balanced edge set S [30, Prop. II.2.7]. Tracing through these isomorphisms, we conclude that ℒ(ℋ^{s}) ≅ [Lat^{b}(Φ^{η_{s}}/E(s))]_{0}^{dim s}. This is the definition of general position of Q̄_{1}, …, Q̄_{k}. □

We can now analyse the oversight in Good and Tideman’s Theorem 2 [17]. It asserts (in our terminology) that, if (K_{n}, 0) is the complete graph with all-zero gain function φ and ℋ = ℋ((K_{n}, 0); Q), then generically ℋ^{s} has the form ℋ((K_{n−q+1}, 0); Q^{s}) for some set of reference points Q_{1}^{s}, …, Q_{n−q+1}^{s} ∈ s if s ∈ ℒ(ℋ) is such that E(s) consists of just one nonisolated component that has q vertices (thus dim s = d − q + 1). This kind of flat is what Good and Tideman call a “circumflat”. By Theorem 7.3 we know that ℒ(ℋ^{s}) ≅ [Lat^{b}(K_{n}, 0)^{η}/E(s)]_{0}^{dim s} where η(i) = d(Q_{i}, s)^{2}; that is, ℒ(ℋ^{s}) is an arrangement of perpendiculars with respect to reference points in s and some gain graph. What we do not know is that reference points exist within s with respect to which the gain graph can be chosen to have all-zero gains (that is, the hyperplanes are to be perpendicular bisectors); and in fact they may not exist, as Example 7.1 shows. But (K_{n}, 0)^{η}/E(s) is balanced (in fact, ℋ^{s} is a power-diagram arrangement with centers bQ and spheres of radii d(Q_{i}, s)) and, by Corollary 11.1, generically the face and flat numbers of ℋ(Φ; Q) for balanced and complete Φ Figure 7.1. A counterexample to the Good–Tideman proof. The points P_{ij} are not centrally symmetric.

are the same as for perpendicular bisectors. So Good and Tideman’s numerical conclusions are correct after all and are valid, moreover, for every flat of ℋ. Example 7.1. In Figure 7.1 are a planar arrangement of bisectors and a circumflat whose induced arrangement cannot be constructed as bisectors from reference points within the circumflat.

**********************************************************

Place FIGURE 7.1 near EXAMPLE 7.1. **********************************************************

First, observe that, if six points in a line are the bisectors of the six segments produced by four reference points in the line, then the bisection points are centrally symmetric.

To construct the example, take generic points Q_{1}, …, Q_{5} in the plane. Let l_{ij} be the perpendicular bisector of [Q_{i}, Q_{j}] and for the circumflat take s = l_{45}. The induced arrangement ℋ^{s} consists of one point P_{ij} for each l_{ij} with i < j ≤ 4; we may ignore l_{i5} since it and l_{i4} meet s in the same point. Thus we have an arrangement of 6 points in s produced by 6 lines l_{ij} that are the perpendicular bisectors of all the segments generated by Q_{1}, …, Q_{4}. In relation to these bisectors, s is an arbitrary line because we can determine it at will by choosing Q_{5}. It is easy to find s so that the 6 points in s are not centrally symmetric; in fact, that situation is generic. Therefore, ℋ^{s} cannot be produced by reference points in s.

7.3. Cross-sectional representation. Is every Pythagorean arrangement a cross-section of one in which the reference points are an affine basis? Yes! Theorem 7.4. Given Φ of order n, d < n − 1, and Q_{1}, …, Q_{n} that affinely span 𝔼^{d}, it is possible to find affinely independent reference points Q′_{1}, …, Q′_{n} ∈ 𝔼^{n−1} such that ℋ(Φ; Q) = ℋ(Φ; Q′)^{t} for some d-flat t in 𝔼^{n−1}.

Proof. Embed 𝔼^{d} as a flat t ⊆ 𝔼^{n−1} and choose Q′_{i} that are all at some fixed positive distance c from the corresponding points Q_{i} but in generically different directions orthogonal to t. Obviously the Q′_{i} will be affinely independent. (If d = n − 2, there are only two directions orthogonal to t so special instructions are necessary. The reference points have only one minimal dependent set, say Q_{1}, …, Q_{k}. If Q_{1}, …, Q_{k} are not all shifted in the same direction, then Q′_{1}, …, Q′_{n} will be affinely independent.) Now Q_{i} = proj_{t} Q′_{i} and therefore ℋ(Φ; Q′)^{t} = ℋ(Φ^{η}; Q), where η(i) = d(Q′_{i}, Q_{i}) = c, by Theorem 7.1. Thus Φ^{η} = Φ. □

Conversely, let us begin with affinely independent reference points in dimension n − 1. Then ℒ(ℋ(Φ; Q)) ≅ Lat^{b} Φ by Theorem 5.1 and Proposition 6.5. If t is a generic affine flat of dimension d, then ℒ(ℋ(Φ; Q)^{t}) ≅ [Lat^{b} Φ]_{0}^{d} by Theorem 7.1. This viewpoint gives another explanation of the generic fact that ℋ(Φ; Q) in lower dimensions has intersection semilattice [Lat^{b} Φ]_{0}^{d}, as Good and Tideman observed for the arrangement of all perpendicular bisectors. Possibly it could be the basis for an alternative proof of Theorem 5.1.

8. Non-Pythagorean perpendiculars

Now let us consider modified Pythagorean description rules, (α, Φ) where α ≠ 0. Recall that the arrangement ℋ(α, Φ; Q), described by (α, Φ) and based on Q, has for each edge e (with endpoints i and j) a hyperplane h(e) perpendicular to Q_{i}Q_{j} with Pythagorean coordinate

ψ_{ij}(h(e)) = φ(e; i, j)d(Q_{i}, Q_{j})^{α}.

Let Z be the set of edges with gain φ(e) = 0. Theorem 8.1. Let n > d ≥ 1. Choose a real number α ≠ 0 and a real, additive gain graph Φ on vertices {1, 2, …, n}. Supposing Q = (Q_{1}, …, Q_{n}) is generic, then the intersection of a subset 𝒮 ⊆ ℋ(α, Φ; Q) is void except that, when 𝒮 corresponds to an edge set S having n − i connected components with i ≤ d and in which every circle is contained in Z (that is, the parts of 𝒮 corresponding to circles in Φ consist of bisectors), then the intersection is a flat of dimension d − i.

Two subsets 𝒮_{1} and 𝒮_{2} with nonempty intersections have the same intersection if and only if S_{1} \ Z = S_{2} \ Z and the connected components of S_{1} ∩ Z and S_{2} ∩ Z partition the vertices in the same way.

Proof. Let Ψ be the Pythagorean gain graph of ℋ(α, Φ; Q); that is,

(8.1)  ψ(e; i, j) = φ(e; i, j)d(Q_{i}, Q_{j})^{α}.

Choosing any Q, by varying Q slightly we can ensure that Q has ideal general position and the gains in Ψ do not sum to zero on any circle except one whose edges all have gain zero. (A more abstract way to obtain the same effect is to replace the nonzero gains in Φ by new real gain values that are linearly independent over the rationals.) We may now apply Theorem 5.1 to ℋ(Ψ; Q). This gives the first half of the theorem immediately.

For the second half we see from Theorem 5.1 that S_{1} ∪ S_{2} must be balanced in Ψ and, if the components of S_{1} have vertex sets V_{1}, …, V_{k}, then so do those of S_{2}. We examine one V_{i}. Let S_{1i} and S_{2i} be the parts of S_{1} and S_{2} with endpoints in V_{i}.

Suppose S_{1i} ∩ Z partitions V_{i} into B_{1}, …, B_{l} with l > 1. If S_{2i} ∩ Z contains an edge e that joins two of the B_{j}’s, say B_{1} and B_{2}, then S_{1i} ∪ {e} contains a circle C ∋ e. C ⊈ Z since e lies in no circle in (S_{1i} ∩ Z) ∪ {e}. Therefore S_{1} ∪ S_{2} contains a circle C that is unbalanced in Ψ. This is impossible. Hence S_{2i} ∩ Z does not join any of the B_{j}’s. It follows that S_{1i} ∩ Z and S_{2i} ∩ Z partition V_{i} in the same way; as this is true for every i, S_{1} ∩ Z and S_{2} ∩ Z partition V in the same way.

Meanwhile, if S_{2i} \ Z contains an edge f ∉ S_{1i} \ Z, then S_{1i} ∪ {f} contains a circle C ∋ f. But C is then unbalanced, which contradicts balance of S_{1} ∪ S_{2}. Therefore S_{2i} \ Z ⊆ S_{1i}. It follows that S_{1i} \ Z = S_{2i} \ Z. □

Comparing with the definition of the complete lift matroid L_{0}(Γ, ℬ) of a biased graph ([30, §II.3]; see the gain-graphic version in our Section 6.1) and its balanced flats, we have a matroid-theoretic restatement of Theorem 8.1.

Corollary 8.2. Let Φ be a real, additive gain graph on n vertices, α a nonzero real number, and n > d ≥ 1. Let Γ be the underlying graph of Φ, let Z = {e ∈ E : φ(e) = 0}, and let 𝒵 be the set of circles in Z. Then for generic Q = (Q_{1}, …, Q_{n}) in 𝔼^{d}, ℒ(ℋ(α, Φ; Q)) ≅ [ Lat^{b}(Γ, 𝒵)]_{0}^{d} and ℒ(ℋ_{ℙ}(α, Φ; Q)) ≅ T_{d+1}(Lat L_{0}(Γ, 𝒵)), with flats of ℋ_{ℙ} in h_{∞} corresponding to matroid flats containing the extra point e_{0}. □

Example 8.1. In Example 4.2, 𝒵 consists of the one circle e_{12}(0)e_{23}(0)e_{13}(0).

Corollary 8.2 leads to the question of describing the edge sets S ∈ Lat^{b} Ψ. From the proof of Theorem 8.1, S is balanced ⟺ every circle in it is contained in Z.

Proposition 8.3. Let S ⊆ E(Ψ). S ∈ Lat^{b} Ψ ⟺ S is balanced and e ∈ S whenever e is an edge in Z whose endpoints are connected by S ∩ Z ⟺ S is balanced and S ∩ Z is closed in the graphic matroid of (V, Z).

Proof. Just interpret the definitions of balance and balance-closure in [30, §§I.5, I.3, resp.]. □

We should like a similar description of the flats of the induced arrangement ℋ(α, Φ; Q)^{s}. We get it by applying Theorem 7.3 to Ψ. The Pythagorean gain graph of ℋ^{s} is Ψ^{s} = Ψ^{η}/E(s) where η(i) = −d(Q_{i}, s)^{2}. We wish to determine the edges sets A of Ψ^{s} that belong to Lat^{b} Ψ^{s}, hence correspond to flats of a generic ℋ^{s} (provided that A has the right rank, for which it is necessary and sufficient that c_{Ψ^{s}}(A) ≥ n − d). To state a relatively nice result, we have to think of A in two ways at once: as an edge set in Ψ^{s} and also as one in Ψ (which it is, since E(Ψ^{s}) ⊆ E(Ψ)). An S-subcomponent is a component of (V, Z ∩ S).

Proposition 8.4. Let A ⊆ E(Ψ^{s}). A ∈ Lat^{b} Ψ^{s} ⟺ A satisfies the two conditions (a) every circle in A (as an edge set in Ψ^{s}) lies in Z ∩ A, and

(b) for each component A_{1} of A (in Ψ^{s}), A_{1} touches (in Ψ) at most one E(s)-subcomponent in each component of (V, E(s)) and, if A_{1} touches two E(s)-subcomponents that are joined by an edge e ∈ Z \ E(s), then e ∈ A.

The point of Proposition 8.4 is to show that Lat^{b} Ψ^{s} can be described but not so easily as Lat^{b} Ψ. The proof, which is not hard, is very technical and ungeometrical and really belongs to the theory of fat forests [31, Ch. IV]. Thus we omit it.

9. A projectionist’s view.

A quite different geometrical construction for the Pythagorean arrangement of a balanced gain graph was suggested to me by Herbert Edelsbrunner in 1984, based on a parabolic approach to Voronoi diagrams (see Edelsbrunner and Seidel [13, end of Note 3.1] for the plane, or the general treatment in [3, Section 4.1] or [12, Section 13.1, p. 296]).

Embed 𝔼^{d} with coordinate vectors x = (x_{1}, …, x_{d}) in 𝔼^{d+1} whose (d + 1)-st coordinate is z. The fundamental paraboloid is the hypersurface S: z = x_{1}^{2} + ⋯ + x_{d}^{2}. For P ∈ 𝔼^{d}, let P^{∗} be its vertical projection up into S; for Q^{∗} ∈ S, let Q be its projection down to 𝔼^{d}. Let T_{Q^{∗}} be the tangent d-space to S at Q^{∗} ∈ S. If Q_{i}, Q_{j} ∈ 𝔼^{d}, then h_{ij}, the vertical projection into 𝔼^{d} of the intersection T_{Q_{i}^{∗}} ∩ T_{Q_{j}^{∗}}, is the perpendicular bisector of the line segment between Q_{i} and Q_{j}. Thus the Good–Tideman arrangement can be constructed by

(1) lifting each Q_{i} to Q_{i}^{∗} ∈ S,

(2) forming the \binom{n}{2} tangent space intersections, and

(3) projecting them back to 𝔼^{d}. Edelsbrunner suggested a similar procedure with step (2) replaced by

(2′) raise each tangent space T_{Q_{i}^{∗}} by an arbitrary amount η(i) ∈ ℝ to a ‘displaced tangent’ T_{i}, parallel to T_{Q_{i}^{∗}} but at height z increased by η(i), and form the intersections of the displaced tangents.

Lemma 9.1. This procedure forms a Pythagorean arrangement in 𝔼^{d}, based on Q_{1}, Q_{2}, …, Q_{n}, with complete, balanced Pythagorean gain graph Ψ = (K_{n}, 0)^{η}.

Proof. Let Q_{i} have coordinate vector a_{i} = (a_{i1}, …, a_{id}) and P have coordinate vector x in 𝔼^{d}. The tangent space at Q_{i}^{∗}, revised by η(i) to T_{i}, has equation z = 2a_{i} · x − c_{i} + η(i), where c_{i} = a_{i} · a_{i}, the z-coordinate of Q_{i}^{∗}. Eliminating z, T_{i} ∩ T_{j} satisfies the equation

−2(a_{j} − a_{i}) · x + c_{j} − c_{i} = η(j) − η(i),

which (with z = 0) defines h_{ij}, the projection into 𝔼^{d}.

Let us calculate the Pythogorean coordinate of a point P ∈ 𝔼^{d}. It is ψ_{ij}(P) = ∥x − a_{j}∥^{2} − ∥x−a_{i}∥^{2} = 2(a_{i}−a_{j})·x+c_{j} −c_{i}. Thus the equation of h_{ij} can be written ψ_{ij}(P) = η(j)−η(i). Since the right side is a constant, h_{ij} is a hyperplane perpendicular to Q_{i}Q_{j}. The form of the constant demonstrates that Ψ = (K_{n}, 0)^{η}. □

We note that Lemma 9.1 is a trivial generalization of [3, Lemma 4]. Proposition 9.2. (a) Let T_{1}, T_{2}, …, T_{n} be arbitrary nonvertical affine d-spaces in 𝔼^{d+1}, no two parallel, and let h_{ij} be the projection into 𝔼^{d} of T_{i} ∩ T_{j}. Then {h_{ij}} is a Pythagorean arrangement described by a balanced, complete gain graph Ψ, based on those points Q_{1}, Q_{2}, …, Q_{n} such that Q_{i}^{∗} is the unique point where a translate of T_{i} is tangent to S.

(b) Conversely let Φ be a balanced, complete gain graph on n vertices and let Q_{1}, Q_{2}, …, Q_{n} be distinct points in 𝔼^{d}. Then there exist affine d-spaces T_{1}, T_{2}, …, T_{n} in 𝔼^{d+1} such that the Pythagorean arrangement ℋ(Φ; Q_{1}, …, Q_{n}) equals the arrangement {h_{ij}} derived from T_{1}, T_{2}, …, T_{n} by the procedure in (a).

Proof. (a) Suppose T_{i} has to be lowered vertically a distance η(i) to become tangent to S. Then {h_{ij}} is as defined before Lemma 9.1 and Ψ is as in Lemma 9.1.

(b) Since Ψ is balanced and connected, there exist numbers η(1), η(2), …, η(n), unique up to an additive constant, so that ψ(e; i, j) = η(j)−η(i). (This is a well-known characterization of tensions on a graph in terms of potentials. See, e.g., [4] or [5, §2.3, Thm. 5].) Thus Ψ = (K_{n}, 0)^{η}. The d-space T_{i} is the result of raising T_{Q_{i}^{∗}} the distance η(i). □

10. Invariants and face enumeration

There is a class of invariants of hyperplane arrangements that are determined by the geometric semilattice: they include the Whitney numbers and the characteristic polynomial. These invariants of a Pythagorean arrangement ℋ(Φ; Q) in 𝔼^{d} with generic reference points are readily derivable from corresponding invariants of Φ, because by Corollary 6.1 Lat ℋ(Φ; Q) ≅ [Lat^{b} Φ]_{0}^{d}. Similarly, if α ≠ 0, one can deduce the invariants of a generic non-Pythagorean arrangement ℋ(α, Φ; Q) from the fact that Lat ℋ(α, Φ; Q) ≅ [Lat^{b} Ψ]_{0}^{d}, where Ψ is as in Section 8.

Throughout this section, Φ is a real, additive gain graph with n vertices and Q = (Q_{1}, …, Q_{n}) ∈ (𝔼^{d})^{n}.

Reasonably obvious is this basic observation: Theorem 10.1. Given Φ, d, and α (zero or not), the numbers of k-dimensional flats, faces, and bounded faces of ℋ(α, Φ; Q) are maximized for generic Q; specifically, when Q has general position with respect to Φ. □

The fundamental enumerative result about arrangements of perpendiculars is Theorem 10.2. Given Φ, d, and α (zero or not). Generically, the numbers of k-dimensional flats, faces, and bounded faces of ℋ = ℋ(α, Φ; Q) are given by the formulas

f_{k}(ℋ) = ∑_{j=d−k}^{d}|w_{d−k,j}(Lat^{b} Ψ)|,

b_{k}(ℋ) = | ∑_{j=d−k}^{d}w_{d−k,j}(Lat^{b} Ψ)|,
a_{k}(ℋ) = W_{d−k}(Lat^{b} Ψ)

for 0 ≤ k ≤ d, where Ψ is the Pythagorean gain graph of ℋ, defined by (8.1). The numbers of flats and faces of ℋ_{ℙ} if 0 ≤ k ≤ d < n are given by

f_{k}(ℋ_{ℙ}) = | ∑_{\begin{matrix}j=d−k \\ d−j even \end{matrix}}^{d} w_{d−k,j}(Lat L_{0}(Ψ))|,

a_{k}(ℋ_{ℙ}) = W_{d−k}(Lat L_{0}(Ψ)).

Proof. This is merely a combination of the general arrangement enumerations in Section 2 with the particular description of generic ℒ(ℋ) in Section 6.1. □

In order to state these results about ℋ most elegantly we need to define some polynomials. The characteristic polynomial of an affine arrangement ℰ in 𝔼^{d} is

p_{ℰ}(λ) = ∑_{j=0}^{d} w_{j}(ℰ)λ^{d−j}.

The Whitney-number polynomial is

w_{ℰ}(x, λ) = ∑ ∑_{0≤i≤j≤d}w_{ij}(ℰ)x^{i}λ^{d−j}.

(In these formulas we define w_{j} = w_{ij} = 0 if j > rk ℰ.) Thus (2.1) and (2.3) can be expressed by the formulas

f_{d}(ℰ) = (−1)^{d}p_{ℰ}(−1) and ∑_{k} f_{k}(ℰ)x^{k} = (−1)^{d}w_{ℰ}(−x, −1),

while

b_{d}(ℰ) = (−1)^{d}p_{ℰ}(1) and ∑_{k} b_{k}(ℰ)x^{k} = (−1)^{d}w_{ℰ}(−x, 1).

Turning to a gain graph Φ of order n, we may define its balanced chromatic polynomial as

χ_{Φ}^{b}(λ) = ∑_{j=0}^{n} w_{j}(Lat^{b} Φ)λ^{n−j}

and its balanced Whitney-number polynomial as

w_{Φ}^{b}(x, λ) = ∑ ∑_{0≤i≤j≤n}w_{ij}(Lat^{b} Φ)x^{i}λ^{n−j}.

(Again, w_{j} = w_{ij} = 0 if j > rk(Lat^{b} Φ).) If Φ has c connected components (thus Lat^{b} Φ has rank n − c), the characteristic and Whitney-number polynomials of Lat^{b} Φ are

p_{Lat^{b} Φ}(λ) = λ^{−c}χ_{Φ}^{b}(λ) and w_{Lat^{b} Φ}(x, λ) = λ^{−c}w_{Φ}^{b}(x, λ).

Theorem 10.3. Let ℋ = ℋ(Φ; Q) have generic reference points in 𝔼^{d}, where d ≤ n. Then p_{ℋ} (λ) and w_{ℋ} (λ) equal the polynomial parts of χ_{Φ}^{b}(λ)/λ^{n−d} and w_{Φ}^{b}(x, λ)/λ^{n−d}, respectively.

Proof. This is the conclusion of the preceding discussion. □

Theorems 10.2 and 10.3 reduce the problem of counting regions or faces in ℋ to that of finding the balanced chromatic or Whitney-number polynomial of Φ. This approach will be illustrated in Section 11.

For non-Pythagorean descriptors there is a similar result. Theorem 10.4. With notation as in Corollary 8.2, let ℋ = ℋ(α, Φ; Q) with generic Q ∈ (𝔼^{d})^{n}. Then p_{ℋ} (λ) and w_{ℋ} (x, λ) are the polynomial parts of χ_{Ψ}^{b}(λ)/λ^{n−d} and w_{Ψ}^{b}(x, λ)/λ^{n−d}, respectively. □ Example 10.1. For the affinographic arrangements of Example 3.2, Lat ℋ(Φ; Q) ≅ Lat^{b} Φ. (The reference points are generic by Proposition 6.2.) Thus Theorem 10.3 applies with d = n.

The Pythagorean planar case has a nice description in terms of the structure of Φ. Let m_{ij} be the number of edges between i and j in Φ, q the total number of edges, and s_{2} the second elementary symmetric function of the m_{ij}. Let t be the number of balanced triangles in Φ and let t_{0} be the number of triangles in the zero-gain edge set.

Corollary 10.5. If Q_{1}, …, Q_{n} are generic in 𝔼^{2}, then the Pythagorean arrangement of lines ℋ(Φ; Q_{1}, …, Q_{n}) has

a_{2} = q  lines,
a_{1} = s_{2}  points,
f_{2} = 1 + q + s_{2} − t regions,
f_{1} = q + 2s_{2} − 3t geometric edges (1-faces),
b_{2} = 1 + s_{2} − q − t bounded regions,
b_{1} = 2s_{2} − q − 3t bounded geometric edges.

Corollary 10.6. Let α be a nonzero real number. If Q_{1}, …, Q_{n} are generic in 𝔼^{2}, then the arrangement of perpendicular lines ℋ(α, Φ; Q_{1}, …, Q_{n}) has numbers as in Corollary 10.5 with t replaced by t_{0}.

Proof. Corollary 10.5 is obtained from Theorems 5.1 and 10.2 by way of Lemma 10.7. Corollary 10.6 follows similarly from Theorems 8.1 and 10.2. □

Examples 11.1, 11.3, and 11.4 illustrate these corollaries.

Lemma 10.7. Suppose a finite gain graph Φ has q edges, all of them links (two distinct endpoints), and t balanced triangles and s_{2} is the second elementary symmetric function of the edge multiplicities. Then in Lat^{b} Φ the first few Whitney numbers are

w_{0} = w_{00} = W_{0} = 1,  w_{1} = w_{01} = −q,  w_{2} = w_{02} = s_{2} − t,
w_{11} = W_{1} = q,  w_{22} = W_{2} = s_{2} − 2t,  w_{12} = 2s_{2} − 3t.

If t = 0 and there are F_{n−3} forests with three edges and t′ balanced quadrilaterals, then

w_{3} = w_{03} = −(F_{n−3} − t′),  w_{13} = F_{n−3} − 4t′,
w_{23} = −(F_{n−3} − 6t′),  W_{3} = w_{33} = F_{n−3} − 3t′.

Proof. The essential fact for w_{i2} is that there are two kinds of balanced flat of rank 2: a balanced triangle, and a pair of nonparallel edges not contained in a balanced triangle. There are t of the former type and s_{2} − 3t of the latter. A similar remark applies to the calculation of w_{i3}. □

11. Enumeration in examples

We now have the machinery to do Pythagorean arrangements of special kinds. Here we describe some abstractly; then in the next section we see how they may arise from various models of voter preference. Throughout, Φ is a real, additive gain graph with n vertices and Q = (Q_{1}, …, Q_{n}) ∈ (𝔼^{d})^{n}.

11.1. Perpendicular bisectors, power-diagram arrangements, and other balanced gain graphs. Suppose the arrangement ℋ consists of one perpendicular hyperplane for each line Q_{i}Q_{j}, positioned according to a balanced Pythagorean gain graph Φ. We obtain the theorem of Good and Tideman as well as generalizations to arrangements based on power diagrams (see Section 7.1) and to a voter with prior biases (as at the end of Section 12).

Corollary 11.1. Let Φ be a balanced, complete Pythagorean gain graph on n vertices. Let ℋ be the Pythagorean arrangement ℋ(Φ; Q). Generically, the numbers of k-dimensional flats, faces, and bounded faces of ℋ are, for regions,

f_{d}(ℋ) = ∑_{i=0}^{d}|s(n, n − i)|,  b_{d}(ℋ) = (−1)^{d}∑_{i=0}^{d}s(n, n − i),

and for the rest,

\begin{aligned}a_{k}(ℋ) & = S(n, n − d + k), \\ f_{k}(ℋ) & = S(n, n − d + k) ∑_{j=d−k}^{d}|s(n − d + k, n − j)|, \\ b_{k}(ℋ) & = (−1)^{k}S(n, n − d + k) ∑_{j=d−k}^{d}s(n − d + k, n − j). \end{aligned}

Proof. We combine Theorem 10.2 with standard facts about Π_{n}, the set of partitions of n elements ordered by refinement, in which rk π = n − |π|. Since every edge set in Φ is balanced, Lat^{b} Φ = Lat G(K_{n}) = Π_{n}. The Whitney numbers of the first and second kinds of Π_{n} are the Stirling numbers (see [14] or [24, §9] for the first kind, [23] for the second). The doubly indexed Whitney numbers are w_{ij}(Π_{n}) = S(n, n − i)s(n − i, n − j). □

The planar numbers result from substituting q = \binom{n}{2}, s_{2} = \binom{q}{2} = 3\binom{n+1}{4}, and t = \binom{n}{3} in Corollary 10.5.

If Φ is balanced but incomplete, the conclusion is more complicated. A partial result is easiest to state. It can be understood as an application of Theorem 10.3. Corollary 11.2. Let Φ be a balanced Pythagorean gain graph on n vertices and let χ_{Γ}(λ) be the chromatic polynomial of the underlying graph Γ. Generically, p_{ℋ(Φ;Q)} (λ) is the polynomial part of χ(λ)/λ^{n−d}. The generic numbers of regions and bounded regions of ℋ(Φ; Q) are

f_{d} = the sum of magnitudes of the d + 1 leading coefficients of χ_{Γ}(λ), and b_{d} = the magnitude of the sum of the d + 1 leading coefficients.

Proof. Rota [24, §9] proved that χ_{Γ}(λ) = ∑ w_{i}(Lat Γ) λ^{n−i}. We know Lat Γ = Lat^{b} Φ from balance of Φ. □

In the planar case we may again resort to Corollary 10.5, as when Φ was complete: still s_{2} = \binom{q}{2}, but now q and t depend on Φ. Example 11.1. In Figure 11.1 we see a balanced gain graph and a corresponding generic Pythagorean arrangement of lines. Since Φ is balanced, χ_{Φ}(λ) = χ_{Γ}(λ) = λ(λ − 1)(λ − 2)^{2}, Γ being the underlying graph of Φ. By Theorem 10.3 therefore p_{ℋ} (λ) is the polynomial part of λ^{−2}(λ^{4} − 5λ^{3} + 8λ^{2} − 4λ), so that p_{ℋ} (λ) = λ^{2} − 5λ + 8. It follows that the number of regions is |p_{ℋ} (−1)| = 14 and the number of bounded regions is |p_{ℋ} (1)| = 4, in agreement with the diagram.

**********************************************************

Place FIGURE 11.1 near EXAMPLE 11.1. ********************************************************** Figure 11.1. A balanced gain graph and a corresponding generic line arrangement. (Example 11.1.)

11.2. Generic hyperplanes and non-Pythagorean rules. (Forests.) Suppose Φ is a Pythagorean gain graph in which no circle is balanced, as would (almost surely) happen if the gains were chosen at random, or suppose (α, Φ) is a non-Pythagorean descriptor (i.e., α ≠ 0) in which the zero-gain edges of Φ contain no circle. These two structures have the same formulas. In either case there are no balanced circles in the appropriate biased graph, so the balanced flats of the lift are precisely the spanning forests of the underlying graph Γ. Let F_{l}(Γ) denote the number of spanning forests with l components.

Corollary 11.3. Let Φ be a Pythagorean gain graph without balanced circles and let α = 0, or let (α, Φ) be a non-Pythagorean descriptor without zero-gain circles. Let Γ be the underlying graph. Generically, p_{ℋ(α,Φ;Q)} (λ) = ∑_{i=0}^{d}(−1)^{i}F_{n−i}(Γ)λ^{d−i}. The numbers of flats and faces of ℋ(α, Φ; Q) when Q is generic are

f_{d} = ∑_{i=0}^{d}F_{n−i}(Γ),  b_{d} = ∑_{i=0}^{d}(−1)^{d−i}F_{n−i}(Γ),

a_{k} = F_{n−d+k}(Γ),  f_{k} = ∑_{i=d−k}^{d}\binom{i}{d − k}F_{n−i}(Γ),

b_{k} = ∑_{i=d−k}^{d}(−1)^{d−i}\binom{i}{d − k}F_{n−i}(Γ)  (except when k = d − n + c(Φ) > 0).

Outline of proof. The Pythagorean gain graph Ψ of ℋ (which equals Φ if α = 0) is contrabalanced (see [30, Ex. III.3.4]) so χ_{Ψ}^{b}(λ) = ∑(−1)^{i}F_{n−i}(Γ)λ^{d−i}. Apply Theorem 10.4 to get p_{ℋ} (λ).

The fact lying behind the counts, that the doubly indexed Whitney numbers of Lat^{b} Ψ are binomial multiples of the forest numbers of Γ, is implicit in [29, Thm. 7] and explicit in [30, Ex. III.5.4]. This fact was recently rediscovered in [21, §5] in the language of what in [30, §IV.4] we would call the canonical affine hyperplanar lift representation of Ψ. □

The first three forest numbers are simple. If Φ has q edges, then F_{n}(Γ) = 1, F_{n−1}(Γ) = q, F_{n−2}(Γ) = \binom{q}{2}. One can now write down explicit formulas for a_{k}, f_{k}, and b_{k} in dimensions d = 1 and 2. In 𝔼^{2}, f_{2} = 1 + \binom{q+1}{2}, f_{1} = q^{2}, b_{0} = f_{0} = \binom{q}{2}, b_{2} = \binom{q−1}{2}, b_{1} = q^{2} − 2q. (We may obtain these formulas also from Corollary 10.6 with t = t_{0} = 0.) Example 11.2. Equally many perpendiculars to each line. Take Γ = mK_{n}, a complete graph with m edges between each pair of vertices. Then

F_{n−i}(mK_{n}) = \frac{m^{i}}{(n − i)!}∑_{k=0}^{n−i}(−\frac{1}{2})^{k}\binom{n − i}{k}\binom{n − 1}{i − k}(n − i + k)!n^{i−k}

by Rényi’s formula for F_{n−i}(K_{n}) [22]. Even without Rényi’s formula it is easy to see that

F_{n−1}(mK_{n}) = m\binom{n}{2}, F_{n−2}(mK_{n}) = 3m^{2}\binom{n+1}{4}, F_{n−3}(mK_{n}) = m^{3}\binom{n}{3} \frac{n^{2} − 5n − 12}{8}.

Example 11.3. The solid lines in Figure 11.3 show a gain graph, Φ, without balanced circles and a generic Pythagorean arrangement of lines, ℋ(Φ; Q). Since each two vertices are doubly adjacent, we are in the situation of Example 11.2 with m = 2. The characteristic polynomial is p_{ℋ} (λ) = λ^{2} − 6λ + 12; there are 19 regions, of whcih 7 are bounded.

**********************************************************

Place FIGURE 11.3 near EXAMPLE 11.3. **********************************************************

11.3. Generic hyperplanes and non-Pythagorean rules, with all bisectors and with equally many perpendiculars to each line. (Fat forests.) As in Section 11.2 this is two kinds of example in one treatment. Here Φ has a complete balanced part as in Section 11.1 and a totally unbalanced part as in Section 11.2. Assume that each pair of vertices is joined by M + 1 edges. If Φ is a Pythagorean gain graph, we assume that all balanced circles lie in a balanced, complete spanning subgraph; for instance, they may be the zero-gain edges. If Φ is part of a descriptor (α, Φ) with α ≠ 0, we assume that the set Z of zero-gain edges forms a complete spanning subgraph (V, Z). (Thus in either case, as a biased graph [30], Φ = ⟨K_{n}⟩ ∪ (MK_{n}, ∅), where ⟨K_{n}⟩ is a balanced K_{n} and (MK_{n}, ∅) is K_{n} with each edge replaced by M distinguishable copies of itself and with no balanced circles.)

The semilattice Lat^{b} Φ is isomorphic to the lower d ranks of the geometric semilattice of spanning fat forests of MK_{n}. A spanning fat forest (π, F) consists of a partition π of the vertex set together with an edge set F ⊆ E(MK_{n}) such that, if each block of π is collapsed to a point, F contains no circle. The geometric lattice of fat forests of a graph and related lattices and semilattices will be studied in detail in the anticipated [31, Ch. IV].

Figure 11.2. Illustration of Examples 11.3 and 11.4. The solid edges and lines show generic gains and a corresponding generic Pythagorean line arrangent (Example 11.3.) With the dashed lines we have also all 0-gain edges and, correspondingly, all perpendicular bisectors (Example 11.4).

We mention three results from [31, Ch. IV]. First, the top Whitney number of Lat^{b} Φ is

w_{n−1} = (−1)^{n−1} \frac{(n − 1)!}{nM} ∑_{μ⊢n} \frac{(nM)^{μ_{1}+μ_{2}+···}}{μ_{1}!μ_{2}! ⋯};

here μ ⊢ n means that μ = (μ_{1}, μ_{2}, …) with all μ_{i} ≥ 0 and ∑ jμ_{j} = n. The other Whitney numbers are given by

w_{n−i} = (−1)^{n−i} n! ∑_{\begin{matrix}λ⊢n \\ ∑ λ_{k}=i \end{matrix}} ∏_{k=1}^{∞} \frac{1}{λ_{k}!} [−\frac{1}{k^{2}M} ∑_{μ⊢k} \frac{(kM)^{μ_{1}+μ_{2}+···}}{μ_{1}!μ_{2}! ⋯} ]^{λ_{k}} .

These formulas are not among the easiest but they do permit computation of the generic numbers of regions and bounded regions in the hyperplane arrangements ℋ of this example. Second, if χ_{n,M}^{b}(λ) denotes the balanced chromatic polynomial of Φ, then {χ_{n,M}^{b}(λ)}_{n=1}^{∞} has exponential generating function

−1 + exp (−\frac{λ}{M} ∑_{k=1}^{∞} \frac{(−z)^{k}}{k^{2}} ∑_{μ⊢k} \frac{(kM)^{μ_{1}+μ_{2}+···}}{μ_{1}!μ_{2}! ⋯} ) .

From this the region and bounded region numbers can, in principle, be obtained by the formulas of Section 10. Third, the number W_{n−i} of spanning fat forests in MK_{n} with i connected components (recall that W_{k} = a_{d−k}, the number of flats in ℋ of codimension k) is given by the same formula as for w_{n−i} except with the signs omitted and an extra factor of 1!^{μ_{2}}2!^{μ_{3}} ⋯ in the denominator of the inmost sum. For instance, the number of spanning fat trees is

W_{n−1} = \frac{n!}{n^{2}M} ∑_{μ⊢n} ∏_{j=1}^{∞} \frac{(nM)^{μ_{j}}}{μ_{j}!(j − 1)!^{μ_{j}}} .

We get much simpler evaluations in the planar case by applying Corollaries 10.5 and 10.6, in which q = (M + 1)\binom{n}{2}, s_{2} = 3(M + 1)^{2}\binom{n+1}{4}, and t = t_{0} = \binom{n}{3}. Example 11.4. The solid and dashed lines in Figure 11.3 show a gain graph and generic Pythagorean arrangement of lines of the kind in Section 11.3. The balanced circles lie in the set Z of edges with gain 0. Since q = 9, s_{2} = 27, and t = 1, Corollary 10.5 says there are 36 regions of which 18 are bounded.

11.4. Symmetric, uniform Pythagorean hyperplanes: odd case. (Composed partitions.) For positive integers k and n, let Φ_{n} = [−k, k]K_{n} be the additive real gain graph on n vertices that has an edge of gain i between each pair of vertices for every i = 0, ±1, …, ±k. This gain graph, or any other obtained through multiplying all gains by a positive constant δ, gives the odd number 2k +1 of perpendiculars to each reference line, placed symmetrically about the bisector and equally spaced, and—in Pythagorean coordinates—identically spaced along all reference lines.

We can easily show that [−k, k]K_{n} has balanced chromatic polynomial

(11.1)  χ_{[−k,k]K_{n}}^{b}(λ) = λ(λ − nk − 1)_{n−1},

where (x)_{r} is the falling factorial x(x − 1) ⋯ (x − r + 1), whence C_{n}(k) = Lat^{b}[−k, k]K_{n} has characteristic polynomial

(11.2)  p_{C_{n}(k)}(λ) = (λ − nk − 1)_{n−1}.

Applying Theorem 10.3 to Equation (11.1), in 𝔼^{d} the number of regions, f_{d}, will equal the sum of the magnitudes of the coefficients of λ^{n}, …, λ^{n−d} in χ_{[−k,k]K_{n}}^{b}(λ). The number of bounded regions, b_{d}, will equal the magnitude of the sum of the same coefficients. Furthermore, by [30, Thm. III.5.2], the characteristic polynomial of the complete lift is

(11.3)  p_{Lat L_{0}([−k,k]K_{n})}(λ) = (λ − 1)(λ − nk − 1)_{n−1}.

To prove (11.2) we treat the gains modulo N, where N > nk, and employ gain graph coloring [30, §III.4]. Taking gains in ℤ_{n} does not change the balanced circles because the largest possible sum of gains around a circle is nk. A zero-free proper coloring of Φ is a function c : [n] → ℤ_{N} such that c(i) and c(j) differ by more than k whenever i ≠ j. ([n] is {1, 2, …, n}.) We obtain every such function by choosing its image, which can be done in \frac{N}{N−nk} \binom{N−nk}{n} ways by [9, Formula [9b]], and then choosing the coloring with that image in any of n! ways. Thus there are N(N − nk − 1)_{n−1} proper colorings. That is, with gain group ℤ_{N} we have balanced chromatic polynomial χ_{N}^{∗} for which χ_{N}^{∗}(N + 1) = N(N − nk − 1)_{n−1}. Since by [30, Thms. III.4.2 and III.5.3] the balanced chromatic polynomial depends only on which circles are balanced and it equals (up to a factor of λ) the characteristic polynomial of Lat^{b} Φ, we have Equation (11.2). (This proof is from [31, Ch. III]. Later others gave various proofs. Apparently the first published was that of Edelman and Reiner, whose proof is by an induction table for their arrangement 𝒜_{r,I}^{(l)} with I = [−l, l] [11, p. 321]; this arrangement (with their l, r = our k, n) is the canonical linear hyperplane representation of L_{0}([−k, k]K_{n}) [30, §IV.4], whose characteristic polynomial is given by (11.3). Athanasiadis’ proof in [2, Thm. 5.1] is essentially the same as ours.)

The geometric semilattice C_{n}(k) and related geometric lattices are very interesting objects. Here I will merely point out that an element of C_{n}(k) can be regarded as a kind of structured partition I call a weakly composed partition of [n] (more specifically, a k-composed partition; strictly composed if k = 1). To explain this we first define a k-composition of a set B: it is an ordered weak partition of B, that is, a sequence (S_{0}, S_{1}, S_{2}, …) of pairwise disjoint sets whose union is B, in which there is no consecutive subsequence of k empty sets except in the infinite terminal string of nulls; for normalization we also require S_{0} ≠ ∅ unless all S_{i} = ∅. If k = 1 this is just a (strict) composition of B, i.e., an ordered partition (S_{0}, S_{1}, …, S_{l}), with a terminal string of null sets attached for notational consistency. A k-composed partition of [n] is a partition of [n] together with a k-composition of each block. One can explicitly describe the refinement ordering, interval structure, and characteristic polynomial of C_{n}(k), Lat L_{0}([−k, k]K_{n}) (which consists of all k-composed partitions and ordinary partitions of [n]), and other related lattices and semilattices in terms of k-composed partial partitions [31, Ch. III].

Recently Gill [15, 16] has studied the weakly composed partition semilattice C_{n}(k) in the guise of the intersection semilattice of the canonical affine hyperplanar lift representation of [−k, k]K_{n}. In particular, p_{ℋ} (λ) = λ^{2} − (2k + 1)\binom{n}{2}λ + [3k(k + 1)n + \frac{3n−1}{4}]\binom{n}{3} generically. Example 11.5. Figure 11.5 displays Φ_{4} = [−2, 2]K_{4} and the generic planar arrangement ℋ(Φ_{4}; Q) with Q_{1} = (0, 0), Q_{2} = (0, 2), Q_{3} = (2, 1), Q_{4} = (3, 2). Since χ_{Φ_{4}}^{b}(λ) = λ(λ − 9)_{3}, the characteristic polynomial p_{ℋ} (λ) = λ^{2} − 39λ + 299. Thus there are 330 regions, 270 of them bounded.

**********************************************************

Place FIGURE 11.5 near EXAMPLE 11.5. **********************************************************

From Corollary 10.5 and Lemma 10.7 with q = (2k + 1)\binom{n}{2}, s_{2} = 3(2k + 1)^{2}\binom{n+1}{4}, and t = (3k^{2} + 3k + 1)\binom{n}{3} (or with greater difficulty from (11.2)) we get the first few Whitney numbers of C_{n}(k) and the face and flat numbers in two dimensions.

11.5. The same, without bisectors. We take Φ′_{n} = {±1, ±2, …, ±k}K_{n} to be the additive real gain graph on n vertices that has an edge of gain i between each pair of vertices for every i = ±1, …, ±k. That is, it is the example of Section 11.4 without the bisectors of the reference segments. This Pythagorean gain graph gives us 2k perpendiculars to each reference line, placed symmetrically about the bisector and equally spaced on each side of it, identically spaced—in Pythagorean coordinates—along all reference lines, but omitting the bisector.

Figure 11.3. The gain graph Φ_{4} = [−2, 2]K_{4} and a portion of the Pythagorean line arrangement of Example 11.5. The heavy lines are the perpendicular bisectors. In the gain graph, in each set of parallel edges the gains are the same; they are only marked for edges e_{12}.

The balanced chromatic polynomial, χ_{Φ′_{n}}^{b}(λ), can be computed from (11.1) by [31, Prop. I.4.4]. Omitting the details, which will appear in [31, Ch. III], the result is that

(11.4)  ∑_{n=1}^{∞} χ_{Φ′_{n}}^{b}(λ)\frac{z^{n}}{n!} = e^{λf(z)} − 1,

where f(z) is determined by

f′(z) = ∑_{j=0}^{∞} \binom{λ−jk−1}{j}z^{j} and f(0) = 0.

From this one can extract the balanced chromatic polynomial itself and thus the Whitney numbers of the first kind and, by the methods of Section 10, the region and bounded region numbers in any dimension d.

Replacing z by −z, if we set λ = −1 Equation (11.4) becomes the exponential generating function for r_{n}, the number of regions of ℋ(Φ′_{n}; Q) when d = n − 1. If we set λ = 1 it becomes the exponential generating function for the number of bounded regions.

In the plane we can compute all Whitney number from Lemma 10.7 and the values q = 2k\binom{n}{2}, s_{2} = 12k^{2}\binom{n+1}{4}, and t = k(k + 1)\binom{n}{3}. Then p_{ℋ} (λ) = λ^{2} − 2k\binom{n}{2}λ + 3k(kn + 1)\binom{n}{3}. Example 11.6. In Figure 11.6 are Φ′_{4} = {±1, ±2}K_{4} and its Pythagorean line arrangement ℋ(Φ′_{4}; Q). From the general planar characteristic poynomial we have p_{ℋ} (λ) = λ^{2}−24λ+216. There are 241 regions and 193 are bounded.

**********************************************************

Place FIGURE 11.6 near EXAMPLE 11.6. **********************************************************

Example 11.7. Just two perpendiculars to each reference line. We specialize to the case k = 1, that is, Φ′_{n} = {+1, −1}K_{n}. We may look upon Φ′_{n} as a directed graph, an edge e with φ′_{n}(e; i, j) = +1 being interpreted as an arc directed from i to j. Thus we are discussing the poise lift matroid of the complete digraph. (See the definition of poise bias in [30, Ex. I.6.5].)

Here the exponential generating function of r_{n} has a remarkable expression. The Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} have ordinary generating function f_{C}(z) = ∑_{0}^{∞} C_{n}z^{n} = (1 − \sqrt{1 − 4z})/2z, as is well known. Then f(−z)|_{λ=−1} = f_{C}(z) − 1 so

1 + ∑_{n=1}^{∞} r_{n} \frac{z^{n}}{n!} = e^{f_{C}(z)−1} = exp (\frac{1 − \sqrt{1 − 4z}}{2z} − 1) .

The explanation is found in the observation of Postnikov and Stanley that (in our language) ℋ([−1, 1]K_{n}; Q) with the affinographic reference points of Example 3.2—equivalently, any affinely independent reference points—has n!C_{n} regions [21, Prop. 7.2]. Thus they call it and ℋ({±1}K_{n}; Q) with similar reference points Catalan arrangements [21, (3.8)].

We mention that Athanasiadis [2, Thm. 5.3] has a different formula from ours for converting the exponential generating function of p(Lat^{b}[−1, 1]K_{n}; λ) to that for p(Lat^{b} Φ′_{n}; λ), as do Postnikov and Stanley though stated there only for the number of regions ([21, Thm. 7.1], announced in [25, Thm. 2.3]. The application to the characteristic polynomial follows from the exponential formula of [25, Thm. 1.2]).

Figure 11.4. The gain graph Φ′_{4} = {±1, ±2}K_{4} and part of the Pythagorean line arrangement from Example 11.6. The heavy lines are the perpendicular bisectors.

11.6. Symmetric, uniform Pythagorean hyperplanes: even case. Here the Pythagorean gain graph is Φ′′_{n} = {±1, ±3, …, ±(2k − 1)}K_{n}, in which each pair of vertices is joined by 2k edges whose gain values are ±i for every odd i ≤ 2k (or, what is essentially the same, ±δi for any fixed δ > 0). This gain graph corresponds to an arrangement of 2k perpendiculars to each reference line, symmetrically placed around the bisector and—in Pythagorean coordinates—identically spaced along all reference lines.

Athanasiadis [2, Thm. 5.2] has produced a remarkable expression for p_{Lat^{b} Φ}(λ) (that is, χ_{Φ′′_{n}}^{b}(λ)/λ) when Φ has a form that includes our examples from Sections 11.4, 11.5, and 11.6. For A a finite set of positive integers and A^{0} = A ∪ {0}, let Φ_{n} = (±A)K_{n} and Φ_{n}^{0} = (±A^{0})K_{n}. By taking A = {1, 3, …, 2k − 1} in Athanasiadis’ theorem we find that, for sufficiently large integers λ, p(Lat^{b} Φ′′_{n}^{0}; λ) is the coefficient of x^{λ−2n} in the expression

(n − 1)! (\frac{1 + x^{2k−1}}{1 − x^{2}} )^{n} .

The conclusion is that Lat^{b} Φ′′_{n}^{0} has characteristic polynomial

p′′_{n}^{0}(λ) = ∑_{\begin{matrix}i=0 \\ even \end{matrix}}^{n} \binom{n}{i} (\frac{λ+i}{2} − 1 − ki)_{n−1}

= ∑_{\begin{matrix}i=0 \\ odd \end{matrix}}^{n} \binom{n}{i} (\frac{λ+i}{2} − 1 − ki)_{n−1}

and therefore

p′′_{n}^{0}(λ) = \frac{1}{2} ∑_{i=0}^{n} \binom{n}{i} (\frac{λ+i}{2} − 1 − ki)_{n−1}

for n > 0. Now we apply the argument of Athanasiadis [2, Thm. 5.3] to obtain the polynomial of Lat^{b} Φ′′_{n}:

p′′_{n}(λ) = ∑_{l=1}^{n} S(n, l)p′′_{l}^{0}(λ)

= \frac{1}{2} ∑_{l=1}^{n} ∑_{i=0}^{l} S(n, l)\binom{l}{i} (\frac{λ+i}{2} − 1 − ki)_{l−1}

for n > 0. From this the characteristic polynomial of a generic arrangement ℋ(Φ; Q) in 𝔼^{d} can be found via Theorem 10.3.

For applications probably the most significant case is that in which k = 1. This case is easier to analyze because it is the same as Example 11.7.

A triangle cannot be balanced in this example, no matter what value k has. Hence t = 0, q = 2k\binom{n}{2}, and s_{2} = 12k^{2}\binom{n+1}{4} in Corollary 10.5; these give the face and flat numbers of a generic planar ℋ(Φ′′_{n}; Q). Thus p_{ℋ} (λ) = λ^{2} − 2k\binom{n}{2}λ + 12k^{2}\binom{n+1}{4} generically. In this example we can go further: since there are no balanced triangles we can compute the number of balanced quadrilaterals and use this to get the Whitney numbers needed for the face and flat numbers in 𝔼^{3}. Omitting the somewhat lengthy details, the Whitney numbers w_{i3} are given by Lemma 10.7 with F_{n−3} = k^{3}(n^{3} − 5n − 12)\binom{n}{3} and t′ = 6[16\binom{k+1}{3} + 3k]\binom{n}{4}.

Example 11.8. We take k = 2 and n = 4 so that we need Φ′′_{4} = {±1, ±3}K_{4}. However, so that perpendiculars of each parallel class will be separated by the same distance as in Example 11.5, we divide the gains by 2, giving gain graph \frac{1}{2}Φ′′_{4} = \{±\frac{1}{2}, ±\frac{3}{2}\}K_{4}. This has no effect on balance, so the face and flat counts remain the same. The solid lines in Figure 11.8 display the gain graph and corresponding generic Pythagorean arrangement. Adding in the dashed lines we have \frac{1}{2}Φ′′_{4}^{0} = \{0, ±\frac{1}{2}, ±\frac{3}{2}\}K_{4} and the asociated Pythagorean arrangement.

**********************************************************

Place FIGURE 11.8 near EXAMPLE 11.8. **********************************************************

12. The voter debates

Once Good and Tideman had introduced the geometrical model of bisecting hyperplanes^{5} it was easy to imagine more elaborate but also plausible variations and to ask for the number of possible outcomes. In the more elaborate models, an outcome may no longer be a simple preference ranking. For example, one of the variations is to allow discrete degrees of preference; an outcome is then the whole set of degrees of preference the voter feels between each pair of candidates.

In the Good–Tideman model, the voter must choose one over the other for every pair of candidates. (We ignore borderline cases.) A more sophisticated voter would expect to see a measurable difference before forming a preference. We can grade models by the degree of sophistication the voter shows in comparing two candidates. A voter at the lowest level simply chooses one of the two. At the second level she has three options: prefer the candidate who is significantly superior or remain neutral if neither is.^{6} A voter in the third level of sophistication distinguishes four choices: strong or weak preference for either candidate. One at the fourth level adds the option of remaining neutral. And so forth.

Each level of sophistication can lead to a variety of models depending on how the voter chooses to define the boundaris between different options. Let us assume the choice is always made on the basis of modified Pythagorean coordinates as in Equation (3.1): in other words, the regions within which the voter chooses a particular option for evaluating Q_{i} vis-á-vis Q_{j} are demarcated by hyperplanes perpendicular to the line Q_{i}Q_{j}, measured by Pythagorean coordinate times some power of the distance between the candidates. (Otherwise we need a new theory.) Then we have to consider how the voter might place the choice boundaries. There are several directions of classification. First is the rule of placement: the rule may specify for each hyperplane its Pythagorean coordinate, its actual distance from the midpoint of segment [Q_{i}, Q_{j}], its proportional distance as a fraction of d(Q_{i}, Q_{j}), or some other exponent α in (3.1). Second is homogeneity: the same rule of location may be used for every pair of candidates, or the voter may emplace boundaries at random (random, of course, to Figure 11.5. The gain graphs and line arrangements of Example 11.8. The heavy lines (which are dashed) are the perpendicular bisectors. the observing sociometrician, who does not know the voter’s reasons). Third is symmetry: the boundaries for comparing Q_{i} with Q_{j} may be symmetrical, or they may not. Fourth is uniformity: the boundary hyperplanes for a given pair of candidates may be uniformly spaced (in the chosen measurement scheme) or they may not.

5The general idea of bisecting hyperplanes’ modeling voter choice was well known. As an application of Voronoi diagrams, it uses only parts of hyperplanes. It was the new idea of Good and Tideman to consider the entire candidate ranking that gave a role to whole hyperplanes. I am not aware of any other similar work.

6The idea of an “indifference region” appeared (independently and somewhat earlier) in the nearestneighbor study of Cacoullos [7, §5]. The delimiting hyperplanes of Cacoullos’ indifference region are fixed by proportional distance, not Pythagorean coordinate, and are based on affinely independent reference points.

Still, this is the only place I know of that treats what we would call unbalanced gains.

Thus there are five dimensions along which we can classify voting models of our general type. Fortunately for us, they lead to just a few mathematical situations.

Let us suppose the voter is at a definite level of sophistication, say the M-th level, where there are M + 1 options divided by M hyperplanes between each pair of candidates.

If the voter applies the distance or proportional rule of placement or any other rule of type (3.1) with α ≠ 0, then (in general) the only thing that matters is whether she chooses to use bisecting hyperplanes. (That is what we learn from Theorem 8.1.) If she follows a symmetrical demarcation scheme with odd M, there will be a bisector between each pair of candidates and we are in the situation of Section 11.3 (Section 11.1 if M = 1). Otherwise she will not (in general) take any bisectors and we have the example of Section 11.2 with m = M.

If the voter uses a placement rule with random hyperplanes, the same remarks apply. We will be in Section 11.2 with m = M unless she deliberately chooses bisectors, when Section 11.3 or 11.1 applies.

A homogeneous Pythagorean placement rule leads to more varied mathematics.

A uniform symmetrical rule puts us in Section 11.1 (Corollary 11.3) if M = 1: this is the original case where there is one dividing hyperplane for each pair and it is the bisector (since it is symmetrically placed). When M > 1, the voter is using dividing hyperplanes with coordinates ψ_{ij}(h) = 0, ±δ, …, ±lδ when M is odd, M = 2l + 1, but ψ_{ij}(h) = ±δ, ±3δ, …, ±(2l − 1)δ when M = 2l is even. This puts us in Section 11.4 if M is odd and Section 11.6 if M is even, Example 11.7 if M = 2.

Asymmetric rules in general seem implausible, but there is one that deserves attention. That is where the voter always prefers one in each pair of candidates (M = 1, the first level of sophistication) but has a biased decision rule instead of simply choosing the nearer candidate. Even an unsymmetrical decision rule gives an arrangement of hyperplanes with balanced Pythagorean gain graph, if the voter has for each candidate Q_{i} what we might call a “prior bias” q_{i} (whether a preference or a prejudice) and the dividing hyperplane h_{ij} has Pythagorean coordinate ψ_{ij}(h_{ij}) = q_{i} − q_{j}; that is, it is offset due to the bias. The more q_{j} exceeds q_{i}, the more h_{ij} will retreat from Q_{j} in the direction of Q_{i}, so favoring Q_{j}. Then Corollary 11.1 tells us that the voter has the same number of possible rankings as in Good and Tideman’s original model.

The actual preference rankings that correspond to the regions of ℋ are wholly unknown, although they must be somehow related to the oriented matroid structure of ℋ. Research Problem 4. (a) What structure is there to the set 𝒪 of preference orderings that is realized by a generic arrangement of all the perpendicular bisectors of n reference points in d-space? (𝒪 is not, as (1.1) suggests, the set of all permutations of {1, …, n} that have at least n − d cycles. An easy example of 4 planar points suffices to disprove that.) (b) Which orderings correspond to unbounded regions? (c) Which new orderings appear as the dimension rises? (d) Characterize the sets 𝒪 that arise from all different possible generic reference points in fixed dimension. Research Problem 5. Generalize Research Problem 4 to arrangements of only some perpendicular bisectors.

Research Problem 6. Generalize Research Problem 4 to arrangements with indifference regions or degrees of preference.

13. Further research

13.1. Nongenericity. We observed in the introduction that an exact description of generic reference points is unknown. This is unsatisfactory. Research Problem 7. Given a real, additive gain graph Φ, characterize genericity (with respect to Φ) of reference points. That is, what are the properties of Q that guarantee that ℒ(ℋ(Φ; Q)) is generic? At a minimum, characterize genericity amongst those Q having ideal general position.

13.2. Special position. Suppose we require certain subsets of the Q_{i} to be affinely dependent but ask for genericity in other respects; or suppose we even prescribe certain parallelisms. It should still be possible to deduce the number of resulting regions by abstract combinatorial means, similar to those of this paper but considerably more complex. Probably, the essential information about the reference points Q_{i} is specified by their affine dependencies and the configuration at infinity of the lines they determine. Abstractly these would be described by their affine dependence matroid and a comap of that matroid to account for behavior at infinity. Research Problem 8. Develop the structure theory of ℒ(ℋ(Φ, Q)) and ℒ(ℋ_{ℙ}(Φ, Q)) for reference points that have (a) specified affine dependencies, (b) simple position but specified behavior at infinity, or (c) both specified affine dependencies and specified behavior at infinity, but are otherwise generic. Especially, compare their (semi)lattice structures to those of Lat^{b} Φ and Lat L_{0}(Φ).

Part (a) will be solved by defining the complete lift matroid of a biased graph with a matroid given on the vertex set, which is a problem of great intrinsic interest. Research Problem 9. Develop the enumerative theory of perpendicular dissections whose reference points have affine or infinite special position or both, but are otherwise generic.

13.3. Hyperbolic dissections. The way Good and Tideman argued for their arrangement of bisectors was this: The voter prefers the nearer of two candidates. The boundary between preference domains is the locus of points equidistant from both candidates. That is the perpendicular bisector of the connecting line segment.

If we apply the same reasoning to a more sophisticated voter, it leads us to a hyperbolic rather than a hyperplanar dissection. Suppose the voter has second-level sophistication with the rule that she prefers one candidate only if its nearness exceeds the other’s by some threshold δ. That is, if the voter falls in the domain where |d(P, Q_{j}) − d(P, Q_{i})| < δ, she is neutral. If d(P, Q_{j}) − d(P, Q_{i}) > δ, she prefers Q_{i}. This mathematics gives us three preference domains separated by the hyperboloid of revolution |d(P, Q_{j}) − d(P, Q_{i})| = δ. The theory of hyperplane dissections does not apply.

Problems of dissection by entire curved subspaces are little studied. The planar hyperbolic Dirichlet tessellations (that is, Voronoi diagrams) of [1, §2] are closely related, though in their subject (that of generalized Voronoi diagrams) only parts of curves and surfaces are employed. There is a partial theory of topological dissections [28], which are more complicated than linear dissections because one has to determine not only the semilattice of intersections but also the topology of each intersection and each region, or at least their Euler characteristics.

It does seem possible that the special properties of hyperboloids on shared foci may make it possible to solve some cases at least of the hyperbolic preference ranking problem. Research Problem 10. Solve the second-level hyperbolic voter ranking problem in the plane. The problem is to determine the maximum number of possible preference rankings if the voter P prefers the nearer of candidates Q_{i} and Q_{j} if |d(P, Q_{i}) − d(P, Q_{j})| > δ_{ij} and is neutral otherwise. The δ_{ij} are positive numbers that may be taken all equal if that helps the solution. Research Problem 11. Decide whether the solution to Problem 10 is generic. That is, is the set of choices of candidates for which the maximum is attained dense in (𝔼^{2})^{n}?

13.4. Other scalar fields. Let us speculate about an inner product space over an arbitrary field F. (All the opinions in this section are unverified wish and hope.) Our results should largely apply to any ordered field. Regions, faces, and the intersection semilattice are defined; the field is topologized so generic position exists; everything seems to work except for a possible difficulty with gains, explained below. Over an unordered field there is an intersection lattice but there are no regions or faces. The fundamental problem there is that of genericity. Defining it would seem to call for a topology on F, but it would be very interesting to see a definition that avoids this, perhaps by basing genericity on a suitable subfield like ℚ or the p-adics.

Finite fields would require an altogether different approach.

The appropriate gain group for an arbitrary inner product space might not be F^{+}. Let D be the set of values of ⟨v, v⟩ − ⟨w, w⟩ for v, w ∈ F^{d}, where ⟨x, y⟩ is the inner product. The gains of a Pythagorean gain graph over F must be chosen in D. As long as D is an additive group (as for instance when F = ℚ or ℝ, so D = F; or when F = ℂ, so D = ℝ), the parts of our theory that involve switching, as required for cross-sections and induced arrangments (Section 7), should carry over.

Complex space is especially interesting. Every coefficient of the characteristic polynomial of ℋ has meaning. The integral cohomology of the complement of the arrangement is determined by the intersection semilattice ℒ(ℋ) and the rank of the ith cohomology group equals |w_{d−i}(ℒ(ℋ))|, the magnitude of the (d − i)th Whitney number of the first kind, by the theorems of Orlik and Solomon ([19], [20, Ch. 5]).

References

[1] Peter F. Ash and Ethan D. Bolker, Generalized Dirichlet tessellations. Geom. Dedicata 20 (1986), 209–243. MR 87h:52026. Zbl. 586.52011.

[2] Christos A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields. Adv. Math. 122 (1996), 193–233. MR 97k:52012. Zbl. 872.52006.

[3] F. Aurenhammer, Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16 (1987), 78–96. MR 88d:68096. Zbl. 616.52007.

[4] Claude Berge, Graphs and Hypergraphs. North-Holland Math. Lib., Vol. 6. North-Holland, Amsterdam-London; American Elsevier, New York, 1973. MR 50 #9640. Zbl. 311.05101.

[5] Claude Berge, Graphs. Second rev. ed. [of Part 1 of [4]]. North-Holland Math. Lib., Vol. 6, Part 1. North-Holland, Amsterdam-New York, 1985. MR 87e:05050. Zbl. 566.05001.

[6] T. Brylawski, Constructions. In Neil White, ed., Theory of matroids, pp. 127–223. Encycl. Math. Appl., Vol. 26. Cambridge Univ. Press, Cambridge, 1986. MR 87k:05054 (book). Zbl. 596.05013.

[7] Theophilos Cacoullos, Comparing Mahalanobis distances I: Comparing distances between k known normal populations and another unknown. Sankhyā Ser. A 27, 1–22. MR 32 #4787. Zbl. 138, 146a.

[8] Paul A. Clement, The concurrency of perpendiculars. Amer. Math. Monthly 65 (1958), 601–605. MR 20 #5451. Zbl. 85, 149a.

[9] L. Comtet, Advanced Combinatorics. D. Reidel, Dordrecht, 1974. MR 57 #124. Zbl. 283.05001.

[10] H.S.M. Coxeter, Introduction to geometry. Wiley, New York, 1961. MR 49 #A1251. Zbl. 95, 345b.

[11] P.H. Edelman and V. Reiner, Free arrangements and rhombic tilings. Discrete Comput. Geom. 15 (1996), 307–340. MR 97f:52019. Zbl. 853.52013. Erratum. ibid. 17 (1997), 359. MR 97k:52013. Zbl. 853.52013.

[12] Herbert Edelsbrunner, Algorithms in combinatorial geometry. EATCS Monographs Theoret. Computer Sci., Vol. 10. Springer-Verlag, Berlin, 1987. MR 89a:68205. Zbl. 634.52001.

[13] Herbert Edelsbrunner and Raimund Seidel, Voronoĭ diagrams and arrangements. Discrete Comput. Geom. 1 (1986), 25–44. MR 87m:68034. Zbl. 598.52013.

[14] Roberto Frucht W. and Gian-Carlo Rota, La función de Möbius para particiones de un conjunto. Scientia (Valparaíso, Chile) No. 122 (1963), 111–115. MR 33 #55.

[15] Robert Gill, The number of elements in a generalized partition semilattice. Discrete Math. 186 (1998), 125–134. MR 99e:52014. Zbl. 956.52009.

[16] Robert Gill, The action of the symmetric group on a generalized partition semilattice. Electron. J. Combin. 7 (2000), Research Paper 23, 20 pp. MR 2001g:05107. Zbl. 947.06001.

[17] I.J. Good and T.N. Tideman, Stirling numbers and a geometric structure from voting theory. J. Combinatorial Theory Ser. A 23 (1977), 34–45. MR 58 #21647. Zbl. 354.05008.

[18] J.H. Mason, Matroids as the study of geometrical configurations. In Martin Aigner, ed., Higher Combinatorics (Proc. NATO Adv. Study Inst., Berlin, 1976), pp. 133–176. NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., Vol. 31. D. Reidel, Dordrecht, 1977. MR 80k:05037. Zbl. 358.05017.

[19] Peter Orlik and Louis Solomon, Combinatorics and topology of complements of hyperplanes. Invent. Math. 56 (1980), 167–189. MR 81e:32015. Zbl. 432.14016.

[20] Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes. Grundl. math. Wiss., Vol. 300. Springer-Verlag, Berlin, 1992. MR 94e:52014. Zbl. 757.55001.

[21] Alexander Postnikov and Richard P. Stanley, Deformations of Coxeter hyperplane arrangements. J. Combin. Theory Ser. A 91 (2000), 544–597.

[22] Alfréd Rényi, Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 (1959), 73–85. MR 22 #6735. Zbl. 93, 376d.

[23] Gian-Carlo Rota, The number of partitions of a set. Amer. Math. Monthly 71 (1964), 498–504. MR 28 #5009. Zbl. 121, 18c.

[24] Gian-Carlo Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions. Z. Wahrsch. verw. Gebiete 2 (1964), 340–368. MR 30 #4688. Zbl. 121, 24f. Many times reprinted.

[25] Richard P. Stanley, Hyperplane arrangements, interval orders, and trees. Proc. Nat. Acad. Sci. USA 93 (1996), 2620–2625. MR 97i:52013. Zbl. 848.05005.

[26] Michelle L. Wachs and James W. Walker, On geometric semilattices. Order 2 (1986), 367–385. MR 87f:06004. Zbl. 589.06005.

[27] Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Amer. Math. Soc., No. 154 (= Vol. 1, Issue 1). Amer. Math. Soc., Providence, R.I., 1975. MR 50 #9603. Zbl. 296.50010.

[28] Thomas Zaslavsky, A combinatorial analysis of topological dissections. Advances in Math. 25 (1977), 267–285. MR 56 #5310. Zbl. 406.05004.

[29] Thomas Zaslavsky, Bicircular geometry and the lattice of forests of a graph. Quart. J. Math. Oxford (2) 33 (1982), 493–511. MR 84h:05050c. Zbl. 519.05020.

[30] Thomas Zaslavsky, Biased graphs. I. Bias, balance, and gains. II. The three matroids. III. Chromatic and dichromatic invariants. IV. Geometrical realizations. J. Combin. Theory Ser. B 47 (1989), 32–52; 51 (1991), 46–72; 64 (1995), 17–88; to appear. MR 90k:05138, 91m:05056, 96g:05139. Zbl. 714.05057, 763.05096, 950.25778.

[31] Thomas Zaslavsky, Geometric lattices of structured partitions. I: Gain-graphic matroids and group valued partitions. II: Lattices of group-valued partitions based on graphs and sets. III: Composed and sequenced partitions. IV: Forests, fat forests, acyclic partition sequences, and the biased union. V: Tatters. Manuscripts, 1985 (I–II); in preparation since 1985 (III–V).

Binghamton University, Binghamton, N.Y., U.S.A. 13902-6000