ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 291-322
One-point extensions in n3 configurations
William L. Kocay *
Computer Science Department and St. Paul's College, University of Manitoba, Winnipeg, Manitoba, R3T 2N2 Canada
Received 30 October 2014, accepted 18 December 2015, published online 30 January 2016
Given an n3 configuration, a 1-point extension is a technique that constructs an (n +1)3 configuration from it. It is proved that all (n + 1)3 configurations can be constructed from an n3 configuration using a 1-point extension, except for the Fano, Pappus, and Desargues configurations, and a family of Fano-type configurations. A 3-point extension is also described. A 3-point extension of the Fano configuration produces the Desargues and anti-Pappian configurations.
The significance of the 1-point extension is that it can frequently be used to construct real and/or rational coordinatizations in the plane of an (n + 1)3 configuration, whenever it is geometric, and the corresponding n3 configuration is also geometric.
Keywords: Fano configuration, Pappus, Desargues, (n, 3)-configuration. Math. Subj. Class.: 51E20, 51E30
1 Projective Configurations
A projective configuration consists of a set E of points and lines, and an incidence relation n, such that two lines intersect in at most one point. We denote this by (E, n). For example, a triangle with points A, B,C and lines a, b, c can be represented by the pair ({A, B, C, a, b, c}, {Ab, Ac, Ba, Bc, Ca, Cb}). A configuration (E, n) can also be viewed as a bipartite incidence graph of points versus lines. We will always assume that the incidence graph of a configuration is connected. Excellent references on configurations are the recent books by Griinbaum [7], and by Pisanski and Servatius [11].
An n3-configuration is a projective configuration with n points and n lines such that every line is incident on 3 points, and every point is incident on 3 lines. There is a unique 73-configuration, the Fano configuration, and a unique 83-configuration, the Mobius-Kantor
*This work is partially funded by a discovery grant from the Natural Sciences and Engineering Research Council of Canada.
E-mail address: bkocay@cs.umanitoba.ca (William L. Kocay)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
292
Ars Math. Contemp. 10 (2016) 255-268
configuration. In 1887, Martinetti [10] presented a method to construct the (n +1)3 configurations from the n3 configurations. This is described in [7, 6]. Boben [1, 2] has analysed and extended Martinetti's construction significantly. Important related work has also been done by Carstens, Dinskiand Steffen [4]. See also [12]. A recent paper [13] by Stokes studies extensions of configurations in a very general setting. The 1-point extension presented here can be related to Stokes's construction, but does not follow directly from it.
An n3 configuration which can be represented by a collection of points and straight lines in the real or rational plane, such that all incidences are respected, and no two points or two lines coincide, and no unwanted incidences occur, is termed a geometric n3 configuration. In order to show that an n3 configuration is geometric, the usual method is to assign suitable homogeneous coordinates to its points and lines. We call this a coordinatization of the configuration. Some n3 configurations are not geometric configurations, although it is currently an unsolved problem to determine which n3 configurations are geometric.
The purpose of this paper is to present a theorem, the 1-point extension theorem, which describes another method to construct an (n +1)3-configuration from an n3-configuration; and to characterize which configurations can be obtained in this way. The significance of this construction is that if the n3 configuration is geometric, with a given coordinatization, then there is usually a simple method to extend the coordinatization to the (n + 1)3 configuration, that is, the (n + 1) 3 configuration will also be geometeric. This is too long to include here, it will be the subject of another paper, currently in preparation [8]. In particular the following theorem is proved.
Theorem 1.1. Let (E, n) be an (n + 1)3-configuration. Then (E, n) can be constructed by a 1-point extension from an n3-configuration if and only if (E, n) is not one of the following configurations:
a)	the Fano configuration,
b)	the Pappus configuration,
c)	the Desargues configuration,
d)	a Fano-type configuration (to be described).
We begin with the idea of a 1-point extension in an n3-configuration.
Theorem 1.2. (1-Point Extension) Let (E, n) be an n3-configuration. Let a\,a2, a3 be 3 distinct points in E, and let t\,t2, ¿3 be 3 distinct lines in E such that a1 = ¿1 n ¿2, a2 = ¿2 n ¿3 and a3 G t3, where a3 G t\. We can represent this in tabular form as
(E,n) ¿1 ¿2 ¿3 ... ai ai a2 ■ ■ ■
■ a2 a3 •••
where the dots indicate other points of the configuration. Let ¿' be the third line containing a 1. Suppose further that if ¿' n ¿3 = 0, then ¿' n ¿3 = a3. Construct a new configuration (E', n') as follows. E' = E U ja0^0} where a0 is a new point and ¿0 is a new line.
n = n — ja^, a^2, a^3} U ja^3, a^0, a^0, a^0, a^, a^2}. We can represent this in tabular form as
W. L. Kocay: One-point extensions in n3 configurations
293
(E', n') 4
«2 ao <33 •
ao •
Here the dots represent exactly the same points as in the previous table. Then (E', n') is an (n + 1)3-configuration.
Proof. The only incidences in which (E', n') and (E,n) differ are those involving i0, i^ i2, i3. It is easy to verify from the tables that each of a1, a2 and a3 occurs in exactly 3 lines in both (E', n') and (E, n), and that a0 also occurs in exactly 3 lines. We must still verify that any two lines of (E', n') intersect in at most one point. Notice that i0 intersects and i2 in exactly one point, since a3 ^ ¿1, i2. Also, i0 intersects i3 in exactly one point. If i = ¿1, i2, i3 is any line of (E, n) intersecting ¿1, then in (E', n'), it intersects in either 0 or 1 point. If i intersects i2 in (E, n), then in (E', n'), it intersects i2 in either 0 or 1 point. If i = i', the third line of (E, n) containing a1, then in (E', n'), i intersects i3 in only a1, because of the condition concerning i'. If i = i' and i intersects i3 in (E, n), then then since a1 ^ i3 in (E, n), it follows that i intersects i3 in 0 or 1 point in (E', n'). Finally, if i is any line of (E, n) not intersecting i1, i2, then it does not intersect i1, i2 in (E', n'). If i does not intersect i3 in (E, n), it may intersect i3 in a1 in (E', n'). This completes the proof of the theorem.
□
Example 1.3. The Fano configuration can be represented by the following table.
Fano i1	i2	i3	i4	i5	i6	i7
1	2	3	4	5	6	7
2	3	4	5	6	7	1 4	5	6	7	1	2	3
Choose i1,i2,i3 as indicated, and choose a1 = 2, a2 = 3, a3 = 6, and let a0 = 8. Notice that the third line containing a1 is i' = i6, which intersects i3 in a3 = 6. Then by Theorem 1.2, the following table represents an 83-configuration, which is known to be unique.
83-config ¿0	¿1	¿2	¿3	¿4	¿5	¿6	¿7
3	1	2	2	4	5	6	7
6	4	5	3	5	6	7	1
8	8	8	4	7	1	2	3
The 83 -configuration can be viewed as a double cover of the cube [9]. It is possible to apply a 1-point extension to this configuration in two possible ways, resulting in two distinct 93-configurations. The third 93-configuration, known as the Pappus configuration, cannot be obtained in this way.
The 1-point extension theorem can be illustrated by the diagram of Figure 1. In (E, n), we have a substructure consisting of 3 points ai, a2, a3, and 3 lines, ¿1, ¿2,, sequentially incident, forming a self-dual substructure contained in the n3-configuration. After the extension, we find that (E', n') contains a triangle with vertices a1, a2, a0 and sides ¿2, ¿3,¿0, where the third point on ¿0 is a3, and the third line through a0 is ¿4. This is again a self-dual substructure in the configuration.
¿2 ¿3 ai ai ao a2
294
Ars Math. Contemp. 10 (2016) 255-268
Figure 1: A 1-point extension with 3 points
Corollary 1.4. In (E', n'), the third line through ai does not intersect £i; the third point on £3 is not collinear with a3; and the third line through a2 does not intersect £2.
Proof. If there were a line £ in (E', n') through ai which intersected £i in a point u, then in (E, n), £ would intersect £i in u and ai, which is impossible. If there were a point x in (E', n') on £3 collinear with a3, then the line £ containing a3 and x would also be a line in (E, n), where it would intersect £3 in two points. Finally, if there were a line £ in (E', n') through a2 which intersected £2 in a point u, then in (E, n), £ would intersect £2 in a2 and u, which is impossible.	□
The purpose of this paper is to characterize the configurations that can be obtained using 1-point extensions. In practice, the 1-point extensions are very easy to find and apply, and can easily be done by computer. However, the characterization of which configurations can be obtained by them is very long and tedious. We shall refer to the Fano, Pappus, and Desargues configurations, illustrated in Figure 1.1.
The conditions of Corollary 1.4 will be used frequently in the characterization. We state them here. We are concerned with an ordered triangle, denoted A(i, j, k), where i, j and k are the first, second, and third vertices, respectively, of the triangle. The line containing i and j is denoted ij, etc.
Definition 1.5. Let (E, n) be a configuration containing an ordered triangle A(i, j, k). We define the following 3 conditions:
A) The third line through k intersects ij ;
W. L. Kocay: One-point extensions in n3 configurations	295
B)	The third line through i intersects the third line through j;
C)	The third point on £ik is collinear with the third point on j. The definition is illustrated in Figure 3.
Figure 3: Conditions A, B and C for triangle A(i, j, k)
Theorem 1.6. Let (S', n' ) be an (n + l)3-configuration containing a triangle A. If conditions A, B and C do not apply to some ordering of the triangle, then (S', n') can be derived from an n3-configuration by a 1-point extension.
Proof. Let the ordered triangle to which conditions A, B and C do not apply be A(a0, a1, a2), and let the sides of the triangle be l0, £2,£3, where a0 = l0 n £2, ai = £2 n £3, a2 = £3 n l0. Let a3 be the third point on £0, and let £1 be the third line through a0. Observe that a3 ^ £1. These incidences are characterized by the following table.
(s, n) £0 £1 £2 £3 a2 a0 a1 a1 0,3 ■ a0 a,2
a0 ■ ■ ■
We can then delete a0 and £0, and change the incidences to the following.
(s', n') £1 £2 £3 a1 a1 a2 ■ a2 a3
Call the result (S', n'). If £ is the third line through a2 in (S, n), then since condition A does not apply, we know that in (S', n'), £ and £2 intersect in just one point. If £ is the third line through a1 in (S, n), then since condition B does not apply, we know that in (S', n'), £ and £1 intersect in just one point, a1. Since £ n £3 = a1 in (S, n), it follows that in (S', n'), if £ and £3 intersect, they intersect in a3.
If £ is any line other than £0 through a3 in (S, n), then since condition C does not apply, we know that in (S', n'), £ and £3 intersect in just one point. The result is an n3-configuration to which Theorem 1.2 applies.
□
296
Ars Math. Contemp. 10 (2016) 255-268
Given an ordered triangle A(i, j, k), the dual is an ordered triangle whose sides are lines which can be denoted i', j', k'. The dual of condition A is that the third point on k' is collinear with i' n j'. But this is just condition A again applied to the triangle A(i' n k', j' n k', i' n j'). So condition A is self-dual. The dual of condition B is that the third point on i' is collinear with the third point on j'. This is just condition C applied to the triangle A(i' n k', j' n k', i' n j'). So B and C are dual conditions.
Theorem 1.6 is the main tool which we will use to characterize the extensions. We will find all configurations such that at least one of conditions A, B, and C apply to every ordering of every triangle. We will also need longer cycles than triangles.
2 The General Extension Theorem
Before beginning the characterization of the n3-configurations that can be obtained by 1-point extensions, we generalize Theorem 1.2 to m points and m lines, sequentially incident.
Theorem2.1. (General 1-Point Extension) Let (E, n) be an n3-configuration. Let ai, a2,
..., am be m distinct points in E, where 3 < m < n, and let ¿^ ¿2,..., ¿m be m distinct lines in E such that ai = ¿1 n t2, a2 = ¿2 n ¿3, ..., am-i = n £m, and am G £m. Suppose that am-i, am G ¿^ ¿2, and that ai G ^i+3, where i =1, 2,..., m — 3. We can represent this in tabular form as
(e, n) ¿i	¿2	¿3 .	. . ¿m—1	¿ m
ai	ai	a2 .	. . am—2	am — 1
	a2	a3 .	. . am—1	am
