ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 479-485
A manifold associated to a topological (nk) configuration*
*
Jürgen Bokowski
Technische Universität Darmstadt, Germany
Ricardo Strausz
Universidad National Autónoma de México, México, D.F., México
Received 13 October 2011, accepted 17 December 2013, published online 11 Jüly 2014
In the study of topological (nk) configurations in the projective plane we have n pseudolines and n points. Precisely k of these points are incident with each pseudo-line and, vice versa, precisely k pseudo-lines are incident with each point. We describe a non-orientable 2-manifold associated in a natural way to a topological (nk) configuration in the projective plane. Apart from being interesting in its own right, this manifold defines an equivalence class within topological configurations. It can be used to distinguish topological (nk) configurations.
Keywords: Point-line configuration, pseudo-line, 2-manifold. Math. Subj. Class.: 51E20, 52C30, 05B30
1 Introduction
This article concerns point-line configurations in the sense of B. Griinbaum's research monograph, [8]. We recommend the reader to have a look at this book and we assume the reader to know pseudo-line arrangements in the projective plane as rank 3 oriented matroids, compare [1], or [2].
We define a topological (nk) configuration in the projective plane as a pair of n pseudolines and n points in the projective plane such that the point-line incidence graph is k-regular.
* This paper is a part of Bled'11 Special Issue.
E-mail addresses: juergen@bokowski.de (Jurgen Bokowski), strausz@matem.unam.mx (Ricardo Strausz) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
402
Ars Math. Contemp. 7 (2014) 379-187
The study of these topological configurations can help to solve problems for geometric configurations, i.e., when all pseudo-lines are straight lines. When we consider pseudolines and points only as abstract elements, we have a combinatorial (nk) configuration. When starting with a combinatorial configuration, we can first try to find all corresponding topological ones, a corresponding investigation was done in [9].
Whenever a class of topological (nk ) configurations is given, we provide in this paper a concept to subdivide this class into natural subclasses. We use for that an associated 2-manifold.
2 Manifold associated to a topological configuration
When two pseudo-line arrangements are given, it is in general not an easy task to tell of whether they are isomorphic. We say that the pseudo-line arrangements are isomorphic up to a relabeling of its elements when there exists a relabeling of the pseudo-lines and a topological transformation of the projective plane that maps the first set of pseudo-lines onto the possibly relabeled second set of pseudo-lines. This notion defines equality of oriented matroids (in rank 3) up to relabeling its elements.
We can also say that two given topological (nk) configurations are isomorphic up to relabeling, when their oriented matroids are equal up to relabeling its elements and when the point-line incidences remain the same.
However, for a given combinatorial configuration there are in general many topological configurations. It is useful to subdivide them into natural classes. This is what we suggest.
We associate a 2-manifold to each topological (nk ) configuration. When the 2-manifold differs for two topological (nk) configurations, the configurations are not isomorphic up to relabeling, When the 2-manifolds coincide, we have a natural common property of the configurations.
The n pseudo-lines of a topological (nk ) configuration form a rank 3 oriented matroid or a pseudo-line arrangement in the projective plane.
We pick for such a topological (nk) configuration with n pseudo-lines in the projective plane an additional pseudo-line as the pseudo-line at infinity. This allows us to orient all given pseudo-lines of the topological (nk ) configuration. These orientations induce a cyclic order for each set of k points lying on a particular pseudo-line of the configuration. We call an oriented pair (Pi, Pi+i) of adjacent points in such a cyclic sequence of points (Pi,... ,Pk) on a pseudo-line l of the configuration a segment si(l).
A segment si(l) can also be considered to be that part of the pseudo-line l that connects the corresponding defining points (Pi, Pi+i) and that contains no additional point of the configuration. We distinguish for such a segment si(l), i e {1,..., k}, its two sides, the right side si+(l) with respect to the orientation of the pseudo-line l and the left side s-(l) with respect to its orientation. We speak of the two signed segments of a segment. When we follow a signed segment across the pseudo-line at infinity, the right side and the left side interchanges, i.e., s+(l) = (Pk,Pi)+ and s-(l) = (Pi,P2)- form a connected path. We say that s+(l) points to the right of the oriented pseudo line l between Pi and Pk and up to
J. Bokowski and R. Strausz: A manifold associated to a topological (nk ) -configuration 483
the pseudo-line at infinity. In the remaining part of l s+(l) points to the left.
When we go around a point p of the configuration, we have 2 • k adjacent pairs of signed segments. The signed segments of such a pair both point to the same adjacent region, and they both are joined via the midpoint p. We call these 2 • k pairs of signed segments angles at p. We glue angles with the same signed segment along their equal signed segments. When we do this repeatedly, we obtain a polygon of signed segments: a closed path.
Definition 2.1. Configuration manifold of a topological (nk) configuration. We define a manifold given by a topological (nk) configuration by taking as its 2-cells all closed paths that we obtain from the above construction. The manifold property is clear. Each 2-cell has at least three edges (signed segments) and each signed edge is incident with precisely one additional signed edge.
In Figure 1 we see as an example, a geometric (123) configuration. All pairs of segments between adjacent points of the configuration are drawn. When we follow the sequences of connected line segments, we can count the path lengths of them.
Figure 1: Configuration manifold of a (123) configuration
402
Ars Math. Contemp. 7 (2014) 379-187
3 Mutation class of a topological configuration
For a combinatorial configuration we often have many topological realizations. Already in the (174) case, the unique combinatorial configuration that admits a topological configuration, compare [8], Figure 3.2.2, or [3], Proposition 3, has not a unique topological realization. We have several topological solutions that can be changed via mutations of the pseudo-line arrangement without changing the combinatorial configuration. A mutation is sometimes also referred to as a Reidemeister move. We have depicted this example in Figure 2. On the line at infinity there are two points, not points of the configuration, at which precisely three pseudo-lines meet. We can change the topological configuration locally such that one pseudo-line of these three pseudo-lines is not incident with the meet of the other two. Locally meens that we have no other pseudo-line intersecting the triangle formed by the three pseudo-lines. We can get two different oriented triangles bounded by the corresponding 3 pseudo-lines at those points without changing the combinatorial configuration. A change of the orientation of such a triangle is called a mutation.
The oriented matroid does change this way, however, these changes are not considered to change a lot the topological configuration.
We define a graph in which the points are pseudo-line arrangements with a given number of elements and edges occur between pairs of pseudo-line arrangments when they differ just by one orientation of such a triangle of three pseudo-lines and when there is no pseudo-line intersecting this triangle. This graph is known as the mutation graph for uniform oriented matroids.
Figure 2: Topological (174) configuration
Definition 3.1. Mutation class of a topological configuration. We call such a mutation of the topological configuration that keep the combinatorial configuration invariant an ad-
J. Bokowski and R. Strausz: A manifold associated to a topological (nk ) -configuration 483
missible mutation, and we speak about the connected component of the mutation graph of topological realizations generated via admissible mutations and call it the mutation class of a topological configuration.
4 Cycle length vector of the associated manifold
Definition 4.1. Cycle length vector. We calculate all cycle lengths of a configuration manifold, we sort these lengths in increasing order to obtain what we call the cycle length vector of the configuration.
From the definition it is clear that the cycle length vector does not change when we relabel the pseudo-lines, it is invariant under relabeling the configuration.
For example, the three (geometric) (93) configurations (93)i, (93)2, and (93)3, compare [8], Figure 2.2.1, have different cycle length vectors (6, 6,14,14,14), (3, 3, 3,3,3, 3, 3,33), and (3,3,3,14,14,14), respectively. When we have another geometric version of one of these drawings, we can tell via the cycle length vector which version we have. We have depicted the second case in Figure 3. The cycles of length 3 are easily seen. The reader can verify that there is only one additional final cycle of length 33.
The cycle length vector provides us with a short invariant of a topological configuration. It has turned out that it can e.g. distinguish all different 17 mutation classes of (184) configurations. We present all these 17 cycle length vectors in Table 1, listed in the order in which the examples were presented in [7]. The last vector in Table 1 is the cycle length vector of the additional topological configuration that was found recently when all mutation classes of topological (184) configurations were generated, see [4]. In Figure 4 you see the new topological example, on the right, together with the former known combinatorially isomorphic Case 5.
Figure 3: Geometric (93)2 configuration
402
Ars Math. Contemp. 7 (2014) 379-187
[3,3,8,8,8,8,8,13,13,13,13,13,33], [3,3,3,3,3,3,8,8,8,18,28,28,28], [3,3,8,18,18,45,49], [3,3,3,3,44,44,44], [3,3,8,8,10,13,13,13,13,29,31], [5,5,8,8,8,8,8,8,8,8,8,31,31], [3,3,3,8,28,45,54], [3,3,12,13,13,13,13,13,13,48], [8,13,13,13,13,13,18,19,34], [8,13,13,13,13,13,13,18,40], [3,3,12,13,13,13,13,34,40], [3,8,13,13,13,13,18,29,34], [3,5,8,8,8,8,8,13,13,13,57], [3,3,8,8,8,8,13,13,18,29,33], [3,8,8,8,13,13,13,13,13,13,13,13,13], [3,3,3,3,3,3,18,18,18,18,18,18,18], [3,3,3,13,24,98].
Table 1: All possible cycle length vectors for topological (184) configurations.
Figure 4: Two topological (184) configurations with an isomorphic combinatorial configuration
5 Properties of the configuration manifold
Before we write the next theorem with properties of configuration manifolds, we wish to mention [6], i.e., another paper with a link between pseudo-line arrangements and topological graph theory.
Theorem 5.1. Properties of configuration manifolds.
1.	Configuration manifolds are non-orientable 2-manifolds.
2.	The configuration manifold of a topological configuration determines its combinatorial configuration.
3.	The configuration manifold of a topological configuration is an invariant of its mutation class.
Proof. Ad 1: Since we work in the non-orientable projective plane, we can go along the Mobius strip of any closed pseudo-line of the arrangement. This Mobius strip is a part of the configuration manifold. So the configuration manifold is non-orientable.
Ad 2: In the definition of the configuration manifold we have the information of all circular sequences of points along each pseudo-line. We only have to follow all straight ahead paths along the edges. This is the information of the combinatorial configuration.
J. Bokowski and R. Strausz: A manifold associated to a topological (nk ) -configuration 483
Ad 3: The definition of a mutation class tells us that the configuration manifold does not change when an admissible mutation changes the topological configuration. The construction of the manifold simply ignores those intersections of pseudo-lines that do not occur at points of the configuration.	□
Remarks: 1. A combinatorial configuration which admits topological configurations can have different configuration manifolds. This property was already shown via Figure 4.
2. The cycle length vector can be used to distinguish all 17 connected admissible mutation graph components in the (184) case. The list of cycle length vectors in Table 1 together with the result of the generation algorithm of topological configurations, presented in [4], provides us with this property.
Our cycle length vector of a configuration manifold has already been tested as an invariant in the classification of [5] that was based on [4] . An algorithm was used for generating all topological (nk ) configurations in the projective plane for given n and given k without determining first all corresponding abstract (nk) configurations.
The (184) case (JAVA code of V. Pilaud with one hour CPU-time) had mainly the character of confirming the satisfiability result of Lars Schewe, [9], however, the case of Figure 4 appeared as a surprising additional aspect. The behavior of the (194) case (JAVA code with 16 days of CPU-time) was completely different. Here we had to sort the output of nearly 70,000 mutation classes of topological (194) configurations, i.e., topological configurations up to mutation equivalence. For this investigation additional techniques are useful and the presented invariant here was only one intermediate step within this investigation. A detailed report about this (194) case can be found in [5].
References
[1]	A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler, Oriented Matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999.
[2]	J. Bokowski, Computational Oriented Matroids, Cambridge University Press, Cambridge, 2006.
[3]	J. Bokowski, B. Griinbaum and Lars Schewe, Topological configurations (n4) exist for all n > 17, Eur. J. Comb. 30 (2009), 1778-1785.
[4]	J. Bokowski and V. Pilaud, Enumerating topological (nk)-configurations, Computational Geometry: Theory and Applications 47 (2014), 175-186, special issue for the 23rd Canadian Conference on Computational Geometry, available via arXiv.
[5]	J. Bokowski and V. Pilaud, On topological and geometric (194)-configurations, 13p., 2013 submitted, available via arXiv.
[6]	J. Bokowski and T. Pisanski, Oriented matroids and complete graph embeddings, Journal of Combinatorial Theory Series A 114 (2007), 1-19.
[7]	J. Bokowski and L. Schewe, On the finite set of missing geometric configurations (n4), Computational Geometry: Theory and Applications 46 (2013), 532-540.
[8]	B. Grunbaum, Configurations of Points and Lines, Graduate Studies in Mathematics, vol. 103, American Mathematical Society, Providence, RI, 2009.
[9]	Lars Schewe, Satisfiability Problems in Discrete Geometry, PhD thesis, Shaker, Technische Uni-versitat Darmstadt, 2007.