Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 235–241
The combinatorial (194) configurations
Octavio Páez Osuna , Rodolfo San Agustı́n Chi
Department of Mathematics, Faculty of Sciences
National Autonomous University of Mexico (UNAM)
4510 Mexico DF, Mexico
Received 17 June 2010, accepted 18 November 2011, published online 22 March 2012
Abstract
A parallel backtrack search is carried out to classify, up to isomorphism, all combina-
torial (194) configurations. A total of 269 224 653 such configurations were found. We
prove that two of the combinatorial (194) configurations are not geometrically realizable
over any field. Also we confirmed the computation of the 971 171 combinatorial (184)
configurations which lacked an independent verification.
Keywords: (194)-configurations, symmetric designs, finite geometries, AMDS-Code, parallel back-
tracking search with isomorph rejection.
Math. Subj. Class.: 05B25, 14N20, 62K10, 68P10, 94B05.
1 Introduction
A combinatorial (vk) configuration is an incidence structure consisting of a set of v points
and b blocks such that each block is incident with exactly k points and each point is incident
with exactly k blocks. We also require that every pair of points is incident with at most one
block.
In this paper we are interested in the enumeration of all combinatorial configurations
with v = 19 and k = 4, which is an open problem. Our approach is computational by
means of a parallel search algorithm that generates, up to isomorphism, all combinatorial
(194) configurations.
Very often combinatorial (vk) configurations appear as theorems in geometry; for ex-
ample, the fundamental Theorems of Pappus and Desargues give rise to (93) and (103)
configurations. Conversely, for given v and k, it is interesting to investigate which (vk)
configurations are geometrically realizable as a set of points and lines in some projective
plane over a field, and which of those correspond to geometric theorems; that is, geometric
E-mail addresses: opo@hp.fciencias.unam.mx (Octavio Páez Osuna), rodolfomeister@ciencias.unam.mx
(Rodolfo San Agustı́n Chi)
Copyright c© 2012 DMFA Slovenije
236 Ars Math. Contemp. 5 (2012) 235–241
realizations for which the last incidence is given by a theorem. Also it is interesting to find
combinatorial (vk) configurations which cannot be realized over any projective space. We
were able to find two configurations which cannot be geometrically realized over any field.
The enumeration of combinatorial (vk) configurations is also important because they
are the building blocks of more complex combinatorial structures such as block designs.
The enumeration of combinatorial structures has recently received a lot of attention due to
the diversity of its applications, from theorems in geometry and the design of experiments
to the theory of error correcting codes and cryptology (see [4]). We were able to construct
an error correcting code by embedding a combinatorial (194) configuration over the finite
projective space PG(3, 67).
2 Computational search
We label the points of our combinatorial configurations with the symbols 0, 1, . . . , 18. The
pencil at a point P in a configuration, consists of the set of blocks incident with P along
with the points they contain.
Each configuration is initialized with the pencil at point 0. Then there are, up to iso-
morphism, five ways to add a fifth block (see Figure 1).
Figure 1: The five initial figures.
We call these five figures P1, P2, P3, P4, P5 the initial figures. They define an ordering
in the search tree. That is, when processing figure Pi, for 1 < i ≤ 5 we only allow adding
blocks which yield configurations that do not contain subconfigurations isomorphic to Pj
for 1 ≤ j < i.
We construct the configurations block by block. The decision to be made is which block
should be added to the configuration being constructed. For each point in the configuration
incident with less than 4 blocks, there is a fixed number of legal options for adding a block
which is incident with it. We compute the number of options for each point, and we try
to add a block that is incident with a point with the minimum number of options. Also a
check is performed to find points in the configuration with 4− s incidences with less than
s options for an incident block. In the case there is at least one such point the configuration
is not considered any further. This is a simple test that detects several configurations early
O. Páez Osuna and R. San Agustı́n Chi: The combinatorial (194) configurations 237
|Aut(C)| Frequency
1 269195473
2 28474
3 492
4 172
6 32
8 5
12 3
18 2
Total 269224653
Table 1: Frequency of sizes of automorphism groups of combinatorial (194) configurations.
in the search tree that cannot be completed to a combinatorial (194) configuration and does
not need to look exhaustively for all completions.
Due to the sizes of the search subtrees and computational infrastructure constraints, we
found out that the enumeration was feasible if the partial configurations were distributed
into several processors after 10 blocks have been added. We used a master/slave parallel
model. Each slave processor attempts all possible completions of these partial configura-
tions into a (194) configuration and creates a database of completed configurations. At the
end, all these databases are merged by the master processor to eliminate possible isomor-
phic configurations.
To further reduce the search tree, we performed partial isomorph rejection at each level,
using NAUTY (see [9]), to avoid the processing of isomorphic subproblems. Most of these
ideas were adapted to our case from the fast backtracking principles found in ([10]).
After 39 182 hours of computation using the supercomputer KanBalam we found 269
224 653 nonisomorphic combinatorial (194) configurations. With our parallel approach
the entire search took only 70 days. Our algorithm was tested for correctness against the
known values of nonisomorphic combinatorial (v4) and (v3) configurations. In particular,
we confirm the known counting of 971 171 combinatorial (184) configurations, (see [1],
[2] and [3]), which lacked an independent verification.
Table 1 lists the possible sizes of the automorphism groups of the (194) configurations
and their frequency.
3 The two combinatorial (194) configurations with largest automor-
phism group.
Let C be the combinatorial (194) configuration defined by block set given in Table 2.
The automorphism group of C has order 18. Such a group is generated by the following
3 generator set:
{(1, 15, 16)(2, 10, 14)(3, 13, 7)(4, 8, 12)(5, 11, 9)(17, 0, 18),
(2, 3)(7, 10)(8, 12)(9, 11)(13, 14)(15, 16),
(2, 10, 14)(3, 7, 13)(4, 5, 0)(8, 11, 18)(9, 17, 12)}
However,
Theorem 3.1. C is not geometrically realizable over any field.
238 Ars Math. Contemp. 5 (2012) 235–241
a b c d e f g h i j k l m n o p q r s
0 0 0 0 1 1 1 2 2 2 3 3 3 4 4 6 6 7 10
1 4 7 10 4 5 6 5 7 12 5 8 9 9 11 8 9 14 13
2 5 8 11 7 13 15 8 11 13 12 14 10 14 13 11 12 16 15
3 6 9 12 10 14 16 17 15 16 18 15 16 18 17 18 17 17 18
Table 2: The first (194) configuration with largest automorphism group.
Proof. Consider the following partial realization of C over P2(k), the projective plane over
the field k:
1. Choose the points 4, 6, 9 and 10 generic in P2(k). So, these points define the lines
e = 4 10, m = 9 10, n = 4 9, and q = 6 9.
Note that the symbols 6 and 10 do not share a block on C and so, we do not consider
the corresponding line in P2(k). Also, although the symbols 4 and 6 belong to the
block b in C, we do not need block b for this argumentation.
2. Choose the points 1 in e, 18 in n, and 17 in q also generic on their respective lines.
These choices define now the lines g = 1 6, o = 4 17, p = 6 18, and s = 10 18.
3. Consider the following intersection points: 11 := p ∩ o, 16 := g ∩m, and 15 := g ∩ s,
and the lines i = 11 15 and r = 17 16.
4. Finally, consider the point 7 := r ∩ i.
Since the symbols 4, 7, and 10 belong to the block e of C, then the point 7 must also
belong to the corresponding line e. If C were geometrically realizable over P2(k), then the
points (except the point labeled 1) and lines considered in this construction would constitute
a (103) geometric configuration C′ in P2(k) (see Figure 2).
18
9
11
15
16
17
6
7
e
10
1
4
Figure 2: The point 7 does not belong in the line e.
O. Páez Osuna and R. San Agustı́n Chi: The combinatorial (194) configurations 239
Glynn’s A B C D E F G H I J
C′ 7 10 4 16 15 18 11 9 17 6
Table 3: Correspondence between Glynn’s construction and C′.
Actually, C′ would be the non-realizable (103) combinatorial configuration: In ([5], fig.
2 p. 73), D.G. Glynn gives all the incidences for this structure and the correspondence in
this paper’s Table 3 gives an isomorphism between them.
The following block set D corresponds to the other combinatorial (194) configuration
with automorphism group of order 18:
0 0 0 0 1 1 1 2 2 2 3 3 3 4 4 5 5 6 6
1 4 7 10 4 5 6 7 8 9 10 11 12 7 8 7 9 8 9
2 5 8 11 13 15 17 13 14 16 13 14 15 10 11 12 11 12 10
3 6 9 12 14 16 18 15 17 18 18 16 17 16 18 14 17 13 15
One might proceed as in the former case or, alternatively, consider the following sub-
structure of D:
0 0 0 1 1 7 3 3 4 5
1 4 10 4 5 13 10 12 7 7
3 5 12 13 15 15 13 15 10 12
which also corresponds to the non-realizable (103) combinatorial configuration. This is so
because both structures have the 6I + 0V + 44 restfigur scheme (see ([7]), table 2.2.8 p.
74), which, in turn, is characteristic of such a configuration.
4 Embedding configurations in PG(k − 1, q) and codes
Let q be a prime power. An Fq−linear error correcting code C of length n is an Fq−linear
subspace of Fnq . The elements of C are called words. The weight wt(x) of a word x in C
is the number of its non-zero coordinates. The minimum weight d of the code C is defined
as the minimum of the weights of non-zero words occurring in C. For x, y ∈ C, we define
the Hamming distance d(x, y) between x and y as wt(x− y). It follows that
d = min{d(x, y)|x, y ∈ C, x 6= y}
and d is called the minimum distance of C. If k is the dimension of C as a vector space
over Fq , then we say that C is a
[n, k, d]q
error correcting code. It is known that the parameters of a code C satisfy
n+ 1 ≥ k + d.
The above inequality is called the singleton bound. A code satisfying the previous inequal-
ity with equality is called a maximum distance separable code, or simply a MDS-Code.
The singleton defect s of a code C is defined as
s = n+ 1− k − d.
240 Ars Math. Contemp. 5 (2012) 235–241
A code with s = 1 is called an almost maximum distance separable code, or simply AMDS-
code. See [8] for more on Coding Theory.
In our context, embedding a (vk) configuration in PG(k − 1, q) means finding a set
of v points and v hyperplanes in PG(k − 1, q) that preserve incidence in the configuration
(see [6]). By embedding a combinatorial (vk) configuration in PG(k− 1, q), we construct
a linear error correcting code C as the linear Fq-span of the rows of the matrix G whose
v columns contains the coordinates of the v points of the configuration. If the embedding
is such that no hyperplane of PG(k − 1, q) contains more than k points of the embedded
configuration, then C has length v, dimension k and minimum distance v − k. Note that
these parameters indicate that the code C is an AMDS code.
5 An example over F67
Let C be the (194) configuration defined by the following block set:
0 0 0 0 1 1 1 2 2 2 3 3 3 5 6 7 8 9 10
1 4 7 10 4 5 6 4 5 12 4 6 7 9 9 13 12 11 14
2 5 8 11 7 8 11 15 10 13 17 8 11 16 12 14 14 13 15
3 6 9 12 10 13 14 16 17 18 18 15 16 18 17 17 16 15 18
An embedding of the points of the configuration in PG(3, 67) is given by the columns
of the following matrix:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
35 56 61 66 28 43 11 59 27 4 57 35 14 52 42 19 64 42 7
46 3 41 42 27 17 20 57 38 24 10 32 20 2 15 22 38 47 60
15 21 15 27 26 11 31 41 54 42 26 18 17 59 4 38 62 36 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
The code spanned by the rows of the previous matrix has parameters [19, 4, 15]67 which is
an AMDS linear code with 3564 words of weight 15.
6 Acknowledgements
The authors acknowledge the support of DGSCA, UNAM, for the use of the supercomputer
KanBalam. We thank J. Bokowski for all his encouragement during his 2009–2010 visit to
UNAM for the completion of this work. We also thank the referees for all their valuable
comments which clarified the presentation of the manuscript.
References
[1] A. Betten and D. Betten, Tactical decompositions and some configurations (v4), J. Geometry
66 (1999), 27–41.
[2] A. Betten, G. Brinkmann and T. Pisanski, Counting Symmetric Configurations v3, Discrete
Applied Math. 99 (2000), 331–338.
[3] M. Boben, B. Grünbaum and T. Pisanski Small triangle-free configurations of points and lines,
Discrete and Computational Geometry 35 (2006), 405–427.
[4] C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chap-
man and Hall/CRC, 2007.
O. Páez Osuna and R. San Agustı́n Chi: The combinatorial (194) configurations 241
[5] D. G. Glynn, On the Anti-Pappian 103 Construction, Geometriae Dedicata 77 (1999), 71–75.
[6] D. G. Glynn, A Note on nk Configurations and Theorems in Projective Space, Bull. Austral.
Math. Soc. 76 (2007), 15–31.
[7] B. Grünbaum, Configurations of Points and Lines, Graduate Studies in Mathematics, vol. 103,
AMS, 2009.
[8] F. J. MacWilliams and J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland,
1977.
[9] B. D. McKay, NAUTY User’s Guide (version 1.5), Technical Report TR-CS90-02, Computer
Science Department, Australian National University, 1990.
[10] B. D. McKay, W. Myrvold and J. Nadon, Fast Backtracking Techniques Applied to Find New
Cages, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San
Francisco, CA, 1998.
[11] R. San Agustı́n Chi, On Cayley’s Projective Configurations. An Algorithmic Study, in: N. L.
White (ed.), Invariant Methods in Discrete and Computational Geometry, Kluwer, 1995, 289–
299.