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) 99-112
Quasi-configurations: Building blocks for point-line configurations
Jürgen Bokowski *
Technische Universität Darmstadt, Dolivostraße 15, 64293 Darmstadt, Germany
Vincent Pilaüd f
CNRS & LIX, Ecole Polytechnique, 91128 Palaiseau Cedex, France
Received 31 March 2014, accepted 19 March 2015, published online 24 Jüly 2015
We study point-line incidence structures and their properties in the projective plane. Our motivation is the problem of the existence of (n4 ) configurations, still open for few remaining values of n. Our approach is based on quasi-configurations: point-line incidence structures where each point is incident to at least 3 lines and each line is incident to at least 3 points. We investigate the existence problem for these quasi-configurations, with a particular attention to 3|4-configurations where each element is 3- or 4-valent. We use these quasi-configurations to construct the first (374) and (434) configurations. The existence problem of finding (224), (234), and (264) configurations remains open.
Keywords: Projective arrangements, point-line incidence structure, (nk ) configurations. Math.. Subj. Class.: 52C30
1 Introduction
A geometric (nk ) configuration is a collection of n points and n lines in the projective plane such that each point lies on k lines and each line contains k points. We recommend our reader to consult GrUnbaum's book [7] for a comprehensive presentation and an historical perspective on these configurations. The central problem studied in this book is to determine for a given k those numbers n for which there exist geometric (nk ) configurations. The answer is completely known for k = 3 (geometric (n3) configurations exist if
*http://wwwopt.mathematik.tu-darmstadt.de/~bokowski/
ÎCorresponding author. http://www.lix.polytechnique.fr/~pilaud/. VP was partially supported by the Spanish MICINN grant MTM2011-22792 and by the French ANR grant EGOS 12 JS02 002 01.
E-mail addresses: juergen.bokowski@gmail.com (Jurgen Bokowski), vincent.pilaud@lix.polytechnique.fr (Vincent Pilaud)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
100
Ars Math. Contemp. 10 (2016) 99-112
rations.
and only if n > 9), partially solved for n = 4 (geometric (n4) configurations exist if and only if n =18 or n > 20 with a finite list of possible exceptions), and wide open for k > 4. Our contribution concerns k = 4, where we provide solutions for two former open cases: there exist geometric (374) and (434) configurations. Moreover, we study building blocks for constructing geometric (nk ) configurations that might be of some help for clarifying the final open cases (224), (234), and (264). Many aspects of our presentation appeared during our investigation of the case (194 ) in which there is no geometric (194) configuration, see [1, 2].
The approach of this paper is to construct geometric (n4) configurations from smaller building blocks. For example, Griinbaum's geometric (204) configuration [6] can be constructed by superposition of two geometric (103) configurations as illustrated in Figure 1. To extend this kind of construction, we study an extended notion of point-line configurations, where incidences are not regular but still prescribed.
1.1 Point - line incidence structures
We define a point-line incidence structure as a set P of points and a set L of lines together with a point-line incidence relation, where two points of P can be incident with at most one line of L and two lines of L can be incident with at most one point of P. Throughout the paper, we only consider connected incidence structures, where any two elements of P u L are connected via a path of incident elements.
For a point-line incident structure (P, L), we denote by p the number of points of P contained in i lines of L and similarly by £j the number of lines of L containing j points
J. Bokowski and V. Pilaud: Quasi-configurations: Building blocks for point-line config... 
101
of P. We find it convenient to encode these incidence numbers into a pair of polynomials (P(x), L(y)), called the signature of (P, L), and defined by
P(x) := Pix4 and L(y) := jyj.
For example, the point-line incidence structure represented in Figure 2 has signature (8x3 + 2x4,8y3 + 2y4). With these notations, the number of points and lines are given by |P | = P(1) and |L| = L(1), while the number of point-line incidences is given by K(p^) g P x L | P g ni = P'(1) = L'(1).
We distinguish three different levels of point-line incidence structures, in increasing generality:
Geometric Points and lines are ordinary points and lines in the real projective plane P.
Topological Points are ordinary points in P, but lines are pseudolines, i.e., non-separating simple closed curves of P which cross pairwise precisely once.
Combinatorial Just an abstract incidence structure (P, L) as described above, with no additional geometric structure.
In this paper, we are mainly interested in the geometric level. We therefore omit the word geometric in what follows unless we have to distinguish different levels.
1.2 (nk ) configurations
One of the main problems in the theory of point-line incidence structures is to clarify the existence of regular point-line incidence structures. A k-configuration is a point-line incidence structure (P, L) where each point of P is contained in k lines of L and each line of L contains k points of P. In such a configuration, the number of points equals the number of lines, and thus it has signature (nxk, nyk ). If we want to specify the number of points and lines, we call it an (nk) configuration. We refer to the recent monographs of Griinbaum [7] and Pisanski and Servatius [8] for comprehensive presentations of these objects. Classical examples of regular configurations are Pappus' and Desargues' configurations, which are respectively (93) and (103) configurations. In the study of the existence of (n4) configurations there are still a few open cases. Namely, it is known that (geometric) (n4 ) configurations exists if and only if n = 18 or n > 20, with the possible exceptions of n = 22,23, 26, 37 and 43 [5, 4, 2]. Different methods have been used to obtain the current results on the existence of 4-configurations:
(i)	For n < 16, Bokowski and Schewe [3] used a counting argument based on Euler's formula to prove that there exist no (n4) configuration, even topological.
(ii)	For small values of n, one can search for all possible (n4) configurations. For n = 17 or 18, one can first enumerate all combinatorial (n4) configurations and search for geometric realizations among them. This approach was used by Bokowski and Schewe in [4] to show that there is no (174) configuration and to produce a first (184) configuration. Another approach, proposed in [1], is to enumerate directly all topological (n4) configurations, and to search for geometric realizations among this restricted family. In this way, we showed that there are precisely two (184) configurations, that of [4] and another one [1], see Figure 3. For n = 19, we obtained in [1] all 4 028 topological (194) configurations and the study of their realizability has led to the result that there is no geometric (194) configuration [2].
102
Ars Math. Contemp. 10 (2016) 99-112
(iii)	For larger values of n, one cannot expect a complete classification of (n4) configurations. However, one can construct families of examples of 4-configurations. One of the key ingredients for such constructions is the use of symmetries. See Figure 1 for the smallest example obtained in this way, and refer to the detailed presentation in Grunbaum's recent monograph [7].
(iv)	Finally, Bokowski and Schewe introduced in [4] a method to produce (n4) configurations from deficient configurations. It consists in finding two point-line incidence structures (P, L) and (P', L') of respective signatures (ax3 + bx4, cy3 + dy4) and (cx3 + ex4, ay3 + fy4), where a + b + c + e = a + c + d + f = n, and a projective transformation which sends the 3-valent points of P to points contained in a 3-valent line of L', and at the same time the 3-valent lines of L to lines containing a 3-valent point of P'. This method was used to obtain the first examples of (294) and (314) configurations.
In this paper, we are interested in this very last method described above. We are going to study deficient configurations (see the notion of quasi-configuration and 3|4-configuration in the next subsection) for the use of them as building blocks for configurations. Our study has led in particular to first examples of (374) and (434) configurations. Thus the remaining undecided cases for the existence of (n4) configurations are now only the cases n = 22,23, and 26.
1.3 Quasi-configurations
A quasi-configuration (P, L) is a point - line incidence structure in which each point is contained in at least 3 lines and each line contains at least 3 points of P. In other words, the signature (P, L) of (P, L) satisfies x3 | P(x) and y3 | L(y). The term "quasi-configuration" for this concept was suggested by Griinbaum to the authors. As observed above, these quasi-configurations can sometimes be used as building blocks for larger point-line incidence structures.
In this paper, we investigate in particular 3| 4-configurations, where each point of P is contained in 3 or 4 lines of L and each line of L contains 3 or 4 points of P. In other words, 314-configurations are point-line incidence structures whose signature is of the form (ax3 + bx4, cx3 + dx4) for some a, b, c, d g N satisfying 3a + 4b = 3c + 4d. Note that their numbers of points and lines do not necessarily coincide. If it is the case, i.e., if a + b = c + d = n, we speak of an (n3|4) configuration. In this case, a = c and b = d, the number of points and lines is n = a + b = c + d and the number of incidences is 3a + 4b = 3c + 4d.
We think of an (n3|4) configuration as a deficient (n4) configuration. A good measure on (n3|4) configurations is the number of missing incidences a. We say that an (n3|4) configuration is optimal if it contains the maximal number of point-line incidences among all (n3|4) configurations. One objective is to study and classify optimal (n3|4) configurations for small values of n.
Example 1.1. Figure 2 shows an incidence structure with signature (8x3 + 2x4, 8y3 + 2y4). It is a 103|4-configuration: the 3-valent elements are colored red while the 4-valent elements are colored blue. We will see in Figure 7 that this 3| 4-configuration is not optimal.
J. Bokowski and V. Pilaud: Quasi-configurations: Building blocks for point-line config... 103
Figure 2: A quasi-configuration with signature (8x3 + 2x4, 8y3 + 2y4). 1.4 Overview
The paper is divided into two parts. In Section 2, we illustrate how quasi-configurations (in particular 3|4-configurations) can be used as building blocks to construct (n4 ) configurations, and we obtain in particular examples of (374) and (434) configurations. In Section 3, we present a counting obstruction for the existence of topological quasi-configurations, and we study optimal (n3|4) configurations with few points and lines.
2 Constructions
We discuss here different ways to obtain new point-line incidence structures from old ones. We are in particular interested in the construction of new quasi-configurations from old ones. We use these techniques to provide the first (374) and (434) configurations.
2.1 Operations on point - line incidence structures
To construct new point-line incidence structures from old ones, we will use the following operations, illustrated in Section 2.2:
Deletion Deleting elements from a point-line incidence structure yields a smaller incidence structure. Note that deletions do not necessarily preserve connectedness or quasi-configurations. We can however use deletions in 4-configurations to construct 3|4-configurations if no remaining element is incident to two deleted elements.
Addition As illustrated by the example of Griinbaum's (204) configuration [6] in Figure 1, certain point-line incidence structures can be obtained as the disjoint union of two smaller incidence structures (P, L) and (P', L'). In particular, we obtain an (n4) configuration if (P, L) and (P', L') are 3|4-configurations, if each 3-valent element of (P, L) is incident to precisely one 3-valent element of (P', L') and conversely, and if no other incidences appear.
Splitting The reverse operation of addition is splitting: given a point- line incidence structure, we can split it into two smaller incidence structures. We can require additionally
104	Ars Math. Contemp. 10 (2016) 99-112
Figure 3: Splittings of the two geometric (184) configurations [4,1] into two (93|4) configurations. The rightmost (184) configuration even splits into two (93) configurations. The points which seem isolated are in fact at infinity in the direction pointed by the corresponding arrow, and are incident to the 4 lines parallel to that direction.
the two resulting incidence structures to be quasi-configurations or even regular configurations. For example, the two geometric (184) configurations [4, 1] as well as Grunbaum's (204) configuration [6] are splittable into 3|4-configurations, see Figures 1 and 3.
Superposition Slightly more general than addition is the superposition, where we allow the two point-line incidence structures (P, L) and (P', L') to share points or lines. For example, we can superpose two 2-valent vertices to make one 4-valent vertex. This idea is used in our construction of (374) and (434) configurations below.
2.2 Examples of constructions
We now illustrate the previous operations and produce 4-configurations from smaller point-line incidence structures. We start with a simple example.
Example 2.1 (A (384) configuration). It was shown in [2] that no topological (194) configuration can be geometrically realized with points and lines in the projective plane. However, Figure 4 (left) shows a geometric realization of a topological (194) configuration where one line has been replaced by a circle. Forgetting this circle, we obtain a 3|4-configuration with signature (15x4 + 4x3,18x4). We take two opposite copies of this 3|4-configuration (colored purple and red in Figure 4 (right)) and add two lines (colored green in Figure 4 (right)) each incident to two points in each copy. We obtain a (384) configuration.
Using similar ideas, we observe that it is always possible to produce a 4-configuration from any 3|4-configuration.
Example 2.2 (Any 3|4-configuration generates a 4-configuration). From a 3| 4-configura-tion with signature (ax3 + bx4, cy3 + dy4), we can construct an (n4) configuration where
n = 16a + 16b + 4c = 4a + 16c + 16d as follows:
(i) We take four translated copies of the 314-configuration and add suitable parallel lines through all 3-valent points.
J. Bokowski and V. Pilaud: Quasi-configurations: Building blocks for point-line config... 
105
Figure 4: (Left) A geometric realization of a topological (194) configuration where one line has been replaced by a circle. (Right) A (384) configuration built from two copies of this incidence structure. The construction is explained in full detail in Example 2.1.
(ii)	We take the geometric dual of the resulting 3|4-configuration (remember that geometric duality transforms a point p of the projective plane into the line formed by all points orthogonal to p and conversely).
(iii)	We take again four translated copies of this dual 3|4-configuration and add suitable parallel lines through all 3-valent vertices.
Of course, we can try to obtain other 4-configurations from 3| 4-configurations. This approach was used by Bokowski and Schewe [4] to construct (294) and (314) configurations from the (143|4), (153|4) and (163|4) configurations of Figure 9. We refer to their paper [4] for an explanation. Here, we elaborate on the same idea to construct two new relevant (n4) configurations.
Example 2.3 (First (434) configuration). To construct a ((n + m)4) configuration from an (n4) configuration and an (m4) configuration, we proceed as follows (see Figure 5):
(i)	We delete two points not connected by a line in the (n4) configuration and consider the eight resulting 3-valent lines (colored blue in Figure 5 (top left) and orange in Figure 5 (top right)).
(ii)	We add four points (colored green in Figure 5), each incident with precisely two 3-valent lines. All points and lines are now 4-valent again, except the four new 2-valent points.
(iii)	We do the same operations in the (m4) configuration.
(iv)	Finally, we use a projective transformation that maps the set of four 2-valent points in the first quasi-configuration onto the set of four 2-valent points in the second quasi-configuration. This transformation superposes the 2-valent points to make them 4-valent.
106
Ars Math. Contemp. 10 (2016) 99-112
If this transformation does not superpose other elements than the 2-valent ones and does not create additional unwanted incidences, it yields the desired ((n + m)4) configuration. This construction is illustrated on Figure 5, where we obtain a (434) configuration from a (254) configuration [7] and a (184) configuration [1].
Unfortunately, the method from the previous example cannot provide a (374) configuration since there is no (n4) configuration for n < 17 [4] and for n = 19 [2]. We therefore need another method, which we describe in the following example.
Example 2.4 (First (374) configuration). To construct a ((n + m -1)4) configuration from an (n4) configuration and an (m4) configuration, we proceed as follows (see Figure 6):
(i)	We delete two points on the same line (colored green in Figure 6) of the (n4) configuration and consider the six resulting 3-valent lines (colored blue in Figure 6 (top left) and orange in Figure 6 (top right)).
(ii)	We add three points (colored green in Figure 6), each incident with precisely two 3-valent lines. All points and lines are now 4-valent again, except the initial 2-valent line and the three new 2-valent points.
(iii)	We do the same operations in the (m4) configuration.
(iv)	Finally, we use a projective transformation that maps the set of four 2-valent elements in the first quasi-configuration onto the set of four 2-valent elements in the second quasi-configuration. This transformation superposes the 2-valent elements to make them 4-valent.
If this transformation does not superpose other elements than the 2-valent ones and does not create additional unwanted incidences, it yields the desired ((n + m - 1)4) configuration. This construction is illustrated on Figure 6, where we obtain a (374) configuration from a (204) configuration [7] and a (184) configuration [1].
We invite the reader to try his own constructions, similar to the constructions of Examples 2.3 and 2.4, using the operations on point-line incidence structures described above. In this way, one can obtain many (n4) configurations for various values of n. Additional features can even be imposed, such as non-trivial motions or symmetries. We have however not been able to find answers to the following question.
Question 1. Can we create a (224) configuration by glueing two quasi-configurations with 11 points and lines each? More generally, can we construct (224), (234), or (264) configurations by superposition of smaller quasi-configurations?
3 Obstructions and optimal 3|4-configurations
In this section, we further investigate point-line incidence structures and 3|4-configura-tions. We start with a necessary condition for the existence of topological incidence structures with a given signature. For this, we extend to all topological incidence structures an argument of Bokowski and Schewe [3] that was used to prove the non-existence of (154) configurations. We obtain the following inequality.
Proposition 3.1. Let (P, L) be topological incidence structure with signature (P, L). Then
P"(1) + 2P'(1) - L(1)2 + L(1) - 6P(1) + 6 < 0.
J. Bokowski and V. Pilaud: 
Quasi-configurations: 
Building blocks for point-line config... 
107

/ /1
construction is explained in full detail in Example 2.3.
108
Ars Math. Contemp. 10 (2016) 99-112
Figure 6: A (374) configuration built from deficient (204) and (184) configurations. The construction is explained in full detail in Example 2.4.
J. Bokowski and V. Pilaud: Quasi-configurations: Building blocks for point-line config... 
109
Proof. Let pi be the number of ¿-valent points and £j the number of j-valent lines in the incidence structure (P, L). The signature (P, L) is P(x) := J2i P^ and L(y) := J2j £jyj.
Since the incidence structure is topological, we can draw it on the projective plane such that no three pseudolines pass through a point which is not in P. We call additional 2-crossings the intersection points of two lines of L which are not points of P. We consider the lifting of this drawing on the 2-sphere. We obtain a graph embedded on the sphere, whose vertices are all points of P together with all additional 2-crossings, whose edges are the segments of lines of L located between two vertices, and whose faces are the connected components of the complement of L. Let /0, /1 and /2 denote respectively the number of vertices, edges and faces of this map. Denoting by deg(p) the number of lines of L containing a point p g P and similarly by deg(£) the numbers of points of P contained in a line £ g L, we have
/0 = 2 (L2:)) - 2 E ((deg(P)) - l) = L(1)(L(1) - 1) + 2P(1) - E ¿(i - 1)Pi, /1 = 2 Edeg(£) + 2/o - 2P(1) = 2 Ej£j + 2/o - 2P(1) = 2 E»Pi + 2/o - 2P(1),
eeL j	i /2 = /1 - /0 + 2.
Moreover, since no face is a digon, we have 3/2	< 2/1. Replacing /2 and /1 by the above expressions, we obtain
0 > 3/2 - 2/1 = /1 - 3/o + 6 = 2 E ¿Pi - 4P(1) - /0 + 6
i
= E»(» + 1)Pi - L(1)(L(1) - 1) - 6(P(1) - 1),
i
and thus the desired inequality.	□
Corollary 3.2. If (ax3 + bx4, ay3 + by4) is the signature of a topological incidence structure, then
-(a + b)2 +7a + 15b + 6 < 0.
The following table provides the minimum value of b for which there could exist a topological incidence structure with signature (ax3 + bx4, ay3 + by4):
a	0	1	2	3	4	5	6	7
bmin	16	14	13	11	9	8	6	3
Proof. Direct from Proposition 3.1 with P(x) = ax3 + bx4 and L(y) = ay3 + by4. □
For example, there is no topological (154) configuration [3] and no incidence structure with signature (7x3 + 2x4, 7y3 + 2y4). Compare to Example 1.1 which shows that a configuration with signature (8x3 + 2x4, 8y3 + 2y4) exists.
( n2 + 17n — 6
Corollary 3.3. A (n3|4) configuration has at most /max := mi^ 4n , ---
incidences. The values of Imax appear in the following table:
n	7	8	9	10	11	12	13	14	15	16
^max	20	24	28	33	37	42	48	53	59	64
110
Ars Math. Contemp. 10 (2016) 99-112
Proof. Consider an (n3|4) configuration with signature (ax3 + bx4,ay3 + by4) where a + b = n. The number of incidences is 1 := 3a + 4b. It can clearly not exceed 4n. For the second term in the minimum, we apply Corollary 3.2 to get
0 > -(a + b)2 +7a + 15b + 6 = -(a + b)2 + 8(3a + 4b) - 17(a + b) + 6 = -n2 + 81 - 17n + 6.
Corollary 3.4. There is no topological (n3|4) configuration if n < 8.
□
Proof. If n < 7, there is no topological (n3|4) configuration since it should have at least 3n incidences, which is larger than the upper bound of Corollary 3.3. If n = 8, a (83|4) configuration should be a (83) configuration by Corollary 3.3. But the only combinatorial (83) configuration is not topological.	□
To close this section, we exhibit optimal (n3|4) configurations for small values of n, i.e., (n3|4) configurations which maximize the number of point-line incidences.
Proposition 3.5. For 9 < n <13, the bound of Corollary 3.3 is tight: there exists (n3|4) configurations with n +1g7"-6 incidences.
Proof. For n = 13, we consider the (133|4)-configuration of Figure 7. The homogeneous coordinates of its points and lines are given by
r	i	
P:= L:= I		
l	1	
ij e{-i,0, lUu
1		0		1		1
0	,	1	,	1	,	-1
0		0		0		0
For n = 10,11 or 12, we obtain (n3|4) configurations by removing suitable points and lines in our (133|4) configuration. The resulting configurations are illustrated in Figure 7. (Note that for n = 10, we even have two dual ways to suitably remove three points and three lines from our (133|4) configuration: either we remove three 3-valent points and the three 4-valent lines containing two of these points, or we remove three 3-valent lines and the three 4-valent points contained in two of these lines). Finally, for n = 9 we use the bottom rightmost (93|4) configuration of Figure 7.	□
As a curiosity, we give another example of an optimal (123|4) configuration which contains Pappus' and Desargues' configurations simultaneously. See Figure 8.
Observe that optimal (n3|4) configurations are given by (n4) configurations for large n, and that the only remaining cases for optimal (n3|4) configurations are for n = 14, 15, 16, 17, 19, 22, 23, and 26. We have represented in Figure 9 some (153|4) and (163|4) configurations which we expect to be optimal, although they do not reach the theoretical upper bound of Corollary 3.3. Observe also that deleting the circle in Figure 4 (left) and adding one line through two of the resulting 3-valent points provides a (19314 ) configuration with 74 incidences, which is almost optimal since there is no (194) configuration [1, 2]. To conclude, we thus leave the following question open.
Question 2. What are the optimal (143|4) configurations? Are the (153|4) and (163|4) configurations in Figure 9 optimal? Is there a (193|4) configuration with 75 incidences.
J. Bokowski and V. Pilaud: Quasi-configurations: Building blocks for point-line config... 111
Figure 7: Optimal (n3|4) configurations, for n = 13,12,11,10,9. They have respectively 48, 42, 37, 33, and 28 point-line incidences. The 3-valent elements are colored red while the 4-valent elements are colored blue.
Figure 8: An optimal (123|4) configuration (left) which contains simultaneously Pappus' configuration (middle) and Desargues' configuration (right). In the (123|4) configuration, the 3-valent elements are colored red while the 4-valent elements are colored blue. In the Pappus' and Desargues' subconfigurations, all elements are 3-valent, but we keep the color to see the correspondence better.
112
Ars Math. Contemp. 10 (2016) 99-112
Figure 9: Apparently optimal (153|4) and (163|4) configurations. They have 56 and 60 point-line incidences respectively. The 3-valent elements are colored red while the 4-valent elements are colored blue.
References
[1]	J. Bokowski and V. Pilaud, Enumerating topological (nk)-configurations, Comput. Geom. 47 (2014), 175-186.
[2]	J. Bokowski and V. Pilaud, On topological and geometric (194) configurations, European J. Combin. 50 (2015), 4-17.
[3]	J. Bokowski and L. Schewe, There are no realizable 154- and 164-configurations, Rev. Roumaine Math. Pures Appl. 50 (2005), 483-493.
[4]	J. Bokowski and L. Schewe, On the finite set of missing geometric configurations (n4), Comput. Geom. 46 (2013), 532-540.
[5]	B. Griinbaum, Connected (n4) configurations exist for almost all n, Geombinatorics 10 (2000), 24-29.
[6]	B. Grunbaum, Musings on an example of Danzer's, EuropeanJ. Combin. 29 (2008), 1910-1918.
[7]	B. Grunbaum, Configurations of points and lines, volume 103 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2009.
[8]	T. Pisanski and B. Servatius, Configurations from a graphical viewpoint, Birkhauser Advanced Texts: Basler Lehrbucher, Birkhauser/Springer, New York, 2013.