Configurations
Welcome to the Superfiguration Zoo, a tool for exploring the 163 key structures which appear in the formula for counting 10-arcs over small projective planes. The formula is the result of new work by Nathan Kaplan, Susie Kimport, Rachel Lawrence, Luke Peilen, and Max Weinreich.
In combinatorial geometry, a linear space is a way of encoding incidence data for a set of points and lines. For instance, an n-arc is a set of ten points in a projective plane, no three of which are collinear. For another example, a Fano plane is a set of seven points and seven lines such that each point belongs to three of the lines and each line contains three points. The combinatorial information given here is free of any particular projective plane as the setting; rather, we have only said which lines contain which points. This data constitues a linear space. These linear spaces may or may not arise as subsets of particular projective planes.
As shown by D. Glynn, one may count arcs in terms of realizations of certain highly determined linear spaces which we term superfigurations, following B. Grunbaum. A linear space is called a superfiguration if it obeys the following two rules:
(1) Every point lies on at least three lines.
(2) Every line contains at least three points.
In more quotidian terms, a superfiguration is a bipartite graph with the parts marked "points" and "lines" such that
(1) there are up to ten "points"
(2) each vertex is degree at least 3
(3) there are no 4-cycles.
The smallest superfiguration is the Fano plane, which contains 7 points. Next is the Mobius-Kantor configuration, containing 8 points. Glynn found expressions for n-arcs up to n = 8 in terms of these two superfigurations. Glynn also identified the ten superfigurations on 9 points. Iampolskaia, Skorobogatov, and Sorokin used these superfigurations to count 9-arcs in projective planes over finite fields. In our paper, we extend that result to count 9-arcs in non-Desarguesian planes. We then find all 151 superfigurations on 10 points, which form the ingredients of the corresponding 10-arcs formula. Thus, by understanding all 163 superfigurations assembled here, one can appreciate the subtlety involved in counting arcs - a wonderful example of how simple structures may give rise to complex phenomena.
Exploring the Zoo
Click the Configurations link to start exploring. For each superfiguration, first we give the incidence data defining the superfiguration. We list the final polynomial system for that superfiguration, the degree of the polynomial system, and the dimension of the quasi-projective variety defined by that polynomial system. Then we give the size of the automorphism group. To help with heuristic understanding, we give counts for how many realizations that superfiguration has on finite projective planes up to order 19. Particularly interesting cases, such as the Desargues configuration, have bold links.
Methodology
Classical lists existed of superfigurations on up to nine points. To identify ten-point superfigurations, we used McKay's graph theory library Nauty via the programming language Sage, and confirmed the results by hand and via computational methods. The superfigurations were stored in a Sage program in terms of their Levi graphs.
The automorphism groups were then calculated using Sage's graph library, adjusting to ensure that only automorphisms which preserved the distinction between points and lines were considered.
To count realizations over small projective planes, we wrote a program which brute-force searches a projective plane for all point subsets which have the collinearity rules encoded by the superfiguration. We do not count weak realizations, that is, sets of points which satisfy additional collinearity relations. Following Iampolskaia, Skorobogatov, and Sorokin, we count these realizations up to projective equivalence. This means that the first four points are assumed to be [1:0:0], [0:1:0], [0:0:1], and [1:1:1]. To translate this into a count of strong realizations, one multiplies by the number of 4-arcs in the projective plane. For more information, see Iampolskaia, Skorobogatov, and Sorokin. We count up to order 19 because the search in order 23 had a prohibitively long runtime.
To understand the relevance of the polynomial systems and how they were obtained, see our paper.