ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 165-186
Sparse line deletion constructions for symmetric 4-configurations
Leah Wrenn Berman
University of Alaska Fairbanks, 513 Ambler Lane, Fairbanks, AK 99775, USA
William H. Mitchell
University ofWisconsin - Madison, 480 Lincoln Dr., Madison, WI53706, USA
Received 15 April 2013, accepted 24 May 2014, published online 21 November 2014
A 4-configuration is a collection of points and lines in the Euclidean plane such that each point lies on four lines and each line passes through four points. In this paper we introduce a new family of these objects. Our construction generalizes a 2010 result of Berman and Grunbaum in which suitable 4-configurations from the well-understood celestial family are altered to yield new configurations with reduced geometric symmetry groups. The construction introduced in 2010 removes every other line of a symmetry class from the celestial configuration; here we we give conditions under which every p-th line can be removed, for p e {2, 3,4, • • • }. The geometric symmetry groups of the new configurations we obtain are of correspondingly smaller index as subgroups of the symmetry group of the underlying celestial configuration. These sparse constructions can also be repeated and combined to yield a rich variety of previously unknown 4-configurations. In particular, we can begin with a configuration with very high geometric symmetry—the dihedral symmetry of an m-gon for m quite large—and produce a configuration whose only geometric symmetry is 180° rotation.
Keywords: Configurations.
Math. Subj. Class.: 05B30, 51E30, 05C60
E-mail addresses: lwberman@alaska.edu (Leah Wrenn Berman), whmitchell@math.wisc.edu (William H. Mitchell)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
Abstract
166
Ars Math. Contemp. 9 (2015) 151-163
1 Introduction
An n-configuration is a set of n points and n lines with the property that each point lies on n lines and each line passes through n points. Configurations can be investigated as geometric objects or more generally as combinatorial objects where the lines are abstract sets of points. In this work we take the geometric perspective and consider points and lines in the Euclidean plane. Although such geometric objects were studied in the 19th century and several theorems on 3-configurations were proved, no illustration of a geometric 4-configuration appeared in print until much more recently, in [4]. Since then many more examples have been introduced. In this paper we give a technique that produces a large new class of 4-configurations, including 4-configurations with very few symmetries. We emphasize that by a symmetry of a configuration we mean an isometry of the plane which maps the configuration to itself, as opposed to the more general notion of combinatorial symmetry. The collection of symmetries of a configuration, or its symmetry group, partitions the points and lines into orbits, called the symmetry classes of points, and the symmetry classes of lines.
One frequently studied class of 4-configurations is the celestial family. Its members have the property that every point lies on exactly two lines from each of two symmetry classes of lines, and every line is incident with two points from each of two symmetry classes of points. Figure 2 gives an example of a celestial 4-configuration. The first published 4-configuration, in [4], was of this class, and more examples appeared in [6]. The first discussion of celestial configurations as a family appeared in a paper called Polycyclic Configurations by Marko Boben and Tomaz Pisanski [2], where they were investigated as a particular class of polycyclic 4-configurations. Branko Griinbaum's 2009 monograph Configurations of Points and Lines [3] gives a detailed analysis of the construction method and theory for celestial 4-configurations. In that reference Griinbaum refers to them as k-astral 4-configurations. However, he also uses the term "k-astral" to describe configurations which have k symmetry classes of points and k symmetry classes of lines; while celestial 4-configurations have this property, there are many other 4-configurations with this property that are not celestial. We reserve the term "k-astral" for the more general class of configurations with k symmetry classes of points and lines, and use the term "celestial" to refer to 4-configurations with the particular symmetry restrictions described above.
In [1], one author (LWB) developed two procedures which modify suitable celestial configurations to yield new 4-configurations. In the first of these, every other line from a particular symmetry class is deleted and then an equal number of new lines that pass through the center of the configuration—diameters—are added in such a way that the resulting structure is a (noncelestial) 4-configuration. The number of points and lines remains unchanged at the end of the construction since one diameter is added for every line removed. In the second procedure, particular elements of certain symmetry classes of points and of lines are both deleted and then diameters are added in such a way that every point is incident with four lines and every line is incident with four points, with a net loss of both points and lines.
In this paper we generalize the first of those procedures. We refer to this generalized procedure as sparse line deletion or p-sparse line deletion because in general it is possible to delete a smaller number of lines than in the old construction. The new configurations obtained in this way differ qualitatively from those introduced in [1] in that they exhibit a
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
167
wider variety of symmetry groups compared to the symmetries of the underlying celestial configurations. In particular, despite beginning with a configuration with a high degree of geometric symmetry, we can obtain configurations of quite low symmetry by repeating the sparse line deletion construction, in contrast to the previous construction. Figure 1 depicts three examples of these new objects; beginning with celestial configurations with d18, d12 and d16 symmetry, we develop configurations with d6, d4 and d4 symmetry, respectively.
The paper is organized as follows. In Section 2 we review the theory and notation for celestial configurations. We correct a minor notational ambiguity from [1] and give new results describing the incidences of the diameters in a series of lemmas. In Section 3 we describe the p-sparse line deletion construction. In Section 4 we show how the construction may be carried out several times simultaneously to yield a rich variety of new configurations. In Section 5 we give examples of configurations obtained by a related, but poorly understood technique applicable in the case where each symmetry class contains an odd number of objects. We close by mentioning several questions that deserve further study. All figures in this paper were generated using the free software Matplotlib [5].
2 Celestial configurations
A celestial configuration is a 4-configuration with a high degree of geometric symmetry; specifically, such a configuration has the property that every point is incident with exactly two lines from each of two symmetry classes, and every line is incident with exactly two points from each of two symmetry classes. If a celestial configuration has k symmetry classes of points and of lines, we refer to it as a k-celestial configuration. Each k-celestial configuration consists of a composite number mk of points and mk lines for some m. The points are the vertices of k concentric regular m-gons, and the configuration exhibits m-fold dihedral symmetry (that is, dm symmetry).
An example of a 3-celestial configuration is shown in Figure 2. In that figure, the three symmetry classes of points are distinguished by color (red, green and blue), and the three symmetry classes of lines are distinguished in the same way (also red, green, and blue). Each green line contains two red points and two green points (and similarly for the other two classes of lines), and each blue point lies on two red and two blue lines (and similarly for the other two classes of points).
Celestial configurations will serve as the building blocks of all of the new 4-configurations described in this paper. One useful feature of celestial configurations is the fact that every celestial configuration may be described by a configuration symbol
m#(si,ti; S2,t2; ■■ ■ ; sk,tk )
which encodes a geometric construction algorithm. The integers si; ti; m in the configuration symbol must satisfy several constraints for the construction to yield a 4-configuration; in this case we say the symbol is valid. The constraints are: m > 7, k > 2,1 < si,ti < m for all i, and
1. (order condition) adjacent entries in the sequence (s1,t1, s2, ■ ■ ■ ,tk) (taken cyclically) are distinct;
168
Ars Math. Contemp. 9 (2015) 151-163
(a) 18#(13*, 7; 8, 6); D*
(b) 12#(23*, 4; 1, 2; 4,1); D*,	(c) 16#(54*, 3; 4, 5; 3,4); D*,
Figure 1: Three new 4-configurations. (a), the 3-sparse line deletion 18#(13*, 7; 8,6); D*, with d6 symmetry. (b) the 3-sparse line deletion 12#(23*, 4; 1,2; 4,1); D*, with d4 symmetry. (c) the 4-sparse line deletion 16#(54*, 3; 4, 5; 3,4); D*, with d4 symmetry.
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...	169
("0)2
Figure 2: The 3-celestial configuration 8#(2,1; 3, 2; 1,3). The labeling updates Figure 2a in [1]. Throughout the paper we use red for v0 and L0, blue for v1 and L\, and green for v2 and L2.
2.	(even condition) J2¿=1 s +is even; and
3.(cosine	condition) nk=i cos (smn) = n^=icos (nm);
4.	(substring condition) the symbol m#(L) is invalid whenever L is a proper contiguous substring of (s1,t1; • • • ; sk,tk).
As an example illustrating contiguity, (3, 2; 1,4) and (4, 7; 5, 3) are contiguous substrings
of (5, 3; 2,1; 4, 7) but (5, 2; 4, 7) is not.
The cosine condition is satisfied automatically if the sets S = js1,...,sfc} and T = {t1,..., tk } are equal, in which case the configuration is called trivial. All the configurations in this paper, with the exception of those in Figures 1a and 3, are formed from trivial celestial configurations. More information on these conditions can be found in [3, Chapter 3].
We now turn to the construction algorithm encoded by the symbol.
2.1 Geometric construction algorithm (celestial configurations)
We write P V Q for the line passing through points P and Q and L A M for the intersection of lines L and M. In the symbols (vjj and (Ljj, the second index j is to be interpreted modulo m. The construction algorithm to produce a celestial configuration given a valid configuration symbol is as follows.
1. Begin with the vertices of aregular m-gon; e.g. take (v0)j = (cos (, sin (), for 0 < i < m. Let v0, written without a second subscript, denote the collection of these points.
170
Ars Math. Contemp. 9 (2015) 151-163
2.	Given points vj, define (Lj )i = (vj )i V (vj)j+sj+1, for 0 < i < m. We denote by Lj the collection of these lines.
3.	Given lines Lj, define (vj+i)j = (Lj)i A (Lj)i-tj, for 0 < i < m, and let vj+i denote the collection of these points.
4.	Repeat the previous two steps until the line class Lk-1 is obtained using the parameter sk. Stop before constructing the points vk; if the symbol is valid, the set of points vk that would be constructed in the next step would coincide setwise with the points
vo.
For future reference we list all of the incidences explicitly in Table 1.
Table 1: Incidences between members of point and line classes in the celestial configuration
m#(s1, t1;...; sk, tk). The quantity S is defined by S = \ J2i=1 s —1%.
Object
Incidences
(Lj)i, 0 < j < k — 1	(vj )i	(vj )i+Sj+1	(vj+1)i,	(vj+1 )i+tj + 1
(Lk-1 )i	(vk-1)i	(vk-1)i+Sj + i	(v0)i+5	(v0)i+S+tk
KOi	(L0)i	(L0)i-si	(Lk-1)i-s	(Lk-1)i-s-tk
(vj)i, 0 < j < k — 1	(Lj )i	(Lj)i sj+1	(Lj-1)i	(Lj-1)i-tj.
2.2 Lines through the origin
The vertices in a given point class vj of a celestial configuration form a regular m-gon. For each integer I it follows that the angle Z(vj)0O(vj)e is an integer multiple of 2n/m (that is, an even multiple of n/m). A slightly weaker statement holds for points in different symmetry classes: for i = j, it is still true that the angle Z(vi)0O(vj)e is an integer multiple of n/m. In the constructions we consider we will add lines through the center of the configuration (although the center is not one of the points of the configuration). We denote by Dj the line through the origin that makes an angle of j m radians with the line O V (v0)0 (conventionally a horizontal line) for j = 0,1, • • • , m — 1. For j > m or j < 0 we reduce modulo m so that Dm = D0 = O V (v0)0. This notation is more flexible than the concept of diametral type introduced in [1] and does not require m to be even. We refer to all of the Dj as diameters.
With this notation we restate some useful facts on celestial configurations.
1.	Suppose that m is even and (vj )j lies on Da. Then (vj)i+ m also lies on Da so that Da passes through two points of vj. However, if q is odd then Da+q passes through no points of vj. Hence if m is even, each diameter passes through either zero or two points from each symmetry class.
2.	Suppose that m is odd. Then each diameter is incident with exactly one point of each symmetry class.
3.	Let 0 < j < k — 1. If (vj)0 lies on Da then (vJ+1)0 lies on Da+Sj+i-t3+i.
By combining (1) and (3) we see that if m and (s1 +11) are even, then the even-numbered
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions.
171
diameters pass through two points from each of v0 and v\ while the odd-numbered diameters miss all of the points in v0 and v\.
We now give three lemmas providing specific information on the incidences of the diameters. This information is conveniently expressed in terms of the constants [Pj } defined by Po = 0 and
ßj	Sq - tq, j = 1, ••• ,k - 1.
q=l
Lemma 2.1. For all i and j, the point (vj )j lies on the diameter Dßj +2i.
Proof. By definition, (v0)o lies on D0. Applying (3) repeatedly we see that (vj)0 lies on diameter DßL. It follows that (vj)i lies on DßL+2i.	□
Lemma 2.2. For 0 < £ < m, and 0 < j < k, the diameter Dt> passes through the following points of vj :
none
(vj ) —L , (vj ) m+t-ßj 2 2
(vj ) m+t-ßj 2
(vj ) —L
m even, Pj — £ odd; m even, Pj — £ even;
m odd, Pj — £ odd;
m odd, Pj — £ even.
Proof. Lemma 2.1 states that for each i the point (vj )i lies on Dfj +2i, so it suffices to solve the congruence £ = Pj + 2i (m) for i. Equivalently we solve 2i = £ — Pj (m). If m is odd, this equation has one solution because 2 is a generator of the cyclic group Z/mZ. This solution depends on the parity of £ — Pj as indicated. If m is even then 2i and 2i — m
are always even, so there is no solution if £ — Pj is odd. If £ — Pj is even then both —.2f1
□
and m+2 ßj are solutions, as indicated.
Lemma 2.3. If 0 < j,£ < k and 0 < i < m, the points of vi sharing a diameter with (vj )i are
none
M
i +
ßj -
• (ve)i+ m+ßj -i+ 2
(vi).+ m + ßj -i+ 2
(vi).+ ßj -ßt
m even, Pi — Pj odd; m even, Pi — Pj even; m odd, Pi — Pj odd; m odd, Pi — Pj even.
Proof. Lemma 2.1 implies that (vj)i lies on Dßj +2i. Lemma 2.2 then states which points of vi lie on this diameter. Writing £ = ßj + 2i and j = £ to match the notation of Lemma 2.2, we find that the following points of v~- lie on D^:
none
(v~j ) l-ß - , (j m+1-ß -
(vi)
m+t — ß l
(vi)i—ß-
m even, Pj — £ odd; m even, Pj — £ even;
m odd, Pj — £ odd;
m odd, Pj — £ even.
2
2
2
2
172
Ars Math. Contemp. 9 (2015) 165-186
In other words, the following points of v£ lie on D@j+2i:
: , (V£) m + gj +2i-
none
(v£) +2i-2
(V£ ) m+gj + 2i-^ 2
(V£ ) gj + 2i-^
m even, fi^ - fij odd; m even, fi^ — fij even; m odd, fi^ — fij odd; m odd, fii — fij even.
The result follows.
□
2
2
3 Sparse line deletion
Consider the celestial configuration 18#(5,1; 4,6), illustrated in Figure 3a. Suppose we delete the lines (L0)k, k = 0, 3, 6,9,12,15; the resulting structure is not a configuration because some of the points, shown larger in Figure 3b, have lost an incidence. We say that these points have been affected by the line deletion. Note that the affected points of v0 lie on the same diameters as the affected points of vi, and each diameter that has any affected point incident with it in fact is incident with two points from each of the two symmetry classes. In addition, each affected point is missing precisely one line. Therefore, if we add the six diameters {D0, D4, D6, D10, D12, D16}, we obtain the 4-configuration depicted in Figure 3c. This is an example of the 3-sparse line deletion construction.
We call this construction sparse in comparison with the construction given in [1], because we remove only one-third of the lines L0 instead of one-half. Figure 4 shows the result of the construction technique described in [1], which was called odd deletion in that work and which corresponds to 2-sparse deletion in the terminology of the present work, beginning from the same celestial configuration 18#(5,1; 4,6). The example of Figure 4 also serves to correct an error from [1], where it was claimed incorrectly that the construction would work only for k-celestial configurations with k > 3.
The following theorem gives necessary conditions for the procedure described above to succeed, given parameters m, s^tj of the celestial configuration and a sparsity p. The proof shows that the affected points all lie on a particular set of diameters, and that all points on these diameters are affected. The case p = 2 was proven in [1].
Theorem 3.1 (p-Sparse Line Deletion). Let p > 2, and let C be a celestial 4-configuration with symbol m#(s1,t1; s2,t2; • • • ; sk ,tk) satisfying the following conditions:
(i)	p does not divide s^
(ii)	m is even, and either ?r = 0 (mod p) or ?r = s1 (mod p).
(iii)	The points lying on even-numbered diameters are precisely those of v0 and v1, i.e.:
If k = 2, then s1 +11 and s2 +12 are both even.
If k > 3, then sj + tj is odd for i = 2, i = k, and even otherwise.
(iv)	The following sets coincide when reduced modulo p:
s1 + t1 s1 — t1
{0,si} =
2
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
173
(b) 18#(53*, 1; 4, 6)	(c) 18#(53*, 1;4, 6); d*
Figure 3: The 3-sparse line deletion construction. (a) The celestial configuration 18#(5,1; 4, 6) with (L0)n drawn thicker for n = 0 mod 3. (b) Lines (L0)n for n = 0 mod 3 have been deleted and the points affected by the deletion are drawn larger. This structure is denoted 18#(53*, 1; 4,6) and is not a 4-configuration; the notation 53* is explained in Theorem 3.1. (c): The 4-configuration 18#(53*, 1; 4,6); D* obtained from (b) by adding diameters.
174	Ars Math. Contemp. 9 (2015) 165-186
Figure 4: The 2-sparse line deletion configuration 18#(52*, 1; 4,6); D*. All of the diameters have been added, so the other constructions considered in this paper are sparse in comparison. In the notation of [1] this would have been denoted 18#(5*, 1; 4,6); D.
Remove from C the lines (L0)np, 0 < n < y. Add the diameters passing through the affected points of v0, i.e. D2np, D2(np+si), for 0 < n < [ 2rp 1. Then the resulting structure C is again a 4-configuration, which we denote as m#(sp*, ti;...; sk, tk); D*.
Proof. We verify that each object in the new structure has exactly four incidences.
Each line (Lj)j of C that is not deleted still has exactly four incidences in C' since no points are added or deleted in this construction.
The added diameters also pass through exactly four points. To see this, note that by condition (iii) the classes v0 and vi and no others lie on even-numbered diameters. Condition (ii) implies that m is even, so each even-numbered diameter passes through two points from each of v0 and vi and no others.
Consider now the points (vj)j with j > 1. By condition (iii) these lie on odd-numbered diameters. They therefore do not gain any incidence from the added diameters, and they do not lose any incidence either since the deleted lines are chosen from L0 and these lines are incident only with points of v0 and vi (again by condition (iii)).
It remains only to show that each point of v0 and vi lies on exactly four lines after diameters are added.
We begin with the points v0. A point (v0)j lies on two lines of L0, namely (L0)j and (L0)i-si. Because si ^ 0 (mod p) by condition (i), at most one of these lines is deleted. Because we add a diameter if and only if it passes through an affected point of v0, the affected points regain their lost incidence and have exactly four incidences. Hence all points (v0)j have at least four incidences in C'.
We must still check that none of them have five, i.e., that no unaffected point of v0 lies
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
175
directly across the origin from an affected point of v0 on the same diameter. We therefore suppose that (v0)j is affected by the deletion, i.e. i = 0 (mod p) or i = s1 (mod p), and we show that its reflection (v0)i+ m across the origin is also affected. To do so, we must show that either i + y = 0 (mod p) or i + y = s1 (mod p). We consider the two cases of condition (ii). In the first case, where y = 0 (mod p) the desired congruence is immediate. In the second case we have y = s1 (mod p), so 2s1 = m = 0 (mod p). However, i + y is congruent to i + s1, since we are in the case where y = s1 (mod p), and this is now congruent to either s1 or 2s1 = 0 (mod p), according to whether i = 0 or i = s1. Hence all of the points v0 have exactly four incidences in the new structure C'.
Now consider the points of v1. We begin by showing that a point (v1)i can lose at most one incidence when the lines (L0)np, 0 < n < [mp], are deleted. Indeed, (v1)i lies on only two lines from the first line class, namely (L0)j and (L0)i-il. Thus, we need to show that t1 = 0 (mod p). This follows from condition (iv). If t1 were congruent to 0 (mod p), we would have sl_tl = sl_tl +11 = Sl+tl (mod p). These numbers cannot be congruent, however, since one is congruent to 0 and the other to s1. This shows that each point (v1)i will lose either zero or one incidence when the lines (L0)np are removed. It follows that each line deletion affects two points of v1 as well as two points of v0, so the same number of points are affected in each of these point classes.
Finally, we argue that the affected points of class v1 are precisely those that lie on the added diameters. Because v1 contains the same number of affected points as v0, it suffices to show that each affected point of class v1 lies on one of the diameters added previously. A counting argument then guarantees that no unaffected point lies on an added diameter. Since = s1 - t1 is even by condition (iii) and m is even by condition (ii), Lemma 2.3 implies that each point (v1)i shares a diameter with (v0)i+1(sl_tl). The affected points of v1 are those lying on (L0)q where q = 0 (mod p), namely (v1)q and (v1)q+tl. It therefore suffices to show that
if i = 0 or t1 (mod p), then i + 1(s1 — t1) = 0 or s1 (mod p),
since 0 and s1 are the remainders modulo p of the indices of affected points in v0. But this is equivalent to condition (iv). Hence the affected points of v1 lie on added diameters in C'. This completes the proof.	□
3.1 Notation
The notation of [1] may be extended to these generalized p-sparse constructions. If each p-th line of the class Lo has been deleted from the celestial configuration m#(si, ti;... ;
, ), we denote the resulting incidence structure by m#(sf*, ti;... ; sk, tk); it is not a configuration. The notation m#(si*,ii;... ; sk, tk) that was used in [1] should now be written as m#(s2*, ti;... ; sk, tk) since all of those constructions were 2-sparse.
We append the symbol D* to the end of the sequence to indicate that for 0 < i < m we add the diameter Dj if any of the points on Dj have been affected by the line deletion. For brevity we do not explicitly state the indices of the added diameters. These can be recovered if necessary: under the conditions of Theorem 3.1, the added diameters are Dj with j = 0 or j = si (modp). Hence if m#(si,ti;... ; sk,tk) is a celestial configuration,
176
Ars Math. Contemp. 9 (2015) 165-186
(a) 24#(24*, 10; 7, 2; 10, 7); d*	(b) 24#(26*\ 10; 7, 2; 10, 7); d*
Figure 5: The celestial symbol 24#(2,10; 7,2; 10, 7) satisfies the hypotheses of Theorem 3.1 for both p = 4 and p = 6, yielding two new configurations.
then m#( si , ti;...; sk ,tk) is an incidence structure formed by removing each p-th line in L0, and Theorem 3.1 asserts that m#(sf*,t1;...; sk,tk); D* is again a configuration under certain conditions on m, sj, ij, and p.
We will need more powerful notation in the next section. In our examples so far, we deleted the lines (L0)q for all q = 0 (mod p). The construction works equally well if we delete instead the lines (L0)q for all q = b (mod p), where 0 < b < p (to see this, rotate the configuration through an angle of -2nb/m radians, perform the same operation, then rotate back). If b = 0 we write b following the asterisk in the superscript of s1; for clarity we may also do this even if b = 0.
The construction outlined in Theorem 3.1 also works if instead of deleting every p-th line in class L0, we instead delete every p-th line in class Lj-1, provided the symbol satisfies the (suitably shifted) conditions of Theorem 3.1.
We therefore use the notation
m#(---;sP*b,tj;•••)
to indicate deletion of each line (Lj-_1)q, with q = b (mod p). See Figure 5b for an example with j = 0 and b =1.
The next section details a generalization of this deletion technique, in which several deletions on the same set of lines are performed simultaneously; to denote this, we write

#(••• ; sj	; ••• )
to indicate deletion of each line (Lj-1)q, with q = b1 or q = b2 or q = b3 (mod p).
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...	177
Figure 6: The constructions illustrated in Figure 5 have been carried out simultaneously to obtain 24#(24*0'6*1,10; 7,2; 10,7); D*. This procedure degrades the symmetry group from d24 to d2.
4 Repetition of sparse line deletion 4.1 Multiple deletions within the first line class
Consider the celestial configuration 24#(2,10; 7,2; 10,7). This symbol satisfies the conditions for Theorem 3.1 for both p = 4 and p = 6. We can delete the lines (L0)q for q = 0,4, 8, • • • and add diameters to obtain 24#(24*0,10; 7,2; 10,7); D*, depicted in Figure 5a. The affected points of v0 are those (v0)j with i = 0 or i = s1 = 2 (mod 4). This leaves all of the (v0)j with odd i untouched. On the other hand, if we delete all lines (L0)q with q = 1 (mod 6), only points (v0)j of odd index will be affected: see Figure 5b. We may therefore perform both constructions together to obtain the configuration 24#(24*0'6*1,10; 7, 2; 10, 7); D*, depicted in Figure 6. We have now added all but two of the even-numbered diameters, and the deletion is "sparse" only in comparison with the construction given in [1]. The resulting configuration has only the four symmetries of a rectangle, compared to the 48 symmetries of the underlying celestial configuration. That is, the new symmetry group has index 12 in the original group. For 2-sparse line deletion the index is at most 4. This indicates that the more general procedure can give qualitatively novel configurations.
Many celestial configurations admit p-sparse line deletions for several values of p. A naïve exhaustion search by machine using the conditions of the theorem uncovered several extreme examples. The celestial configuration 48#(13,11; 20,13; 11, 20) admits p-sparse line deletion with p = 2,3,4, 6 or 12. With 80#(12,28; 23,12; 28, 23) we can take p = 5, 8,10, or 20. By repeating and combining the p-sparse line deletions for some-
178
Ars Math. Contemp. 9 (2015) 165-186
what larger values of p, we can obtain a large number of new 4-configurations. Even in the relatively small case of 24#(2,10; 7, 2; 10,7) we can obtain the configurations illustrated in Figure 7 in addition to those from Figures 5 and 6.
4.2 Combining deletions in the first and third classes in 4-celestial configurations
Another possibility for repetition of the p-sparse line deletion construction arises in the special case of 4-celestial configurations. Suppose that the hypotheses of Theorem 3.1 hold for the celestial symbol
m#(si,ti; S2,t2; «3,^3; S4,t4) with p = p1. Suppose further that they hold for the symbol
m#(s3,t3; «4,¿4; «i,ti; «2,¿2)
withp = p2. Beginning from the first symbol m#(s1, t1; s2, t2; s3,t3; s4, t4), we may then perform p1-sparse deletion on the lines L0 and add even-numbered diameters to recover a configuration (as in Theorem 3.1). We may additionally perform p2-sparse deletion on the lines L2 and add odd-numbered diameters to recover yet another configuration of a family not available previously.
For example, the 4-celestial configuration 20#(6,4; 3,6; 7, 3; 4,7) admits a 5-sparse deletion on both L0 and L2. We can delete the lines (L0)q with q = 0 (mod 5) and add even-numbered diameters, or we can delete the lines (L2)q with q = 0 (mod 5) and add odd-numbered diameters to obtain a 4-configuration. We can also do both; in this case we arrive at the configuration 20#(65*, 4; 3, 6; 75*, 3; 4,7); D*, depicted in Figure 8b. By rotating the first construction we obtain 20#(65*1,4; 3,6; 75*0, 3; 4,7); D*, depicted in Figure 8c. These three objects are different, at least in the geometric sense that they differ by more than an isometry, illustrating the very large number of new configurations available through this method.
Finally we note the possibility of repeating deletions within L0 and also repeating deletions within L2. An example is 20#(65*0'2,4; 3,6; 75*0'4,3; 4,7); D*; see Figure 8a and note again the very small symmetry group.
5 Constructions with an odd number of points per symmetry class
Let C be a k-celestial configuration with symbol m#(s1, t1;...; sk, tk). Suppose that m is odd. The hypotheses of Theorem 3.1 cannot hold; in this section we ask if there is another way to remove some lines of C and then add an equal number of diameters to recover a 4-configuration. We will give some examples where this succeeds and suggest a classification of the resulting configurations. We leave open the task of giving explicit construction algorithms with sufficient conditions on m, s, t and p.
We claim that such a construction is possible only if k = 4. Indeed, since m is odd every diameter passes through exactly one point in each symmetry class; if the added diameters are lines in a 4-configuration then there must be exactly four classes.
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
179
(a) 24#(24*0'1,10; 7, 2; 10, 7); d*
(b) 24#(26*0,1, 10; 7, 2; 10, 7); d*	(c) 24#(26*°>3, 10; 7, 2; 10, 7); d*
Figure 7: Three more configurations arising from multiple modifications to the same celestial configuration as in Figures 5 and 6. Note that in the configuration shown in (a) we have deleted every red line (L0)q where q is congruent to 0 or 1 (mod 4). As a result all even-numbered diameters have been added, although this configuration cannot be constructed via 2-sparse line deletion.
180	Ars Math. Contemp. 9 (2015) 165-186
(a) 20#(6b*°>2, 4; 3, 6; 75*0'4, 3; 4, 7); d*
(b) 20#(65*, 4; 3, 6;75*, 3; 4, 7); d * .	(c) 20#(65*1,4; 3, 6;75*0, 3; 4, 7); d * .
Figure 8: Three configurations obtained from 20#(6,4; 3, 6; 7,3; 4,7) by performing 5-sparse deletion on both L0 and L2. Both odd- and even-numbered diameters have been added.
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
181
The examples in previous sections proceeded in steps where some of the lines in one symmetry class were removed and diameters were added to yield a new configuration; in the more complicated examples several intermediate configurations were formed and destroyed along the way. With m odd such a scheme cannot work. Because each added diameter passes through points in four symmetry classes, while the lines of any line class Lj pass only through the two point classes vj, vj+i, we must simultaneously delete lines from more than one symmetry class. The necessity of coordinating these different classes of removed lines is the main challenge in this section.
We propose the following classification for line deletion constructions. The ray from the origin through (v0)o passes through either zero points or one point from each of the classes v1, v2, v3. If this ray passes through a point of class vj we say that vj is a cis class; otherwise we say that vj is a trans class (that is, trans classes are on the opposite side of the origin from points v0, while cis classes are on the same side of the origin as points v0). Hence v0 is always a cis class, and our Theorem 3.1 addresses the case where m is even and the set of cis classes is {v0, v1}.
There are 23 = 8 possible sets of cis classes in a 4-celestial configuration. In Figures 9, 10, and 11 we give examples where m is odd and the cis classes are {v0, v1}, {v0, v1, v2, v3}, and {v0, v2, v3} respectively. It may be that for each of the eight possibilities one can find sufficient conditions for some line deletion procedure in the spirit of Theorem 3.1. This problem is beyond our scope here.
6 Questions for further study
In Configurations of Points and Lines, Griinbaum wrote that "constructing new 4-configura-tions is still more of an art than a science" [3]. We now offer several possible directions for future work towards the ultimate goal of finding and classifying all 4-configurations.
The technique we have explored here, the replacement of some lines of a celestial configuration with an equal number of diameters, can be extended further. The examples given in Section 5 should be systematized with explicit construction algorithms and sufficient conditions. There are also possibilites with m even that are not covered by Theorem 3.1. Figure 12 gives an example with m =12 where v0 and v2 are of cis type, in contrast to the situation of Theorem 3.1, where v0 and v1 are of cis type. This could be the first example of a new infinite family obtained by a more general construction.
We also have yet to consider the "even deletion" procedure introduced in [1], in which points as well as lines are removed. This no doubt has a p-sparse generalization and could be worth exploring since the "even deletion" construction in [1] yielded previously unknown (254) configurations.
We close by mentioning a related question. We say that two configurations are (combina-torially) isomorphic if there exists an incidence-preserving bijection between the two configurations. It is not clear how many of the configurations introduced here belong to new isomorphism classes in this combinatorial sense. For example, it is not known whether or not the configurations depicted in Figures 8b and 8c are combinatorially isomorphic. Even for the celestial configurations this question has not been solved.
182
Ars Math. Contemp. 9 (2015) 165-186
Figure 9: The configuration 15#(43*, 2; 1,4; 53*, 1; 2, 5); D*. The ray from the origin through (v0)0 (red) passes through (vi)_i (blue) but no points of v2 (green) or v3 (magenta), so the cis classes are v0 and v1.
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...	183
Figure 10: The configuration 27#(43*, 2; 8,4; 103*, 8; 2,10); D*. All four points on each added diameter lie on the same side of the origin, so all point classes are of cis type. The diameters could be extended through the origin without hitting other points because m is odd.
186	Ars Math. Contemp. 9 (2015) 165-186
Figure 11: The configuration 35#(125*, 13; 3,12; 75*, 3; 13, 7); D*. The cis classes are v0, v2, and
L. W. Berman and W. H. Mitchell: Sparse line deletion constructions...
76
Figure 12: The configuration 12#(23*0,5; 4, 3; 53*1,2; 3,4); D*. Here the cis classes are v0 and v2 .
77
Ars Math. Contemp. 9 (2015) 165-186
References
[1]	L. W. Berman and B. Grunbaum, Deletion constructions of symmetric 4-configurations. Part I, Contrib. Discrete Math. 5 (2010), 18-33.
[2]	M. Boben and T. Pisanski, Polycyclic configurations, European J. Combin. 24 (2003), 431-457, doi:10.1016/S0195-6698(03)00031-3.
[3]	B. Griinbaum, Configurations of Points and Lines, volume 103 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2009.
[4]	B. Grunbaum and J. F. Rigby, The real configuration (2I4), J. London Math. Soc. (2) 41 (1990), 336-346, doi:10.1112/jlms/s2-41.2.336.
[5]	J. D. Hunter, Matplotlib: A 2d graphics environment, Computing In Science & Engineering 9 (2007), 90-95.
[6]	D. Marusic and T. Pisanski, Weakly flag-transitive configurations and half-arc-transitive graphs, European J. Combin. 20 (1999), 559-570, doi:10.1006/eujc.1999.0302.