where the dots indicate other points of the configuration. Let ¿j be the third line containing ai, where 1 < i < m — 2. Suppose further that if ¿j n ¿i+2 = 0, then ¿j n ¿i+2 = ai+2. Construct a new configuration (E', n') as follows. E' = E U {ao,¿o} where a0 is a new point and ¿0 is a new line. n' = n — {a1¿1, a2¿2,..., am¿m} U {a^3, a2¿4,..., am—am—, a^0, a0¿0, a0¿1, a0¿2}. We can represent this in tabular form as
(E', n')
¿0	¿i	¿2	¿3 .	. . ¿ • • ^m—1	¿ m
am—1	a0	a0	ai .	. . am—3	am—2
am		ai	a2 .	. . am —2	am— 1
a0					
Here the dots represent exactly the same points as in the previous table. Then (E', n') is an (n + 1)^-configuration.
Proof. The only incidences in which (E', n') and (E, n) differ are those involving ¿0, ¿1, ¿2,..., ¿m. It is easy to verify from the tables that each of a1, a2,..., am occurs in exactly 3 lines in both (E', n') and (E, n), and that a0 also occurs in exactly 3 lines. We must still verify that any two lines of (E', n') intersect in at most one point. Notice that ¿0 intersects ¿4 and ¿2 in exactly one point, since am-1, am G ¿4, ¿2. It does not intersect ¿3,..., ¿m-1, and it intersects in exactly one point.
Let I = ¿1, ¿2,..., be a line of (E, n). If I intersects in (E, n), then in (E', n'), it intersects in either 0 or 1 point. If I intersects ¿2 in (E, n), then in (E', n'), it intersects
W. L. Kocay: One-point extensions in n3 configurations
297
12	in either 0 or 1 point. Suppose that i intersects i3 in (E, n). If i = i^, then ini3 = a3 in (E, n) according to the condition of the theorem concerning ij. It follows that i n i3 = a1 in (E', n'). If i = i1, then i intersects i3 in either 0 or 1 point in (E', n'). An identical argument holds if i intersects one of i4,..., im in (E, n).
Suppose that i does not intersect i1 in (E, n). Then it also does not intersect i1 in (E', n'). Similarly, if i does not intersect i2 in (E, n), then it also does not intersect i2 in (E', n'). Suppose that i does not intersect i3 in (E, n). Then in (E', n'), it may intersect
13	only in a1. A similar argument holds if i does not intersect i4,..., im.
Finally, let i, and ij, where 1 < i < j < m, be two lines of (E, n). If j = i + 1, then ij and ij intersect in one point in both (E, n) and (E', n'). Suppose that j = i + 2. If ii n ij = 0 in (E, n), then it is also 0 in (E', n'). Now i n ij = ai-1 in (E, n) (when i > 1), because of the hypothesis that ak & ik+3. Also, i, n ij = a,, because ii+1 contains a, and ai+1. It follows that |i, n ij| is the same in (E, n) and (E', n') when j = i + 2. Suppose now that j > i + 3. It is easy to see that |i, n ij | < 1 in (E', n'). This completes the proof of the theorem.	□
Theorem 2.1 is illustrated in Figure 4, with m = 4. This general form of Theorem 2.1 is stated separately from Theorem 1.2, because the form with m = 3 is simpler, and because we shall mostly only require Theorems 1.2 and 1.6 when characterizing extensions.
Figure 4: A 1-point extension with 4 points
An ordered cycle in a configuration is a sequence of distinct points and lines which are cyclicly incident, for example C = (ai, ¿4, a2, ..., am, where a = £¿-1 n for i = 2,3,..., m, and a1 = £m n £1. Here m > 3. Each point of C is incident on two lines of C, and vice versa.
Corollary 2.2. Let (E, n) and (E', n') be as in Theorem 2.1, so that C = (a0, £2, a1, £3, . . . , am—2 , £m, 1, £0) is an ordered cycle in (E', n'). Then in (E', n'):
i)	the third points of £m and £0 are not collinear;
ii)	the third point on £j is not contained in the third line through a^, for i = 2,..., m — 1;
iii)	the third lines through a0 and a1 do not intersect.
298
Ars Math. Contemp. 10 (2016) 255-268
Proof. The third point of i0 is am. If there were a line i in (E', n') containing am and the third point of im, then in (E, n), i and im would intersect in two points, which is impossible.
Let i be the third line through aj in (E', n'), for some i = 2,..., m — 1, and let u be the third point on ij. Suppose that u G i. In (E', n'), aj is contained in ij+1 and ij+2, but in (E, n), aj is contained in ij and ij+1. We then find that in (E, n), i n ij = {u, a4}, which is impossible.
The third line through ao is ii . Let i be the third line through ai . If i n ii = u in (E', n'), then in (E, n), i n i1 = {u, a1}, which is impossible.	□
Observe that a triangle is a set of three distinct points and lines that are cyclically incident. Similarly, we define a quadrangle to be a set of four distinct points and lines that are cyclically incident. We will also need conditions similar to A, B, C for quadrangles. An ordered quadrangle with vertices i, j, k, m is denoted □ (i, j, k, m). In analogy with Definition 1.5 and Corollary 2.2, we make the following definition for a quadrangle.
Definition 2.3. Let (E, n) be a configuration containing an ordered quadrangle □ (i, j, k, m). We define the following 4 conditions:
D)	The third point on ijm is collinear with the third point on ikm;
E)	The third line through m intersects ijk;
F)	The third line through k intersects ijj;
G)	The third line through j intersects the third line through i. These conditions are illustrated in Figure 5.
D
Figure 5: Conditions D, E, F, G for quadrangle □ (i, j, k, m)
The analog of Theorem 1.6 for general 1-point extensions is the following.
Theorem 2.4. Let (E', n') be an (n + 1)^-configuration containing an ordered cycle C = (ao,^2, ai,4, «2, 4,..., «m-2,^m, flm-i,^o), where m > 4; ao, ai,..., am_i are distinct points; and	... ,^m-1 are distinct lines. Let denote the third
line containing a0 and let am denote the third point on t0. Suppose that is distinct from 4i, ^3,..., and that a2 ^ Let £i denote the third line containing ait for i = 1,2,..., m — 1. Suppose that £i does not not contain the third point of iit for i = 2,..., m — 1; that n = 0; and that am is not collinear with the third point of tm. Then (E', n') can be derived from an n3-configuration by a 1-point extension.
Proof. The incidences of the ordered cycle can be represented by the following table.
W. L. Kocay: One-point extensions in n3 configurations
299
(s, n) io
io	i1	i2	i3 .	. . im_ 1	i m
am_ 1	ao	ao	a1 .	. . am_3	am_2
am		a1	a2 .	. . am_2	am_ 1
ao					
We can then delete a0 and 4i, and change the incidences to the following.
(£', n') h
ai
i2	i3 .	. . im _ 1	i m
a1	a2 .	. . am_2	am_ 1
a2	a3 .	. . am_1	am
Call the result (S, n). It is clear that each point of (S, n) is contained in exactly three lines. We have to show that any two lines intersect in at most one point in (S, n), and that ¿4, i2,i3,..., im are distinct lines in (S, n). Any two of i^ i2,..., im intersect in at most one point because we began with an ordered cycle of distinct points, and because a2 ^ ¿1. Let i be any line not in this set. Suppose that i intersects ij in two points, for some i = 2,..., m — 1. Now ij contains ai_1, aj and a third point z. If i contained a^ then i = ij, which does not intersect ij in (S', n'), by assumption. Therefore aj ^ i. Otherwise i must contain aj_1 and z. But these points are in ij in (S', n'), and i is unchanged. It follows that i intersects i2,..., im-1 in at most one point each.
Suppose that i intersects i1 in two points in (S, n). Now i1 contains a1 and two other points u, v. As u and v are both on i1 in (S', n'), it follows that i does not contain both u and v. Therefore i = ii. But by assumption, ii n i1 = 0 in (S', n').
Suppose that i intersects im in two points in (S, n). The two points cannot be am-1, am, because these points occur on iQ in (S', n'). They cannot be am-1 and a third point w, because these points occur on im in (S', n'). And they cannot be am and the third point w, because by assumption, am is not collinear with the third point of im in (S', n'). We conclude that (S, n) is an n3-configuration to which the conditions of Theorem 2.1 apply.	□
Corollary 2.5. Let (S', n') be an (n+1)3-configuration containing a quadrangle D(i, j, k, m). If conditions D, E, F and G do not apply to some ordering of the quadrangle, and if the third line through i does not contain k, then (S', n') can be derived from an n3-configuration by a 1-point extension.
Proof. The conditions D, E, F, G, and a2 = k ^ i1 are the conditions of Theorem 2.4 applied to an ordered quadrangle.	□
Theorem 2.6. Let (S', n') be an (n + 1)^-configuration. If (S', n') does not contain a triangle, then it can be derived by a 1-point extension from an n3-configuration.
Proof. Choose a cycle of smallest possible length in (S', n'). Denote the cycle by
(ao, i2, a1, i3, a2, i4,. .. , am_2, im, am_ 1, io),
where m > 4. Let i1 be the third line containing aQ, and let am be the third point on iQ. This can be denoted in tabular from by
300
Ars Math. Contemp. 10 (2016) 255-268
(s, n) ¿q ¿i
Om-1 aQ
am	*
aQ	•
Let ¿i denote the third line containing ai, where i = 1, 2,..., m — 1. If ¿i were to intersect ¿i in a point z, where i = 2,..., m — 1, this would create a triangle A(ai-1, ai, z). If ¿1 were to intersect ¿1 in a point u, this would create a triangle A(aQ, a1, u). If am were collinear with the third point w of ¿m, this would create a triangle A(am-1, am, w). If ¿1 contained a2, this would create a triangle A(aQ, a1, a2). It follows that the conditions of Theorem 2.4 apply, so that (S', n') can be derived by a 1-point extension from an n3-configuration.	□
3 Fano-Type Configurations
Let F denote the Fano configuration, the unique 73 configuration. We will use three subconfigurations to build a family of n3 configurations which cannot be obtained by 1-point extensions.
Definition 3.1. Denote by F' the unique configuration obtained from F by removing a single incidence. Denote by Fi the unique configuration obtained from F by removing a line. Denote by Fp the unique configuration obtained from F by removing a point. Note that Fi and Fp are dual configurations.
¿2 ¿3 aQ ai a1 a2
. . ¿
m- 1 ¿m am-3 am-2 am - 2 am -1
Figure 6: The configurations Fi, Fp and F'
The configurations Fe, Fp and F' are not n3-configurations. They can be used as building blocks of n3 configurations, which we call Fano-type configurations. F' has one point on only two lines, and one line containing only two points. Fp has three lines containing only two points. Every point is in three lines. Fe has three points in only two lines. Every line contains three points. These are illustrated schematically in Figure 7, where the points missing a line are indicated as black circles, and the lines missing a point are indicated as lines.
These sub-configurations can be used as modules, which can be connected together like vertices of a graph, to create graphs representing n3 configurations. For example, two or more copies of F' can be connected into a cycle or path of arbitrary length. If only Fe and Fp are used, the resulting structure is a bipartite graph.
W. L. Kocay: One-point extensions in n3 configurations
301
Theorem 3.2. Let G be a multigraph which is isomorphic to either a cycle of length > 2, or a subdivision of a 3-regular bipartite multigraph, with bipartition (X, Y ). Replace each vertex of X by a configuration Fp, replace each vertex of Y by a configuration Fi, and replace each vertex of degree two by a configuration F '. The result is an n3 configuration which can not be obtained by a 1-point extension.
Proof. Refer to Figure 8, showing a cycle of length four, and a configuration constructed from the unique 3-regular bipartite multigraph on four vertices.
Figure 8: Configurations constructed from F', Fi and Fp
We must show that the n3 configurations constructed like this cannot be obtained by a 1-point extension. Observe first that the Fano configuration F is a projective plane, so that every two points are contained in a line, and every two lines intersect in a point. Consequently, every triangle contained in F', Fi or Fp has an ordering which satisfies one of conditions A, B or C .By Corollary 1.4, a Fano-type configuration cannot be obtained by a triangular 1-point extension (Theorem 1.2). Suppose that it can be obtained by a general 1-point extension (Theorem 2.1). By Corollary 2.2, there must be an ordered cycle C of length > 4 satisfying certain conditions. Let C = (a0, i2,a\,i3,..., am-2,lm, am-l, £0) be as in Corollary 2.2, and let £i denote the third line containing a4, where i = 1,2,... ,m-1. Let l\ denote the third line containing a0, and let am denote the third point on l0. If C were contained within an F', Fi or Fp, then C would have length 4, because any 5 points of F necessarily contain three collinear points. But in F', Fi or Fp, every ordered quadrangle satisfies at least one of conditions D, E, F, G, since the Fano configuration is a projective plane.
It follows that C is not contained within an F', Fi or Fp. Consider the portion of C contained within some F', Fi or Fp. It is a sequence of sequentially incident points and lines. Suppose first that it is contained within an F'. Referring to Figure 6 we see that the
302
Ars Math. Contemp. 10 (2016) 255-268
shortest possible portion of C contained within an F' is (ai; ¿i+2, ai+1, ¿i+3, ai+2, ¿¿+4), for some i = 0,1,..., m - 1 where subscripts are reduced modulo m. If ai+2 = a0, a1, then ¿¿+2 contains the third point of ¿i+2, which is in F'. If ai+2 = a0, then ai+1 = am-1 and ¿i+2 = ¿m, so that am is collinear in F' with the third point of ¿m. If ai+2 = a1, then ai+1 = a0, so that ¿1 and ¿1 are in F' and ¿1 n ¿1 = 0. Thus, the conditions of Corollary 2.2 are never satisfied if a portion of C is contained within an F'.
Suppose next that a portion of C is contained within an F^. Referring to Figure 6 we see that the shortest possible portion of C contained within an Fe is (^¿i+2, ai+1^i+3, ai+2), for some i = 0,1,...,m - 1 where subscripts are reduced modulo m. If ai+2 = a0, a1, then ¿¿+2 contains the third point of ¿i+2, which is in F^. If ai+2 = a0, then ai+1 = am-1 and ¿i+2 = ¿m, so that am is collinear in Fe with the third point of ¿m. If ai+2 = a1, then ai+1 = a0, so that ¿1 and ¿1 are in Fe and ¿1 n ¿1 = 0. Thus, the conditions of Corollary 2.2 are never satisfied if a portion of C is contained within an F^. A similar result holds for Fp, which is the dual of F^. We conclude that the Fano-type configurations can not be obtained by a 1-point extension.	□
4 The Characterization Theorem
In this section we will assume that (£, n) is an n3-configuration which cannot be derived by a 1-point extension. It follows from Theorem 2.6 that we can assume that (£, n) has a triangle. Let the points of (£, n) be numbered 1,2,..., n. Without loss of generality, we can assume that A(2, 3,1) is a triangle in (£, n). This is illustrated in Figure 9. It will be convenient to omit the commas and brackets from expressions like A(2,3,1), and write simply A231.
We divide the analysis into two cases according to whether or not (£, n) has a triangle satisfying condition A. The theorem obtained will be the following.
Theorem 4.1. If (£, n) is an n3-configuration which cannot be obtained from a 1-point extension, then either:
i)	(£, n) is one of the Fano, Pappus, or Desargues configurations; or
ii)	(£, n) is a Fano-type configuration.
Proof. The proof of this theorem is very long, involving an analysis of many possible cases. Case A. (£, n) has a triangle satisfying condition A.
W. L. Kocay: One-point extensions in n3 configurations
303
Let the ordered triangle be A231, as above. Condition A tells us that the third line through 1 intersects ^23. Call the point of intersection 4. This is shown in Figure 9. We will show that any n3 configuration that cannot be obtained by a 1-point extension, and which satisfies Condition A, is either a Fano-type configuration, or the Fano configuration. Now consider A142. It currently does not satisfy conditions A, B, or C. Since every triangle must satisfy at least one of these conditions, there are three possibilities, which we indicate by A142A, A142B, and A142C. These are shown in Figure 10. In A142A, the third line through 4 intersects £12 (in point 5). In A142B, the third lines through 1 and 4 intersect (in point 5). In A142C, the third points on ii2 (point 5) and t24 (point 3) are collinear.
These three structures are easily seen to be isomorphic, by relabelling the points. Each structure is self-dual, having two points incident on 3 lines each, and two lines each containing 3 points. Thus, without loss of generality, we can assume that the subconfiguration A142A exists in (£, n) in Case A. Consider triangle A124. It currently does not satisfy condition A, B, or C. Since it must satisfy at least one of these conditions, there are three possibilities, which we indicate by A142AA124A, A142AA124B, and A142AA124C. These are shown in Figure 11.
The structures A142AA124B and A142AA124C are duals of each other. The first has 6 points and 5 lines, while the other has 5 points and 6 lines. It can be verified by exhaustion that every ordered triangle in these structures satisfies at least one of conditions A, B, or C.
Case A142AA124A.
Consider the quadrangle D6431 in A142AA124A. It must satisfy at least one of
304
Ars Math. Contemp. 10 (2016) 255-268
conditions D, E, F, G (see Figure 5). Condition D is possible only if ¿25 intersects ¿43. Condition E is not possible. Condition F is possible only if the third line through 3 intersects ¿46. Condition G is possible only if there is a line ¿56. These cases are illustrated in Figure 12.
Figure 12: A142AA124AD6431D, A142AA124AD6431F, A142AA124AD6431G
Now the diagrams A142AA124AD6431D and A142AA124AD6431G are duals of each other, for the mapping which sends points 1,2,3,4, 5,6,7 of D to ¿15,¿16, ¿25, ¿24, ¿46, ¿13, ¿56 of G is an isomorphism. Therefore we need only consider cases D and F.
Case A142AA124AD6431D.
It can be verified that all triangles of the diagram satisfy one of conditions A, B, C. Consider the quadrangle D3164. Condition D is only possible if point 7 lies on line ¿46. Condition E is not possible. Condition F is only possible if there is a line ¿67. Condition G is only possible if there is a line ¿35. These cases are illustrated in Figure 13.
Figure 13: A142AA124AD6431DD3164D, F, and G
Case A142AA124AD6431DD3164D.
It can be verified that every triangle satisfies at least one of conditions A, B, C, and every quadrangle satisfies at least one of conditions D, E, F, G. This configuration is isomorphic to the Fano configuration, with one line removed (¿356), which we denote as F^. The dual configuration is the Fano configuration, with one point removed, which we denote as Fp.
Case A142AA124AD6431DD3164F.
Consider the quadrangle D2376. Condition D requires that ¿15 intersects ¿67, which
W. L. Kocay: One-point extensions in n3 configurations
305
is impossible. Condition E requires that ¿46 contains point 1, which is impossible. Condition F requires that ¿75 contains point 4, which is impossible. Condition G requires a line ¿35. The result is illustrated in Figure 14.
\7 /	(l \6/
	2
	
Figure 14: Case A142AA124AD6431DD3164FD2376G
We then consider quadrangle 06237. Condition D requires that ¿45 intersects ¿67, which is impossible. Condition E requires that ¿75 contains point 4, which is impossible. Condition F requires that ¿35 contains point 1, which is impossible. Condition G requires that ¿46 and ¿25 intersect in point 5, which is impossible. We conclude that case A142AA124AD6431DD3164F is not possible.
Case A142AA124AD6431DD3164G.
Consider the quadrangle 104316. Condition D requires that ¿25 intersects ¿46. The point of intersection can only be 7. Condition E requires that ¿75 contains point 6, which is impossible. Condition F requires that ¿15 contains point 2, which is impossible. Condition G requires a line ¿356. These cases are illustrated in Figure 15.
Figure 15: Cases A142AA124AD6431DD3164GD4316D and G
These two configurations are easily seen to be isomorphic, by the permutation of the points given by (2, 3,4)(5,6, 7), mapping D onto G. They are both isomorphic to the Fano configuration, with one incidence removed, denoted by F'. Every triangle satisfies at least one of conditions A, B, C, and every quadrangle satisfies at least one of conditions D, E, F, G.
306
Ars Math. Contemp. 10 (2016) 255-268
Note that we can complete F' to the Fano configuration, which can not be constructed by a 1-point extension.
We summarise Case A as follows:
Consider an n3 configuration (E, n), where n > 7, which cannot be constructed by a 1-point extension. Every triangle satisfying condition A is contained in a unique sub-configuration isomorphic to one of Fg, Fp or F'.
Case B. (E, n) has no triangle satisfying condition A.
We begin with triangle A231. It must satisfy condition B or C. These two possibilities are shown in Figure 16.
Figure 16: A231B and A231C
These two structures are duals of each other. Hence we can assume without loss of generality that (E, n) contains the structure A231B.
Consider the triangle A123. It must satisfy condition B or C. We must take these as two separate cases, Case BA123B and Case BA123C. They are shown in Figure 17. It will be necessary to examine a great many subcases.
Figure 17: Cases BA123B and BA123C
Case BA123B.
Consider triangle A132. There are two possibilities, cases BA123BA132B and BA123BA132C, which must both be considered. They are shown in Figure 18.
Case BA123BA132B.
Consider triangle A243. There are two choices BA123BA132BA243B and
W. L. Kocay: One-point extensions in n3 configurations
307
Figure 18: Cases BA123BA132B and BA123BA132C
BA123BA132BA243C. They are shown in Figure 19. These structures both have 7 points {1, 2,..., 7}, so that a mapping from the first to the second can be denoted by a permutation. It is easy to see that the permutation (1,2, 3)(4, 6,5)(7) maps the first to the second. Thus, without loss of generality, we can suppose that (E, n) contains the structure BA123BA132BA243B.
Figure 19: Isomorphic cases BA123BA132BA243 B and C
Consider triangle A342. There are two possibilities, BA123BA132BA243B A342B and BA123BA132BA243BA342C. They are shown in Figure 20. We must consider both possibilities.
Figure 20: Cases BA123BA132BA243BA342B and BA123BA132BA243BA342C
This is beginning to look remarkably like the Pappus configuration.
Case BA123BA132BA243BA342B.
Consider the quadrangle D1248. At least one of conditions D, E, F, G must be satisfied. Of these, it is only possible to satisfy condition E, namely the third line
308
Ars Math. Contemp. 10 (2016) 255-268
through 8 must intersect ¿24. The point of intersection can only be 5. Therefore the left diagram of Figure 21 must exist in (£, n).
Figure 21: Cases BD1248E and BD1248ED7238E
Consider the quadrangle D7238. At least one of conditions D, E, F, G must be satisfied. Of these, it is only possible to satisfy condition E, namely the third line through 8 must intersect ¿23. Therefore the right diagram of Figure 21 must exist in
(£, n).
Consider the quadrangle D3159. It is only possible to satisfy condition E, namely the third line through 9 must intersect ¿15 in point 6. Therefore the following structure (Figure 22) must exist in (£, n).
Figure 22: Case BD1248ED7238ED3159E
Consider the quadrangle D1347. It is only possible to satisfy condition E, namely the third line through 7 must intersect ¿34. The point of intersection must be 6, so that point 7 is incident with ¿69. Therefore the diagram is completed to a 93-configuration, so that (£, n) can only be the Pappus configuration.
Case BA123BA132BA243BA342C.
This case is illustrated in Figure 20. Consider the triangle A274. There are two possibilities, A274B and A274C, shown in Figure 23. These are duals of each other. The mapping which sends the points 1,2,..., 8 of A274B to the lines i15,i25,i34, ¿32, ¿12, ¿13, ¿58, ¿47 of A274C is an isomorphism. Hence we only need to consider one of them, the first, say.
Consider the quadrangle D1783. It is only possible to satisfy condition E, namely the third line through 3 must intersect ¿78. The point of intersection must be 6, so that ¿78 must be extended to include point 6. Consider next quadrangle D1745. It is
W. L. Kocay: One-point extensions in n3 configurations
309
Figure 23: Case BA123BA132BA243BA342CA274, B and C
only possible to satisfy condition E, namely the third line through 5 must intersect ¿47. The result is illustrated in Figure 24.
\/l
Figure 24: Case BA123BA132BA243BA342CA274BD1783D1745
Finally, consider quadrangle D7138. It is only possible to satisfy condition E, namely the third line through 8 must intersect i13. The point of intersection must be 9, so that i13 must be extended to include point 9. Once again we have the Pappus configuration.
Case BA123BA132C.
This case is illustrated in Figure 18. Consider the triangle A267. There are two possible ways to satisfy condition B, namely the third line through 6 could contain either 4 or 5. The first of these choices is illustrated in Figure 25. The second is not allowed, as it would create a triangle A125 satisfying condition A. There are two possible ways to satisfy condition C, namely i67 could intersect i13 or i34. Call these two results C1 and C2, respectively, also shown in Figure 25.
Case BA123BA132CA267B.
Consider the quadrangle D1673. It is not possible to satisfy conditions D or F. Condition E can only be satisfied if i34 intersects i67. Condition G can only be satisfied if i15 intersects i46. These cases are shown in Figure 26.
Now case G (the right diagram) leads to a contradiction, for consider the quadrangle □3167. Conditions E, F, G are not possible. Condition D is only possible if 5 G i67. But this creates a triangle A156 satisfying condition A, a contradiction. Therefore we consider case E (the left diagram). Consider the quadrangle ^3761. Conditions D, F, G cannot be satisfied. Condition E can only be satisfied if i15 intersects i67 in point 8, as shown in Figure 27. Consider next the quadrangle ^6137. Conditions
310	Ars Math. Contemp. 10 (2016) 255-268
Figure 25: Cases BA123BA132CA267 B, Cu and C2
Figure 26: Cases BA123BA132CA267BD1673 E and G
D, F,G cannot be satisfied. Condition E can only be satisfied if the third line through 7 intersects l\3 in a point 9, also illustrated in Figure 27.
Figure 27: Cases ED1673E and ED1673ED6137E
Consider now the quadrangle 02685 in the right diagram of Figure 27. Conditions D, F, G cannot be satisfied. Condition E can only be satisfied if the third line through 5 contains point 7, which is only possible if 5 G £rg. The result is isomorphic to the diagram of Figure 24. Once again, we obtain the Pappus configuration.
Case BA123BA132CA267Ci.
Refer to Figure 25. Consider the quadrangle 02784. Conditions D and F cannot be satisfied. Condition E can only be satisfied if there is a line l46, which gives a result identical to the left diagram of Figure 26. Condition G can only be satisfied if the third line through 7 intersects ^26 in point 1, but this creates a triangle A127
W. L. Kocay: One-point extensions in n3 configurations
311
satisfying condition A, which is not allowed. This completes this case.
Case BA123BA132CA267C2.
Refer to Figure 25. Consider the quadrangle 01376. Conditions D, E, F are not possible. Condition G is only possible if ¿15 and ¿34 intersect, shown in Figure 28. Consider now the quadrangle 01872. Conditions D, E, F are not possible. Condition G is possible if ¿15 intersects the third line through 8. The point of intersection can be either 5 or 9, resulting in G1 and G2, also shown in Figure 28.
Figure 28: Cases C201376G, G01872G1 and G01872G2
Consider the quadrangle 07218 in diagram G01872G1. Conditions D, E, F cannot be satisfied. Condition G can only be satisfied if the third line through 7 intersects ¿24. The point of intersection can be 4 or 5. But 4 creates a triangle A734 satisfying condition A, a contradiction. Therefore the intersection must be point 5, as shown in Figure 29. Then consider quadrangle 07812. Conditions D, E, F cannot be satisfied. Condition G can only be satisfied if ¿15 and ¿89 intersect, also shown in Figure 29. Next, consider quadrangle 01572. Conditions D, E, F, G cannot be satisfied, a contradiction. This completes this case.
Figure 29: Cases G1 : 07218G and 07218G07812G
Consider next G01872G2, and quadrangle 07218. Conditions D,E, F cannot be satisfied. Condition G can only be satisfied if the third line through 7 intersects ¿24. The point of intersection must be 4. But this creates a triangle A734 satisfying condition A, a contradiction. This completes this case, and also case BA123BA132CA267C2, and case BA123BA132C and case BA123B.
Case BA123C.
312
Ars Math. Contemp. 10 (2016) 255-268
Refer to Figure 17. Consider the triangle A132. Condition B can be satisfied if the third line through 1 intersects l34. There are two ways this can occur - the intersection can be point 4, or a new point. This gives B1 and B2, shown in Figure 30. Condition C can be satisfied if point 6 is collinear with the third point on 112. There are two ways this can occur. The line through 6 intersecting ii2 can be or a new line. This gives Ci and C2, shown in Figure 31.
/TV	A\'
\5/ / \	\5/ \
\V l\ 6 \ 2 /	I\ 6 \-V
Figure 30: Case BA123CA132 Bi and B2
Figure 31: Case BA123CA132 Ci and C2
It can be observed that Ci is isomorphic to the dual of Bi. If we map points
1,2,3,4, 5, 6,7 of Ci to lines li2, l23, li3, l56, li4, l34, i24, respectively, of Bi, we have an isomorphism. Similarly, C2 is isomorphic to the dual of B2. An isomorphism maps points 1, 2,3,4,5, 6, 7 of C2 to lines li2,li3, l23, l56, l24, i34, li7, respectively, of B2. Consequently, we have only cases Bi and B2 to deal with.
Case BA123CA132Bi.
Consider the quadrangle D1562. Condition D can only be satisfied if the third point on li2 is collinear with point 3. But then triangle A123 would satisfy condition A, which is not allowed. Condition E can be satisfied if l24 intersected . This is shown in Figure 32. Condition F can only be satisfied if the third line through 6 intersected ii5 in point 3. However, 6 and 3 are already collinear. Condition G can be satisfied if the third line through 5 intersected li4. The third line through 5 cannot be i24, for A124 would then satisfy condition A. Thus, the third line through 5 must be a new line, as shown also in Figure 32.
Case BA123CA132B1D1562E.
Consider the triangle A267. Condition B can be satisfied if the third line through 6 intersected li2. The third line through 6 cannot be li4, as the triangle A123 would then satisfy condition A. Hence, the third line through 6 must be a new line, as shown in Figure 33. Condition C can only be satisfied if points 4 and 5 are collinear.
W. L. Kocay: One-point extensions in n3 configurations	313
\5 /	y/i h\
\3/ '	
	4
Figure 32: Case BA123CA132B1D1562 E and G
The line containing 4 and 5 cannot be l14 and it cannot be ^34. Therefore Condition C is impossible, and we must have BA123CA132B1D1562EA267B, shown in Figure 33.
Figure 33: Case BA123CA132B1D1562EA267B
This structure is found to be isomorphic to the dual of BA123BA132CA267B
□	1673G, shown in Figure 26. The isomorphism maps points 1, 2,3,4,5, 6, 7,8 to lines ^24,^26,^56,^15,^34,^18,^68,^14. This completes case BA123CA132B1
□	1562E.
Case BA123CA132Bi□1562G.
Consider the quadrangle ^2651. Condition D can only be satisfied if the third point on i23 is collinear with point 3. However triangle A132 would then satisfy condition A. Condition E can only be satisfied if ¿14 intersected 46. The point of intersection cannot be 7. If it were point 4, then A563 would then satisfy condition A. Hence condition E is not possible. Condition F can only be satisfied if intersected i26 in point 3. However 5 and 3 are already collinear. Condition G can be satisfied if the third line through 6 intersected ^24. The point of intersection cannot be 4. The only possibility is a new line through 6, as shown in Figure 34.
Consider the quadrangle □4863. Condition D can only be satisfied if the third point on ^34 is collinear with point 2. The triangle A342 would then satisfy condition A,
314
Ars Math. Contemp. 10 (2016) 255-268
Figure 34: Cases BA123CA132B1D1562G : D2651G and □2651GD4863G
which is not allowed. Condition E can only be satisfied if intersected ¿68 in either 1 or 5. However, 1 and 5 are already each on 3 lines. Condition F can only be satisfied if ¿56 intersected ¿4s in 2. However 6 and 2 are already collinear. Condition G can be satisfied if the third line through 8 intersected ¿14. The point of intersection can only be 7, shown in the right diagram of Figure 34.
Consider the quadrangle ^6512. Condition D can only be satisfied if the third point on ¿42 were collinear with point 3. But triangle A123 would then satisfy condition A. Condition E can only be satisfied if ¿24 intersected ¿15 in 3. This is not possible. Condition F can only be satisfied if l14 intersected ¿56. This is not possible. Condition G can only be satisfied if ¿57 intersected ¿68. This is shown in Figure 35.
Figure 35: Cases ^6512G and □6512Gœ743G
Consider the quadrangle ^5743. Condition D can only be satisfied if the third point on ¿34 were collinear with point 1. But then triangle A341 would satisfy condition A. Condition E can only be satisfied if ¿23 intersected ¿47 in point 1. This is not possible. Condition F can only be satisfied if ¿24 intersected ¿57 in 9. This is not possible. Condition G can only be satisfied if ¿78 intersected ¿56 in a new point, also shown in Figure 35.
Consider the triangle A157. Condition B can only be satisfied if ¿12 intersected
W. L. Kocay: One-point extensions in n3 configurations
315
¿56. The point of intersection must be point 0. Condition C can only be satisfied if points 4 and 9 are collinear. The line of collinearity must be ¿34. The resulting two structures are both isomorphic to the Desargues configuration, with one incidence missing, as can be seen from Figure 1.1. If we then consider A268, the remaining incidence is forced. This completes case BA123CA132B1[H1562G and also case BA123C A132B1.
Case BA123CA132B2.
Refer to Figure 30. Consider the triangle A173. Condition B can be satisfied if the third line through 7 intersected ¿12. The point of intersection cannot be point 2. Therefore it is a new point, as shown in Figure 36. Condition C can be satisfied if points 4 and 5 are collinear. The line of collinearity cannot be ¿56, for triangle A453 would then satisfy condition A. Hence ¿45 is a new line, also shown in Figure 36. be satisfied if ¿57 intersected ¿68. This is shown in Figure 35.
Figure 36: Cases BA123CA132B2 A173 B and C
Now case BA123CA132B2 A173C is isomorphic to case BA123BA132CA267B, shown in Figure 25. As both diagrams have 7 points, the isomorphism can be given by a permutation, (1,5,6)(2, 3,4), which maps diagram BA123BA132CA267B to BA123CA132B2 A173C. Thus we need only consider case BA123CA132B2 A173B.
Consider the triangle A781 in the left diagram of Figure 36. Condition B can be satisfied if the third line through 8 intersected ¿37. The point of intersection cannot be 3. Therefore there must be a line ¿48, as shown in Figure 37. Condition C can be satisfied if the third point on ¿17 is collinear with point 2. The line of collinearity cannot be ¿26, for if point 6 were on ¿17, triangle A173 would satisfy condition A. Hence ¿24 must intersect ¿17 in a new point. This is also shown in Figure 37.
Case BA123CA132B2A173BA781B.
Consider the triangle A365. Condition B can be satisfied if the third line through 6 intersected ¿37. The point of intersection cannot be 4, because ¿48 would then contain 6, causing a triangle A682 satisfying condition A. Line ¿17 cannot contain 6, for then triangle A136 would satisfy condition A. Therefore condition B requires that ¿78 contain 6, shown in Figure 38. Condition C can be satisfied if the third point on ¿56 were collinear with point 1. The line of collinearity must be ¿17, also shown in Figure 38.
Figure 38: Case BA123CA132B2A173BA781BA365 B and C
Case BA123CA132B2A173BA781BA365B.
Refer to the left diagram of Figure 38. Consider the quadrangle D2176. Condition D can only be satisfied if points 3 and 8 were collinear. This is not possible as 3 and 8 are already incident on 3 lines each. Condition E can only be satisfied if ¿56 intersected ¿17, shown in Figure 39. Condition F can only be satisfied if ¿37 intersected ¿12 in 8. However, 7 and 8 are already collinear. Condition G can only be satisfied if ¿15 and ¿24 intersected. The point of intersection must be 5, making triangle A132 satisfy condition A. We conclude that only E is possible.
Figure 39: Case BA123CA132B2A173BA781BA365BD2176E
Consider the quadrangle D2156. Condition D can only be satisfied if points 3 and 9 were collinear, which is impossible. Condition E can only be satisfied if ¿67 intersected ¿15 in point 3, which is impossible. Condition F can only be satisfied if
W. L. Kocay: One-point extensions in n3 configurations
317
the third line through 5 intersected i12 in point 8, which is impossible. Condition G can only be satisfied if i17 and i24 intersected. The point of intersection must be point 9, also shown in Figure 39. As can be seen from the diagram, this is the Pappus configuration with one incidence missing. We conclude that this case results in the Pappus configuration.
Case BA123CA132B2A173BA781BA365C.
Refer to the right diagram of Figure 38. Consider the quadrangle Q7123. Condition D can only be satisfied if points 4 and 6 are collinear, which is impossible. Condition E can only be satisfied if i13 contains 8, which is impossible. Condition F can only be satisfied if i24 contains point 9. Condition G can only be satisfied if i78 intersected i13. The point of intersection must be 5, creating a triangle A195 satisfying condition A, a contradiction. We conclude that only condition F is possible, shown in Figure 40.
Figure 40: Cases BA123CA132B2 A173BA781BA365CD7123F and D2371F
Consider the quadrangle D2371. Condition D can only be satisfied if points 8 and 9 are collinear, which is impossible. Condition E is only possible if £13 contains 4, which is impossible. Condition F is possible only if £78 contains 6. Condition G is only possible if £29 and £35 intersected, which is impossible. We conclude that condition F is necessary.
We next consider quadrangle D4862. Condition D can only be satisfied if points 9 and 3 are collinear, which is impossible. Condition E can only be satisfied if £21 contains point 7, which is impossible. Condition F is possible only if £69 and £48 intersect in point 5. Condition G is only possible if £47 and £81 intersected, which is impossible. We conclude that condition F is necessary, giving the Pappus configuration. This completes case BA123CA132B2A173BA781B.
Case BA123CA132B2A173BA781C.
Refer to the right diagram of Figure 37. Consider triangle A243. Condition B can only be satisfied if the third line through 4 intersected £28. The point of intersection can only be 8, as shown in Figure 41. Condition C can only be satisfied if points 6 and 7 are collinear. The line of collinearity cannot be £17, as triangle A231 would then satisfy condition A. Hence, the line can only be £78, which must contain 6, as shown in Figure 41.
Case C is isomorphic to the dual of BA123CA132B2A173BA178BA365B, shown in Figure 38. An isomorphism maps points 1, 2,..., 9 of C to lines £67, £34,
£23, £24, £56, £13, £12, £17, £48, respectively, of B. Thus we only need consider case B.
318
Ars Math. Contemp. 10 (2016) 255-268
Figure 41: Case BA123CA132B2A173BA178CA243B and C
Consider the quadrangle D8731. Condition D can only be satisfied if points 2 and 6 are collinear, which is impossible, as the line of collinearity could only be ^24. Condition E cannot be satisfied. Condition F can only be satisfied if l36 intersects l87. The point of intersection must be 6, as shown in Figure 42. Condition G can only be satisfied if ^ and ^79 intersect, which is impossible. Thus, only condition F is possible. But this diagram is isomorphic to case BA123BA132CA267BD1673ED6137E, shown in Figure 27. An isomorphism is given by (5,9)(6,7, 8).
Figure 42: Case BA123CA132B2A173BA178CA243BD8731F
We summarise Case B as follows:
An n3 configuration (E, n), which cannot be constructed by a 1-point extension, and having no triangle satisfying condition A, is one of the Pappus or Desargues configurations.
We still must show that the Fano, Pappus, and Desargues configurations cannot be obtained by 1-point extensions. This is clearly so for the Fano configuration, as there are no 63 configurations. Consider the Pappus configuration. One way to show that it cannot be obtained by a 1-point extension is to start with the unique 83 configuration and to show that the possible 1-point extensions do not produce the Pappus configuration. Another way is to show that every ordering of every triangle and quadrilateral in the Pappus configuration satisfies one of conditions A, B, C, D, E, F, G, so that the Pappus configuration does not
W. L. Kocay: One-point extensions in n3 configurations
319
arise by a 1-point extension. The collineation group of the Pappus configuration has order 108. It is transitive on points, lines, triangles, and quadrangles, so that only one triangle and one quadrilateral need be tested. We omit the proof.
7	W 8	<> /. '
- ' 2
Figure 43: The Pappus configuration
Consider next the Desargues configuration. Its collineation group has order 120. It is transitive on points, lines, triangles, quadrangles, and also on quadruples (a0, ¿2, ai, ¿3), where a0,ai G ¿2, a0 = ai, ai G ¿3, and ¿2 = ¿3. It is not transitive on pentagons, hexagons, etc. Refer to Figure 44. We look for a cycle beginning (a0, ¿2, ai, ¿3,..., ¿0) = (1, ¿i3,3, ¿34,...), satisfying the conditions of Theorem 2.4. Since ¿i n ¿i = 0, where ¿i = ¿37, and ¿i is the third line through a0 = 1, we must have ¿i = ¿i5, so that ¿0 = ¿i7. Since a2 G ¿4, by Theorem 2.4, we cannot have a2 = 5. Hence, a2 = 4.
Figure 44: The Desargues configuration
Then since ¿2 n ¿2 = 0, we cannot have ¿2 = ¿42, as ¿42 intersects ¿2 = ¿i3 in 2. Therefore ¿4 = ¿49, from which we have a3 = 9, and the cycle is (1, ¿i3,3, ¿34,4, ¿49, 9, ..., ¿i7). Since ¿3 n ¿3 = 0, we cannot have ¿3 = ¿59, as ¿59 intersects ¿3 = ¿34 in 5. It follows that ¿5 = ¿59. But then a4 must be either 1 or 5, both of which are impossible. We conclude that the Desargues configuration cannot be obtained by a 1-point extension. This completes the proof of Theorem 4.1.	□
Observe that we have only used 1-point extensions based on triangles and quadrangles in the proof of Theorem 4.1. Hence we have proved that if an (n +1)3 configuration cannot be obtained using a 1-point extensions based on triangles or quadrangles, then it is the Fano, Pappus, Desargues, or a Fano-type configuration. Therefore we have the following corollary.
320
Ars Math. Contemp. 10 (2016) 255-268
Corollary 4.2. Every (n +1)3 configuration that can be obtained from an n3 configuration by a 1-point extension, can be obtained using a 1-point extension based on triangles or quadrangles.
A consequence of this corollary is that the (n + 1)3 configurations can be constructed from the n3 configurations by constructing all sequences of sequentially incident points and lines of length at most 4, and testing whether they satisfy the conditions required for a 1-point extension. Isomorphism testing of the resulting (n + 1)3 configurations then gives all configurations that can be constructed by 1-point extensions. Those which cannot be constructed in this way are the Fano-type configurations, which can be constructed from cycles and subdivisions of bipartite 3-regular multigraphs, using Theorem 3.2.
One of the central problems in the theory of n3 configurations is to determine whether they are geometric, that is, whether they can be coordinatized over the reals and/or rationals. See [3, 14, 15, 16]. This means to assign homogeneous coordinates in the real and/or rational projective plane, so that the lines are straight lines, and all incidences and non-incidences are respected. The application of 1-point extensions to geometric configurations will be described in another article (in preparation).
5 The 3-Point Extension
Let (S, n) be an n3-configuration. Choose a line ¿, and let its points be ai, a2, a3. Construct a new configuration (S', n') as follows. S' = S U b2, b3, ¿^ ¿2, ¿3}, where bi, b2, b3 are new points and ¿^ ¿2, ¿3 are new lines. The incidences n' are constructed as follows. ¿i contains the points ai, b2, b3. ¿2 contains the points bi, a2, b3, and ¿3 contains the points bi, b2, a3. Choose 3 lines ¿i, ¿2, ¿3 = ^ such that ¿j contains a4. Remove aj from ¿j and place bj on ¿j. This is illustrated in the following table. Then n' contains all remaining incidences of n, except for the incidences a^i, a^2, a^3.
¿	¿i	¿2	¿3	¿'i	¿' ¿2	¿' ¿3
ai	ai	bi	bi	bi	b2	b3
a2	b2	a2	b2			
a3	b3	b3	a3			
Theorem 5.1. (S', n') is an (n + 3)3-configuration.
Proof. Note that each bj is incident on exactly 3 lines, and that each of ¿i, ¿2, ¿3 is incident on exactly 3 points. We must verify that any 2 lines of (S', n') intersect in at most one point. Clearly ¿, ¿^¿^¿3 intersect each other in at most one point. Similarly for ¿, ¿i, ¿2, ¿3. The same is true for all other lines of S', because it is true for (S, n). □
Example 5.2. The Fano configuration has 7 points and 7 lines, all of which are equivalent under automorphisms. There is one way to choose 3 points ai, a2, a3. The incidences of ¿, ¿i, ¿2, ¿3 are uniquely determined. The choice of ¿i, ¿2, ¿3 is not unique, as each aj is incident on two lines other than ¿. There results two possible 3-point extensions of the Fano configuration. One of these is the Desargues configuration. The other is known as the "anti-Pappian" configuration [5].
A complete quadrilateral in an n3 configuration is a set of four distinct lines intersecting in six distinct points. Notice that the extended configuration (S', n') always contains a complete quadrilateral ¿, ¿i, ¿2, ¿3, intersecting in the six points ai, a2, a3, bi, b2, b3. The
W. L. Kocay: One-point extensions in n3 configurations
321
3-point extension can also be constructed from the dual point of view - rather than beginning with 3 collinear points ai, a2, a3, we begin with 3 concurrent lines, and so forth. This is equivalent to using the 3-point extension in the dual of (£, n), and then dualizing (£', n'). In this case, the 3-point extension will always contain a complete quadrangle, that is, the dual of a complete quadrilateral.
Theorem 5.3. The Fano-type configurations cannot be obtained by a 3-point extension.
Proof. Suppose that a Fano-type configuration (£, n) were obtained by a 3-point extension. It would then contain a complete quadrilateral ¿, ¿1, ¿2,¿3, intersecting in the six points a1, a2, a3, b1, b2, 63. These four lines and six points must all be part of a single F', Fp, or Fe. Refer to Figure 6. Now the points a1, a2, a3 must be collinear. Furthermore, there must be a line containing a1,62, 63, and so forth. This determines the labelling of an F', Fp, or Fe. But we then find there is a line containing at least one of the pairs a1, 61; a2, 62; a3,63, which is not possible in a 3-point extension.	□
6 Acknowledgement
The author would like to thank an anonymous referee for very many helpful comments, and especially for bringing the articles [1, 2, 4, 12, 13] to his attention.
References
[1]	M. Boben, Reductions of («3) configurations, 2005, arXiv:math/0505136 [math.CO] .
[2]	M. Boben, Irreducible (v3) configurations and graphs, Discrete Math. 307 (2007), 331-344, doi:10.1016/j.disc.2006.07.015.
[3]	J. Bokowski and B. Sturmfels, Computational synthetic geometry, Berlin etc.: Springer-Verlag, 1989, doi:10.1007/BFb0089253.
[4]	H. Carstens, T. Dinski and E. Steffen, Reduction of symmetric configurations n3, Discrete Appl. Math. 99 (2000), 401-411, doi:10.1016/S0166-218X(99)00147-X.
[5]	D. G. Glynn, On the anti-Pappian 103 and its construction, Geom. Dedicata 77 (1999), 71-75, doi:10.1023/A:1005167220050.
[6]	H. Gropp, Configurations between geometry and combinatorics, Discrete Appl. Math. 138 (2004), 79-88, doi:10.1016/S0166-218X(03)00271-3.
[7]	B. Grunbaum, Configurations of points and lines, Providence, RI: American Mathematical Society (AMS), 2009.
[8]	W. Kocay, Coordinatizing n3 configurations, in preparation.
[9]	W. Kocay and R. Szypowski, The application of determining sets to projective configurations, Ars Comb. 53 (1999), 193-207.
[10]	V. Martinetti, Sulle configurazioni piane Ann. Mat. Pura Appl. 15 (1887), 1-26.
[11]	T. Pisanski and B. Servatius, Configurations from a graphical viewpoint, New York, NY: Birkhauser, 2013, doi:10.1007/978-0-8176-8364-1.
[12]	E. Steffen, T. Pisanski, M. Boben and N. Ravnik, Erratum to: "Reduction of symmetric configurations n3" [Discrete Appl. Math. 99 (2000), no. 1-3, 401-411; by H. G. Carstens, T. Dinski and Steffen], Discrete Appl. Math. 154 (2006), 1645-1646, doi:10.1016/j.dam.2006.03.015, http://dx.doi.org/10.1016/j.dam.2006.03.015.
[13]	K. Stokes, Irreducibility of configurations, Ars Math. Contemp. 10 (2016), 169-181.
322
Ars Math. Contemp. 10 (2016) 255-268
[14]	B. Sturmfels, Aspects of computational synthetic geometry. I. Algorithmic coordinatization of matroids, in: Computer aided geometric reasoning, Vol. I, II (Sophia-Antipolis, 1987), INRIA, Rocquencourt, pp. 57-86, 1987.
[15]	B. Sturmfels and N. White, Rational realizations of 113-and 123-configurations, in: Symbolic Computation in Geometry, H. Crapo et al. IMA preprint series, volume 389, 1988 .
[16]	B. Sturmfels and N. White, All 113 and 123-configurations are rational, Aequationes Math. 39 (1990), 254-260.