A family of n = n() distinct straight lines in the plane, not all through one point, determines an aggregate (). An aggregate is the geometric structure consisting of all the lines of together with all the vertices (), that is, intersections of two or more of the lines of . By “plane” we mean the real projective plane, which we envisage as modeled by the extended Euclidean plane. This is the ordinary Euclidean plane augmented by the points-at-infinity (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 of an aggregate () is said to be k-fold if it lies on precisely k lines of . 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˝os some fifty years later. Detailed references and proofs, as well as strengthenings and extensions, may be found, among others, in [3], [9], [4], [20], [7], [8].

We are interested in the following question: Given an aggregate (), are there any lines of that contain no ordinary vertices? Each line with this property is said to be an omittable line of , since its omission from does not decrease the number of vertices of the aggregate. We denote the totality of omittable lines of by O(L), and the number of lines in O() by g(). We are interested in the relations between g() and n(). In particular, we shall discuss various types of families of lines that can serve as O() for some . 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.

By: Leah Wrenn Berman; Branko Grunbaum; Jonathan Lenchner

Published in: RC24602 in 2008


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .