Also available at http://amc.imfm.si ISSN 1855-3966 (printed ed.), ISSN 1855-3974 (electronic ed.) ARS MATHEMATICA CONTEMPORANEA 1 (2008) 206–222 Omittable Lines Leah Wrenn Berman Ursinus College, Department of Mathematics and Computer Science, P.O. Box 1000, Collegeville, Pennsylvania, USA Branko Grünbaum University of Washington, Department of Mathematics, Seattle, WA 98195, USA Jonathan Lenchner IBM Thomas J. Watson Research Center, 19 Skyline Drive, Hawthorne, NY 10532, USA Received 1 July 2008, accepted 7 December 2008, published online 28 December 2008 Abstract Given a collection of n lines in the real projective plane, a line ` is said to be omittable if ` is free of ordinary points of intersection—in other words, if all the intersection points of ` with other lines from the collection come at the intersection of three or more lines. Given a collection of lines L, denoting by O(L) the set of all omittable lines in the collection and by g(L) the cardinality of O(L), we describe three infinite families of lines that can serve as O(L) for suitable L and also display a finite set of sporadic additional examples such that O(L) does not fall into any of the three families. We derive bounds on the size of g(L) in caseO(L) falls into one of the three infinite families and weaker bounds for the more general case. Keywords: Aggregates, arrangements, omittable lines. Math. Subj. Class.: 52C30, 52C99 1 Introduction A family L of n = n(L) distinct straight lines in the plane, not all through one point, de- termines an aggregate A(L). An aggregate is the geometric structure consisting of all the lines of L together with all the vertices V(L), that is, intersections of two or more of the lines of L. By “plane” we mean the real projective plane, which we envisage as modeled by the E-mail addresses: lberman@ursinus.edu (Leah Wrenn Berman), grunbaum@math.washington.edu (Branko Grünbaum), lenchner@us.ibm.com (Jonathan Lenchner) Copyright c© 2008 DMFA – založništvo L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 207 extended Euclidean plane. This is the ordinary Euclidean plane augmented by the points- at-infinity (where each such point corresponds to a family of all mutually parallel Euclidean lines) and the line-at-infinity (which is formed by the totality of the points-at-infinity). A vertex V ∈ V(L) of an aggregateA(L) is said to be k-fold if it lies on precisely k lines of L. A 2-fold vertex is called ordinary. A well-known but nontrivial result of combinatorial geometry is that every aggregate contains at least one ordinary vertex. This was conjectured by J. J. Sylvester [22] in 1893, but forgotten and independently asked by P. Erdős some fifty years later. Detailed references and proofs, as well as strengthenings and extensions, may be found, among others, in [3, 4, 7, 8, 9, 20]. We are interested in the following question: Given an aggregate A(L), are there any lines of L that contain no ordinary vertices? Each line with this property is said to be an omittable line of L, since its omission from L does not decrease the number of vertices of the aggregate. We denote the totality of omittable lines of L by O(L), and the number of lines in O(L) by g(L). We are interested in the relations between g(L) and n(L). In particular, we shall discuss various types of families of lines that can serve as O(L) for some L. The topic is equivalent (by duality in the projective plane) to the questions on omittable points considered in [15]. The aim of the present note is to extend the results of [15], and to correct an omission and an error of that paper (see Section 2 below). We shall freely use both the “omittable lines” and the dual “omittable points” approaches. The line-centric approach is perhaps more natural because of the additional explicit structure (vertices in the line-centric approach versus connecting lines in the point-centric approach), but, for example in the proofs of Theorems 4 and 5, we feel that the point-centric approach is sometimes more intuitive. 2 History of the topic The concept of omittable points was introduced by K. Koutsky and V. Polák [17] in 1960; however, it seems that for a long time this paper elicited no additional investigations. Inde- pendently, the concept was introduced by W. F. Smyth [21] in 1989. Working in the omittable points version, Koutsky and Polák proved several results, which we can formulate for omit- table lines as follows. Theorem 1. If an aggregate A(L) of n = n(L) lines, not all in a pencil, contains g = g(L) ≥ 3 omittable lines that form a pencil, then n ≥ 3g. Moreover, for every g ≥ 3 there exists such a set L of 3g lines with g omittable lines in a pencil. Theorem 2. Any set O of lines forming a pencil is the set O(L) of omittable lines for some aggregate A(L) of lines L. In a series of talks on families of lines, which one of the authors of this note (B. G.) gave in 1974 at the University of Washington, the results of Koutsky and Polák were presented with simplified proofs and with some additional examples. A quarter century later, in 1999, a short note [15] was published, describing the work of Koutsky and Polák; the note contained the above Theorem 1 and the following strengthening of Theorem 2. Theorem 3. Any setO of g lines forming a pencil is the setO(L) of omittable lines for some aggregate A(L) of lines L with n(L) ≤ g + 2g . One of the authors of this note (J. L.) pointed out (in a private communication to B. G.) two errors of the note [15]. In Theorem 1 of [15] the first part should have been “If a set 208 Ars Mathematica Contemporanea 1 (2008) 206–222 of n points, not all collinear, contains k ≥ 3 collinear omittable points, then n ≥ 3k”. Unfortunately, the word “collinear” italicized here was omitted from the formulation in [15], although it was used in the proof, and the assertion is clearly not valid without it. (This error was also mentioned by Richard Koch, in his review of [15] in the “Zentralblatt” v. 941 #51019; however, the review was noticed only recently.) The second error concerns the claim that the example in Figure 2 of [15] shows 13 points of which 6 are omittable. However, the example has only 4 omittable points. As indicated in Figure 5 below, as far as is known, 14 is the smallest number of lines in an aggregate with 6 omittable lines. These facts led to a reinvestigation of the topic of omittable lines, and the results of this activity are the main contents of this note. 3 The main results In trying to describe the results on omittable lines, it seems most useful to start by distinguish- ing various possibilities regarding the sets of omittable lines, rather than with aggregates of lines as such. In particular, we are interested in finding families O of lines that can serve as O(L) for appropriate L. More precisely, for any family O in some collection Q of families, we would like to decide whether every member O of Q is O(L) for some L, as well as find special members of Q for which it is possible to find aggregates L with small n(L). We find it convenient to consider separately the following cases: 1. Q consists of all pencils O such that O = O(L) for some aggregate L. 2. Q consists of all near-pencils O such that O = O(L) for some aggregate L. (A near- pencil consists of a pencil together with one line not in the pencil.) 3. Q consists of all families O formed by a pencil with two additional lines not in the pencil, such that O = O(L) for some aggregate L. We shall sometimes refer to such a family as a near-near-pencil. 4. Other possibilities for O = O(L); we call these Os sporadic. Case 1, in which the family Q consists of all pencils, is covered by Theorems 1, 2 and 3. This information can be succinctly stated as follows: Theorem 4. If Q is the family of pencils, then any aggregate L with O(L) ∈ Q has n(L) ≥ 3g. Moreover, for any pencil P ∈ Q we can find an aggregate L with n(L) = g + 2g and O(L) = P . Finally, for every g ≥ 3 there exists a pencil P and an aggregate L with O(L) = P, g = g(L) and n(L) = 3g. Proof. For completeness, and also since the proof requires only minor changes in order to establish Theorem 5, we repeat the arguments from [15]. The first part of the theorem is most intuitively argued in the dual formulation, where we deal with point aggregates rather than line aggregates. Connecting lines take the place of vertices and a point is omittable if its removal from the aggregate does not cause the number of connecting lines to be reduced. In the dual formulation we assume that we are given a family P of g collinear points. Without loss of generality we may take the line containing P to be the line-at-infinity. Consider the convex hull C of the points of L that lie in the finite part of the plane. Obviously, C is 2-dimensional, and every point of P determines two support parallel lines of C; since each point of P is omittable, each of the support lines contains at least two vertices of C. Hence each point of P is associated in this way with at least four vertices of C. Moreover, by L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 209 convexity, each vertex of C is associated with at most two points of P . Therefore C has at least 2g vertices, and so n(L) ≥ 2g + g = 3g. To establish the existence of an aggregate of size g + 2g with the asserted properties, let P be an arbitrary set of g points p1, ..., pg on the line-at-infinity. We start with any points q1, q2 not on the line-at-infinity, collinear with p1, then construct translates q3, q4 of q1, q2 by a suitable vector v2 in the direction of p2; these four points qj are translated by a vector v3 in the direction of p3, where the length of the vectors being chosen at each step are such that no three of the resulting points qj are collinear, nor are pairs of the qjs accidentally collinear with any of the pj . Repeating the same procedure for the remaining pis we arrive at a set L consisting of g + 2g points and having precisely the set P of omittable points. Finally, to establish the existence of the advertised aggregate of size 3g, revert to the aggregate (of lines) formulation. Start with a regular 2g-gon R, and take as L the 2g lines determined by the sides ofR, together with the g mirrors (lines of symmetry) ofR that pass through pairs of its antipodal vertices. These g mirrors form O(L). This is illustrated in Figure 1. In it, as well as in other diagrams, the lines in O(L) are shown as dashed black lines, and the lines of L that are not omittable are shown as solid black lines. In the above proof we argued about the convex hull of the points—since the upper (respec- tively lower) hull of a set of points corresponds to the lower (respectively upper) envelope of the dual set of lines, the proof could easily be altered to work with the line-centric approach using essentially the same ideas. The point-centric view seems, however, to be just a bit more transparent. Figure 1: Examples of aggregates in which O(L) is a pencil and n(L) = 3g. Here g = 3, 4. These results can be extended to case 2. Theorem 5. If Q is the family of near-pencils, then any aggregate L with O(L) ∈ Q has n(L) ≥ 3g − 2. Moreover, for any near-pencil O ∈ Q we can find an aggregate L with n(L) = 2g + g − 2 and O(L) = O. Finally, for every even g ≥ 4 there exists a near-pencil O and an aggregate L with O(L) = O, g = g(L) and n(L) = 3g − 2. Proof. To prove the lower bound on n(L) we only need to repeat the argument from the proof of Theorem 4, noticing that now we need only 2(g−1) support lines, since there are only g−1 points at infinity. If C has more than 2(g− 1) vertices then n(L) > 2(g− 1) + g− 1; that is, n(L) ≥ 2(g−1)+g = 3g−2. The rest of the argument depends on whether the last of the g 210 Ars Mathematica Contemporanea 1 (2008) 206–222 points, say pg , is a vertex ofC or not. If pg is not a vertex, then n(L) ≥ 2(g−1)+g = 3g−2. But if pg is a vertex, then there must be some point of L in the interior of C, hence yielding the same estimate. Indeed, if there were no such point in the interior then the lines through pg and the other 2g − 3 vertices would determine 2g − 3 directions, and on each of these lines there would have to be a point-at-infinity, since pg is omittable. Thus 2g− 3 ≤ g− 1 or g ≤ 2, contradicting the assumption g ≥ 3. For an arbitrary near-pencil we repeat the construction in the proof of Theorem 4; now the line-at-infinity carries g − 1 points p1, p2, ..., pg−1, and the point pg is not on that line. We modify the construction by first taking q1 to coincide with pg . This yields a set S of 2g−1 finite points, which includes pg . All the other points of P are omittable with respect to this set S, but we need to take care of pg . To do this we construct a set S∗ by mapping S \ {pg} homothetically with center pg and a ratio chosen not to generate any extraneous collinearities. Thus we can take as L the union of S with S∗ and with the g− 1 points at infinity, for a total of 2g−1 + 2g−1 − 1 + g − 1 = 2g + g − 2 = n(L) points. Finally, for the near-pencil which is O(L) for an aggregate with n(L) = 3g − 2, again in the omittable lines version, start with the same construction as in the final paragraph of the proof of Theorem 4, this time with C a regular (2g − 2)-gon. Adding to the resulting aggregate the line-at-infinity yields a family L with n(L) = 3g − 2. If we number the edges of C in clockwise order e1, ..., e2g−2 and say that vertex v1 lies between e2g−2 and e1, that vertex v2 lies between e1 and e2, and so on, then a line of symmetry cuts through v1 and vg , another cuts through v2 and vg+1, and so forth. If g is even, then g − 1 is odd so that the line of symmetry cutting through v1 and vg is parallel to eg/2 and e(3g−2)/2. Analogously, each of the other mirrors has two parallel edges. Hence all the vertices on the line-at-infinity are 4-fold and the line-at-infinity is omittable. On the other hand, if g is odd then none of the edges of C are parallel to any of the mirrors so that the line-at-infinity intersects the mirrors in ordinary points and the line-at-infinity is not omittable. Examples are shown in Figure 2, while the illustration at right in Figure 1 makes clear that the construction does not work for odd g. Figure 2: Examples of aggregates in which O(L) is a near-pencil; each aggregate includes the line-at-infinity, which is omittable. Shown are examples for g = 4, 6. For g ≥ 5 odd, one may remove one of the pencil lines from the near-pencil examples above to obtain aggregates L with O(L) a near-pencil and n(L) = 3g, which is not quite as L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 211 good as the n(L) = 3g − 2 obtained for even g. We do not know if the value n(L) = 3g is optimal for such odd g. For families of type 3 we have only the analog of the last part of Theorems 4 and 5: Theorem 6. For every g ≥ 4 there is a near-near-pencil O of g lines and an aggregate L such that O = O(L) and n(L) = 4g − 9. Proof. The examples needed to establish Theorem 6 can be described as follows. For a given g ≥ 4 we start with a regular (2g − 4)-gon. The aggregate L consists of the 2g − 4 lines determined by the sides of the polygon, and 2g − 5 of the mirrors of the polygon—that is, all mirrors except one that bisects a pair of opposite sides of the polygon. Then F = O(L) consists of the g − 2 mirrors that pass through the vertices of the polygon, together with the two lines determined by the sides that are bisected by the mirror that was not included in L. These families illustrate n(L) = 4g − 9. Examples are shown in Figure 3. Figure 3: Examples of aggregates covered by Theorem 6, for g = 4, 5, 6. Theorem 7. Sporadic familiesL are known for (g(L), n(L)) = (1, 5), (2, 7), (5, 13), (6, 14), (7, 19), (8, 20), (9, 21), (8, 32), (9, 33), (10, 34), (11, 35), (12, 36), (13, 37). Proof. Examples establishing this are shown in Figure 4. These sporadic aggregates are noteworthy because the sets O(L) are different from the ones covered by Theorems 4, 5 and 6. Several examples not explicitly illustrated can be derived by adding the line-at-infinity, or deleting one or several lines, as appropriate. 4 Bounds on the number of omittable and non-omittable lines As a preliminary observation, we note that the proof of Theorem 5, with k = g − 1, is easily seen to establish the following: Lemma 8. In an aggregate L whose omittable lines do not all form a pencil, but which contains k < g(L) omittable lines which do form a pencil, n(L) ≥ 3k + 1. At present we can establish what we consider to be relatively weak upper bounds on the maximum number of omittable lines relative to the total number of lines amongst all aggregates of a given size n = n(L). Since the expression is simpler, we actually express n in terms of the number of non-omittable lines. A line is non-omittable if its deletion removes vertices from the aggregate; that is, if it contains an ordinary vertex. Denote by N = N(L) 212 Ars Mathematica Contemporanea 1 (2008) 206–222 g = 1, n = 5 g = 2, n = 7 g = 5, n = 13 g = 6, n = 14 with the line-at-infinity (8,20) as shown (9,21) with the line-at-infinity (7, 19) without the middle vertical line (12, 36) as shown (12, 37) with the line-at-infinity Up to four of the middle omittable lines may be deleted Figure 4: Representative members of the sporadic family. The values of (g, n(L)) are shown near each. L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 213 g = # omittable lines n = # lines 10 20 30 40 50 60 70 5 10 15 20 25 Sporadic family O(L) is a pencil O(L) is a near-pencil O(L) is a near-near- pencil Pseudolines Figure 5: The explicitly known pairs (g, n(L)) of numbers of omittable lines and all lines in an aggregate. To avoid clutter, points corresponding to aggregates withO(L) a pencil that are to the left of (g, n) = (g, 3g) are not shown. Sporadic aggregates are indicated only in cases where no other examples are known. The four families and the aggregates of pseudolines are explained in the text. 214 Ars Mathematica Contemporanea 1 (2008) 206–222 the number of non-omittable lines in an aggregate L. For a given aggregate L, of course, g(L) +N(L) = n(L). Though they used somewhat different terminology, the following definition and lemmas are due to Kelly and Moser [16]. In what follows we consider not only the aggregate induced by a collection of lines (i.e., the lines together with the resulting vertices or 0D-cells), but the full arrangement (i.e. the lines plus all 0D, 1D and 2D-cells, where 1D cells are edges and 2D cells are faces). Definition 9. Say that an ordinary point p is attached to a line `, not containing p, if ` together with two lines crossing at p form a (possibly infinite) triangular cell of the induced arrangement. In this case, say that ` counts p as an attachment (or as an attached point). See Figure 6 for an illustration. p q Figure 6: An example of a line ` (the thick line) with two attached ordinary points. The point p is attached through the finite shaded triangle and the point q is attached through the shaded infinite triangle. Lemma 10 (Four Attachments Lemma). In any arrangement an ordinary point can have at most four lines counting it as an attachment. Proof. An ordinary point is contained in two crossing lines, and hence is a vertex of at most four faces. It can therefore be attached to at most four lines. Lemma 11. Let L be an aggregate such that all lines have at least three vertices. Then an omittable line must have at least three ordinary points attached to it. An aggregate having a line with only two vertices can have at most one omittable line—the line with the two vertices, so this case is not interesting to us. A simple proof of Lemma 11 can be found in [10, page 75]. Lemma 12. For a given number N of non-omittable lines, an aggregate L may contain no more than 23N(N − 1) omittable lines. Proof. Given N non-omittable lines, the maximum number of ordinary points is ( N 2 ) . By the Four Attachments Lemma (Lemma 10) there are at most 2N(N − 1) point-line attach- ments. By Lemma 11, an omittable line has at least three attachments, so there can be at most 2 3N(N − 1) omittable lines. L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 215 For a lower bound on the number of non-omittable lines we use the following well-known result of Csima and Sawyer [7]: Theorem 13. (Csima, Sawyer, 1993) Except for the single aggregate of 7 lines with 3 ordi- nary points (the left hand drawing in Figure 3), an aggregate of n lines must contain at least 6n/13 ordinary points. The following result is also remarked upon by Chen in [5]. Lemma 14. For any aggregate L, ( N 2 ) ≥ 6n 13 unless n = 7, in which case N ≥ 3. Proof. Ordinary vertices always come at the intersection of non-omittable lines. If t2 denotes the number of ordinary vertices then ( N 2 ) ≥ t2. The Theorem therefore follows by the Csima- Sawyer Theorem (Theorem 13). Writing n = N + g, Lemma 14 says that N(N − 1) 2 ≥ 6(N + g) 13 13N2 − 25N 12 ≥ g which is weaker than Lemma 12 for all N ≥ 4. 4.1 Chen’s bounds Chen [5] studied omittable lines in the dual (point-centric) setting. Restricting attention to non-collinear sets of points, he used the term “Gallai lines” for ordinary lines, and “Gallai point” for any point lying on one or more Gallai lines. In other words, Chen’s Gallai points are our non-omittable points. Chen’s work focused on computing the minimum value of the number N(L) of Gallai points for aggregates L of small cardinality n = n(L)1. He gave analytical arguments establishing the minimal values N∗() of N as a function of n = n(L) listed below. Thus N∗(n) is the minimum number of non-omittable lines in an aggregate of size n, and hence n − N∗(n) is the maximum number of omittable lines in aggregates of size n. The values of N∗(n) are consistent with the values in Figure 5, although N∗(6) and N∗(8) are not present in the graph. To see thatN∗(8) ≥ 2, add another solid (non-omittable) line through the central 3-crossing in the g = 2, n = 7 example in Figure 4 and to see that N∗(6) ≥ 1 add another solid line through either of the 3-crossings in the g = 1, n = 5 example in the same figure. n 3 4 5 6 7 8 9 N∗(n) 3 4 4 5 3 6 6 n−N∗(n) 0 0 1 1 4 2 3 1He also proved an interesting analog of the Sylvester-Gallai Theorem for finite metric spaces, originally conjec- tured upon by Chvátal. See [6] for the journal version. 216 Ars Mathematica Contemporanea 1 (2008) 206–222 Chen also developed a program to compute, for aggregates of pseudolines2, the values of Ñ∗(n) that correspond to N∗(n). His values, which we have not independently confirmed, are: n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Ñ∗(n) 3 4 4 5 3 6 6 6 6 6 7 8 9 8 n− Ñ∗(n) 0 0 1 1 4 2 3 4 5 6 6 6 6 8 By virtue of Theorem 5 (in particular the left-hand example in Figure 2), and the above computation for pseudolines, one can extend Chen’s first table to include N∗(10) = 6. Note that we do not have information about the exact examples establishing Ñ∗(12), Ñ∗(13) or Ñ∗(16) but at the least, if Chen’s program is correct, they would provide new pseudoline examples to be added to Figure 5. 4.2 Connection to magic arrangements Recently, Ackerman et al. [1] studied so-called “magic arrangements,” confirming a conjec- ture of Murty’s [19] that there are only four such arrangements. A magic arrangement (in our terminology, a magic aggregate) is a collection of lines, together with an assignment of positive weights to the lines (up to scaling by a common factor), such that if we sum the weights of lines intersecting at any vertex we get the same number. It is clearly sufficient to assume that all weights are strictly between zero and one and that the common sum at any vertex is one. Murty’s conjecture (confirmed by Ackerman et al.) was that there are just four magic arrangements: (i) a pencil in which all lines get weight 1n , (ii) a near-pencil in which all lines but the line not in the pencil get weight 1n−1 and the remaining line gets weight n−2 n−1 , (iii) the left hand arrangement Figure 3 in which all omittable lines get weight 14 and all non- omittable lines get wieght 12 , and finally (iv) any arrangement in general position in which all lines get weight 12 . It is not difficult to see that if there were an additional magic arrangement, it would have to consist of a set ofN non-omittable lines each with weight 12 and hence all in general position, plus at least N + 1 omittable lines. To verify the first part of this assertion, suppose we had a magic arrangement L with L not amongst the four families mentioned above, and with N non-omittable lines, but for which one of the non-omittable lines `, had weight 0 < w < 1 and w 6= 12 . By virtue of ` being non-omittable, there is a second (non-omittable) line k intersecting ` at an ordinary point. We may therefore suppose that wt(`) = 12 +  and wt(k) = 12 − . Since all lines intersect ` it follows that all lines but ` have weight strictly less than 12 . It follows that all ordinary points must lie on `. However, by Corollary 2 of [18] this is impossible unless L is a pencil or a near-pencil, which are amongst the four excluded classes. It follows that each non-omittable line in a hypothetical additional magic arrangement would necessarily have weight 12 and so the non-omittable lines must be in general position. To see that in addition to the N non-omittable lines there would have to be at least N + 1 omittable lines, consider the dual setting where we have first placed the N non-omittable points in general position—and furthermore, because each point has weight 12 , there can be no additional omittable point collinear with two of the non-omittables. Let us place the first 2An aggregate of pseudolines in the projective plane consists of family of lines that have been modified in a finite part in such a way that each is free of self-intersections and any two have just a single point in common, at which they cross each other. See [14], [10] or [11] for an introduction to this topic. For such aggregates the concept of omittable and non-omittable pseudolines can be defined without change. L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 217 omittable point p0. Since there can be no two non-omittable points collinear with p0, there are N distinct lines determined by p0 and each of the non-omittable points. Since p0 is omittable, each of these lines must contain an additional omittable point, for a total of at least N + 1 omittable points, as claimed. So we see that had there been an additional magic arrangement it would have implied an aggregate L with g(L)n(L) > 1 2 , in addition to the left hand aggregate in Figure 3, of which none are known. See also conjectures 16 and 17 in section 5. 4.3 O(L) in general position We have seen that the set of omittable lines can form a pencil (Theorem 4), a near-pencil (Theorem 5), and a near-near-pencil (Theorem 6), as well as a hand-full of sporadic other examples. We have shown that in any aggregate such that O(L) is a pencil or near-pencil, then, in contrast to Lemma 12, the number of omittable lines is at most a constant multiple kn of the number of total lines, for some k < 1. For pencils, as a consequence of Theorem 4, k = 13 , while for near-pencils, as a consequence of Theorem 5, k = 3 7 , or asymptotically, k = 13 . Let us now consider the other extreme, where O(L) is in general position. Note that the left-hand aggregate in Figure 3 is both an example where O(L) is a near-near-pencil, and so covered by Theorem 6, and an example where O(L) is in general position. We have the following: Lemma 15. For any aggregateL, whereL is not a pencil, and withO(L) in general position, g(L) n(L) ≤ 4 7 . Proof. Let L be an aggregate meeting the hypotheses of the lemma and let kn be the fraction of omittable lines for some k < 1. Consider the dual setting where we speak of omittable points rather than lines. There must be a non-omittable point collinear with each pair of omit- table points. Each non-omittable point can be collinear with at most bkn2 c pairs of omittable points. Thus we have kn 2 (1− k)n ≥ ( kn 2 ) (1) so that k(1− k)n2 ≥ kn(kn− 1) (2) n− 2kn+ 1 ≥ 0 (3) 2k − 1 ≤ 1 n . (4) Now note that there are no aggregates with n(L) ≤ 4 meeting the hypotheses of the Lemma. With n(L) ≥ 5, by the Csima-Sawyer Theorem (Theorem 13), there are at least three ordinary points, and as a result, at least three non-omittable lines. The cases where g(L) ≤ 3 are taken care of by Theorems 4 and 5, so we may assume that g(L) ≥ 4 and so n = n(L) ≥ 7. Thus, returning to equation (4), we have 2k − 1 ≤ 1 7 k ≤ 4 7 . 218 Ars Mathematica Contemporanea 1 (2008) 206–222 5 Comments (i) The term “aggregate” is introduced here for want of any word in the literature that de- scribes the family consisting of a set of lines and their points of intersection. The topic dis- cussed here is often framed as pertaining to arrangements of lines—but arrangements include the edges and faces determined by the set of lines, and these are not relevant in the present context, except for their brief mention in section 4. If a better term can be suggested, we would be happy to replace “aggregate,” which was the best we could come up with. It may be noted that in German the situation is even worse, since there is no accepted translation for “arrangement,” and the term “configuration” is used instead (see, for example, [2]) despite its well-known designation for a special class of families of points and lines. (ii) It is clear that projective transformations applied to any family L of lines apply the same transformations to the set O(L) of omittable lines. However, in many cases, the same pair (g(L), n(L)) occurs in projectively inequivalent aggregates, and even in aggregates that are not isomorphic. We say that two aggregates are isomorphic provided there is a one-to-one correspondence between their lines that preserves incidences, and separation among quadru- plets of collinear vertices. For example, the aggregate in Figure 7 is isomorphic to the aggre- gate in Figure 1, but is not projectively equivalent to it. (It should be noted that considered as arrangements these two examples are isomorphic—but we do not know whether this is true in general.) On the other hand, the aggregate with (g, n) = (12, 36) shown in the last part of Figure 4 is clearly not isomorphic with the example with the same (g, n) = (12, 36) constructed in the proof of Theorem 4. Figure 7: An aggregate with (g, n) = (3, 9) which is isomorphic with the first example in Figure 1, but not projectively equivalent to it. (iii) The upper bounds on n(L) in Theorems 4 and 5 seem excessive. While it may be very hard to find exact upper bounds, deciding whether the growth is exponential would seem interesting. (iv) The examples with (g, n) = (g, 3g) seem exceptional in several respects. To mention just two: An arbitrary number k ≤ g − 3 of the omittable lines may be deleted from the family while the remaining g − k lines remain omittable. In the opposite direction, there is no limit to the number of lines that can be added to the family while keeping those same g omittable lines. The illustration in Figure 8 is an example that admits many variations. (v) No examples of aggregates L are known for which O = O(L) is a near pencil with g(L) odd and n∗(O) = 3g− 2, the bound attained in Theorem 5 for even g. The best result known L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 219 Figure 8: An example of an aggregate with O(L) a pencil but n > 3g. is given by a family of aggregates such that g(L) is odd and n(L) = 4g + 1. We conjecture this is best possible. (vi) The four families described above reflect the character of the set O(L) of omittable lines in examples known at present: a pencil, a near-pencil, a near-near-pencil, and other possibilities. The small number of examples in the sporadic family hints at the difficulty of constructing aggregates with the set O(L) far from being a pencil. We propose: Conjecture 16. There are only finitely many sporadic families O(L). In fact, there probably are no such families with n > 37. (vii) Theorem 5 provides a counterexample to conjecture (A) of [21], that for g ≥ 6 all omittable points are collinear. However, no counterexample is known for Conjecture (E) of [21], which can be formulated as follows: Let M and N be sets of m ≥ 1 omittable and k ≥ 1 non-omittable lines, respectively, of any aggregate A(L), such that any intersection point of M ∈ M and N ∈ N belongs to no other line inM∪N . Then there are at least m+ k− 2 lines of L that do not belong toM∪N . Moreover, if either m = 1 or k = 1 then there are at least m+ k − 1 such lines. (viii) Theorem 6 provides a counterexample to Conjecture 2 of [15], which essentially as- serted that pencils and near-pencils are the only infinite families that can occur as O(L). The above Conjecture 16, if true, would imply that the sets O(L) of Theorems 4, 5, and 6 are the only infinite families. A related conjecture, close to Conjecture 1 of [15], is: Conjecture 17. lim sup n→∞ g n = 1 3 . (ix) Two problems arise in connection with the family 3 of near-near-pencils. One is whether the bound of Theorem 6 is a lower bound for all near-near-pencils; most likely this is true, but a proof seems elusive. The other question concerns the upper bound on n(L) in terms of g(L) for families of this kind—if such a bound exists at all. We conjecture that there is no bound, and that there are near-near-pencils with unbounded numbers of lines that do not coincide with O(L) for any aggregate L. (x) The various aggregates with relatively large g are either simplicial, or close to simplicial. (Here an aggregate is said to be simplicial provided the arrangement generated by its lines has only triangles as faces. Further details about simplicial aggregates can be found in [13] 220 Ars Mathematica Contemporanea 1 (2008) 206–222 Figure 9: An pseudoline aggregate of 18 pseudolines with 8 omittable pseudolines. Figure 10: A pseudoline aggregate of 36 pseudolines, with 16 omittable. L. W. Berman, B. Grünbaum and J. Lenchner: Omittable Lines 221 and [12].) This is the reason why the present paper deals with omittable lines instead of the omittable points considered in [15]. With simplicial arrangements it is frequently impossible to add or delete single lines without changing the character of the arrangement; somewhat analogous is the situation concerning aggregates with relatively large g. In most cases, the addition or deletion of a single line decreases g by more than one. (xi) For aggregates of pseudolines the definition and lemmas of Section 4 are still valid, so that the bounds obtained (Lemmas 12 and 14) still apply3. It is not surprising that with the consideration of pseudolines, new examples arise. Two interesting cases are shown in Figures 9 and 10. For these families (g, n) equals (8, 18) or (16, 36), respectively. This seems to indicate that one should not expect Conjecture 17 to be valid for aggregates of pseudolines. (xii) Many other directions of investigation of omittable lines are completely open. For exam- ple, how many lines (or pseudolines) can be omitted simultaneously? Is there a meaningful concept of omittable planes in 3-dimensional projective space? Acknowledgements. The authors are indebted to Professor William F. Smyth for a copy of the hard-to-find note [21], and to Tomaž Pisanski for helpful comments. The hospitality and resources of the Helen Riaboff Whiteley Center at the Friday Harbor Laboratories of the University of Washington, extended to Branko Grünbaum in the early stages of this work, are also gratefully acknowledged. References [1] E. Ackerman, K. Buchin, C. Knauer, R. Pinchasi and G. Rote, There are not too many magic con- figurations, Proceedings of the 23rd Annual Symposium on Computational Geometry (SCG’07), ACM, New York, NY, 2007, 449–458. [2] G. Barthel, F. Hirzebruch and T. Höfer, Geradenkonfigurationen und Algebraische Flächen. As- pects of Mathematics, D4, Friedr. Vieweg & Sohn, Braunschweig, 1987. [3] P. Borwein and W. Moser, A survey of Sylvester’s problem and its generalizations, Aequationes Mathematicae 40 (1990), 111–135. [4] P. Brass, W. Moser and J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005. [5] X. Chen, Some Problems in Discrete Geometry, Ph. D. Thesis, Rutgers University, 2006. [6] X. Chen, The Sylvester-Chvátal theorem, Discrete and Computational Geometry 35 (2006), 193– 199. [7] J. Csima and E. Sawyer, There exist 6n/13 ordinary points, Discrete and Computational Geom- etry 9 (1993), 187–202. [8] J. Csima and E. Sawyer, The 6n/13 theorem revisited, in: Y. Alavi and A. Schwenk (eds.), Graph Theory, Cobinatorics, and Applications 1, Wiley, 1995, 235–249. [9] P. Erdős and G. Purdy, Extremal problems in combinatorial geometry, in: R. G. et al. (eds.), Handbook of Combinatorics, Elsevier, 1995, 809–874. [10] S. Felsner, Geometric Graphs and Arrangements, Some chapters from combinatorial geometry, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, 2004. [11] J. E. Goodman, Pseudoline arrangements, in: J. E. Goodman and J. O’Rourke (eds.), Handbook of Discrete and Comutational Geometry, 2nd edition, Chapman & Hall/CRC, New York, 2004, 97–128. 3The Csima-Sawyer Theorem (Theorem 13) is likewise more generally true for pseudolines. 222 Ars Mathematica Contemporanea 1 (2008) 206–222 [12] B. Grünbaum, A catalog of simplicial arrangements in the plane: https://digital.lib.washington.edu/dspace/handle/1773/2269. [13] B. Grünbaum, Arrangements and hyperplanes, in: R. C. M. et al. (eds.), Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing 3, Louisiana State University, Baton Rouge, 1971, 41–106. [14] B. Grünbaum, Arrangements and Spreads, Number 10 in Conference Board of the Mathematical Sciences, Regional Conference Series in Mathematics. Amer. Math. Soc., Providence, RI, 1972. [15] B. Grünbaum, Omittable points, Geombinatorics 9 (1999), 57–62. [16] L. Kelly and W. Moser, On the number of ordinary lines determined by n points, Canadian Journal of Mathematics 10 (1958), 210–219. [17] K. Koutsky and V. Polák, Note on the omissable points in complete systems of points and straight lines in the plane (Czech, with Russian and English summaries), Časopis pro pestováni matem- atiky 85 (1960), 60–69. [18] J. Lenchner and H. Brönnimann, On the number of Euclidean ordinary points for lines in the plane, Geombinatorics 16 (2006), no. 1, 227–234. [19] U. S. R. Murty, How many magic configurations are there?, American Mathematical Monthly 78 (1971), 1000–1002. [20] N. Nilakantan, Extremal problems related to the Sylvester-Gallai theorem, in: J. P. J. E. Goodman and E. Welzl (eds.), Combinatorial and Computational Geometry, Cambridge University Press, 2005, 479–494. [21] W. F. Smyth, Sylvester configurations, James Cook Mathematical Notes 5 (1989), no. 49, 5193– 5196. [22] J. J. Sylvester, Mathematical question 11851, Educational Times, 59:98, 1893.