Arrangement of Lines - Triangles in Arrangements

Triangles in Arrangements

An arrangement of lines in the projective plane is said to be simplicial if every cell of the arrangement is bounded by exactly three edges; simplicial arrangements were first studied by Melchior. Three infinite families of simplicial line arrangements are known:

1. A near-pencil consisting of n − 1 lines through a single point, together with a single additional line that does not go through the same point,
2. The family of lines formed by the sides of a regular polygon together with its axes of symmetry, and
3. The sides and axes of symmetry of an even regular polygon, together with the line at infinity.

Additionally there are many other examples of sporadic simplicial arrangements that do not fit into any known infinite family. As Grünbaum writes, simplicial arrangements “appear as examples or counterexamples in many contexts of combinatorial geometry and its applications.” For instance, Artés, Grünbaum & Llibre (1998) use simplicial arrangements to construct counterexamples to a conjecture on the relation between the degree of a set of differential equations and the number of invariant lines the equations may have. The two known counterexamples to the Dirac-Motzkin conjecture (which states that any n-line arrangement has at least n/2 ordinary points) are both simplicial.

The dual graph of a line arrangement, in which there is one node per cell and one edge linking any pair of cells that share an edge of the arrangement, is a partial cube, a graph in which the nodes can be labeled by bitvectors in such a way that the graph distance equals the Hamming distance between labels; in the case of a line arrangement, each coordinate of the labeling assigns 0 to nodes on one side of one of the lines and 1 to nodes on the other side. Dual graphs of simplicial arrangements have been used to construct infinite families of 3-regular partial cubes, isomorphic to the graphs of simple zonohedra.

It is also of interest to study the extremal numbers of triangular cells in arrangements that may not necessarily be simplicial. In any arrangement, there must be at least n triangles; every arrangement that has only n triangles must be simple. The maximum possible number of triangles in a simple arrangement is known to be upper bounded by n(n − 1)/3 and lower bounded by n(n − 3)/3; the lower bound is achieved by certain subsets of the diagonals of a regular 2n-gon. For non-simple arrangements the maximum number of triangles is similar but more tightly bounded.