# Classification of Triangle-Free223 Configurations

Authors: Abdullah Al-Azemi; Anton Betten
Journal: International Journal of Combinatorics
 (2010)

---

## Abstract

The 157, 211 triangle-free symmetric223 configurations are classified and some of their
properties are examined. We conclude that each such configuration has a blocking set. Further
properties like transitivity on lines, self-duality, and self-polarity are discussed.


---

## Body

## 1. Introduction

Afinite incidence structure𝒳 is a pair (P,ℬ), where P and ℬ are finite sets. In particular, P={p1,p2,…,pv} is a set of  v  points and ℬ={B1,B2,…,Bb} is a set of  b  blocks (or lines) such that Bi⊆P for i=1,2,…,b.The number of blocks containing a pointp∈P is called the degree, denoted by [p]. The number of points that are contained in a block B is called the size of B, denoted by |B|. A pair (p,B) with p∈B∈ℬ is called a flag. In this case, we say that p lies on B, or that p and B are incident.A (combinatorial)configuration (see [1]) of type (vr,bk) is an incidence structure (P,ℬ) with (C1)
|Bj|=k for j=1,…,b,(C2)
[pi]=r for i=1,…,v,(C3)
any two distinct points being incident with at most one line.The last axiom implies that two points determine at most one line and that two lines intersect in at most one point. We say that two points arecollinear if they lie on a line (and two lines are concurrent if they intersect). Note that these structures are defined purely combinatorially (and hence sometimes called combinatorial configurations). It is a different question whether or not a given configuration can be embedded in projective space (such that the blocks arise from lines in that space). This question leads to the notion of geometric configurations. In this paper, we are concerned with combinatorial configurations only. We do not discuss the problem of whether or not they can be embedded in projective space. Clearly, every geometric configuration is also combinatorial. Therefore, the results in this paper may be seen as a starting point to classify the corresponding geometric configurations. For the sake of simplicity, henceforth we will simply talk about configurations. In all cases, this will mean combinatorial configurations.A(vr,bk) configuration with v=b (and hence r=k) is called symmetric (see for instance [2, 3]). A symmetric configuration is denoted by vr.Configurations are closely related to graphs. Let𝒞=(P,ℬ) be a v3 configuration. The Levi graph (or incidence graph), denoted L(𝒞), associated with 𝒞, is the cubic bipartite graph with vertex set P∪ℬ with p∈P and B∈ℬ adjacent if and only if p∈B; see [3–7]. Alternatively, it is the cubic bipartite graph with black vertices representing the points, with white vertices representing the lines, and with an edge joining two vertices if and only if the corresponding point and line are incident. According to Coxeter [4], configurations can be characterized in the following way. Recall that the girth in a graph is the length of the shortest cycle.Proposition 1.1.
An incidence structure𝒞 is a v3 configuration if and only if its Levi graph is cubic and has girth at least 6.Anisomorphism between two incidence structures 𝒞1=(P1,ℬ1) and 𝒞2=(P2,ℬ2) is a bijection α:P1→P2 which takes ℬ1 to ℬ2 (where α(B)={α(p)∣p∈B} for B∈ℬ1). If such an isomorphism exists, the incidence structures are isomorphic. It is well known that isomorphism of incidence structures is an equivalence relation. The equivalence classes are known as isomorphism types. The problem of classifying a class of incidence structures is determining the classes of isomorphic objects.Furthermore, for an incidence structure𝒞=(P,ℬ), the isomorphisms from 𝒞 to 𝒞 are known as automorphisms. They form a group, the automorphism group of 𝒞.IfG is any subgroup of the automorphism group of a configuration 𝒞, then G may be seen as acting on the set of points, the set of blocks, and the set of flags; see [8] for more details. An orbit of G on points, blocks, flags (resp.) is known as a point-orbit, block-orbit, flag-orbit (resp.). It is well known that a flag transitive automorphism group G is also transitive on points and blocks (but not conversely).Ablocking set in a configuration is a subset H of points such that each block contains at least one element from H and one element not from H. Not every configuration has a blocking set. An example of a blocking set free configuration is the unique 73 configuration (or Fano plane) shown in Figure 1. The figure also shows the Levi graph of this configuration. This graph is also known as the Heawood graph.The Fano plane and its Levi graph (Heawood graph).
(a)(b)To each(vr,bk) configuration 𝒞=(P,ℬ), we may associate another configuration known as the dual configuration. The dual configuration is 𝒞*=(ℬ,P), with the roles of points and blocks reversed, but with the same incidence. That is, a “point” B is on a “block” p in the dual configuration if p∈B in 𝒞. Clearly, 𝒞* is a (bk,vr) configuration. Also, 𝒞 and 𝒞* have the same Levi graph, except that the color classes are reversed. Applying duality twice in a row, we obtain a configuration 𝒟 that is isomorphic to the original configuration 𝒞.If𝒞 is isomorphic to its dual (𝒞*), we say that 𝒞 is self-dual and a corresponding isomorphism is called duality. Moreover, a duality of order 2 is called a polarity. A self-polar configuration is a configuration that admits a polarity. The Fano plane of Figure 1 is both self-dual and self-polar. To see this, notice that the bijective mapping pi↔Bi for i=1,2,…,7 preserves the Levi graph of the Fano plane.In this paper, we considerv3 configurations that contain no triangles. A triangle in a configuration is a triple of points that are pairwise collinear but not with the same line. A configuration is triangle-free if and only if the girth of the incidence graph is at least 8 (configurations in general have girth at least 6). In terms of points and lines, we have that a point p that is not on a line B is collinear to at most one point of B. This is a weakening of the axiom of a generalized quadrangle: in a generalized quadrangle, a point p not on a line B is collinear to exactly one point of B.So far, triangle-freev3 configurations have been classified for v≤21. In the current work, a classification for v=22 is carried out. Table 1 shows the known results of the nonisomorphic triangle-free v3 configurations for v≤22. The entries for v≤21 were determined previously in [8, 9]. The entries in the last row of Table 1 are new and were constructed in our search.Table 1
Triangle-free configurationsv3 for 15≤v≤22.
vABCDEF15111110160000001711100018422000191466000201624040110214,71330730310022157,2111,9991,992000Note:A is the number of configurations v3,B is the number of self-dual configurations v3,C is the number of self-polar configurations v3,D is the number of point-transitive configurations v3,E is the number of flag-transitive configurations v3, and F is the number of blocking set free configurations v3.


## 2. Search and Results

Necessary existence conditions for a(vr,bk) configuration are (2.1)vr=bk,v-1≥r(k-1),
obtained by counting in two ways the incidences of points with lines and the incidences of pairs of points containing a given point with lines, respectively. For k=3, these conditions are also sufficient; see Gropp [10].In this paper, we use computer search to classify the triangle-free223 configurations. We find exactly 157,211 nonisomorphic configurations of this type. Moreover, we also verified the results in [8] for triangle-free configurations v3 with at most 21 points.Gropp [3] has stated that there is a blocking set free 223 configuration. Our search shows that there is no blocking set free 223 configuration which is also triangle-free. Thus, Gropp's configuration must contain triangles.Av3 configuration (P,ℬ) with P={p1,…,pv} and ℬ={B1,…,Bv} can be represented by a {0,1} incidence matrix A=(ai,j), say, with v rows and v columns. The entry ai,j is one if and only if pi∈Bj. Clearly, there are three ones in each row and column. Also, the dot product of any two distinct rows is at most 1. Those properties are equivalent to those that were mentioned earlier in Section 1, namely, (C1), (C2), and (C3). Moreover, two matrices are isomorphic if one can be obtained from the other by permuting the rows and the columns. In the incidence matrices that are displayed below, we write “x” if ai,j=1 and “empty square” if ai,j=0.Let us now describe the algorithm that we use to classify the triangle freev3 configurations. The algorithm is an instance of the method of orderly generation [11].We carry out a row-by-row (or point-by-point) backtrack search over all incidence matrices of triangle freev3 configurations. We start with the all-zero matrix and augment it one row at a time, subject to the properties (C1), (C2), and (C3). Augmenting means deciding on the positions of the three ones in one particular row. The rows are augmented in order. Moreover, we use an algorithm from [12, 13] for testing the girth condition (of the partially filled incidence matrix). In this way, we ensure that all of the considered structures are triangle-free configurations. Once a row has been completed, one of two actions is taken. If the number of completed rows is between 17 and 21, no further action is taken. In the other cases, we perform a test whether or not the lexicographically least form of the incidence matrix agrees with the matrix that was created. If yes, we keep the row that was just added and proceed with the search. If no, the row is rejected and we backtrack. This test is our way to solve the isomorphism problem. Namely, each isomorphism class is represented by its lexicographically least representative. Since we perform this test after 22 rows, the resulting objects are pairwise nonisomorphic. The reason for not testing after rows 18, 19, and 20 is the following. Computing the lexicographically least incidence matrix is expensive. Therefore, the isomorphism test described above slows down the search quite a bit. The benefits of using the isomorphism test are worth the effort in the early rows (up to row 17). Namely, the isomorphism test keeps the number of possibilities down and thereby reduces the size of the search space. On the other hand, for rows 18–20, the number of possibilities of partial incidence matrices increases dramatically. We observe, however, that many of these matrices do not complete and hence do not contribute to the classification. Therefore, switching off the isomorphism test for rows 18–20 means that we do not spend time on classifying partial incidence matrices that do not complete anyway. This simple trick saves us a lot of time. In fact, we can classify the triangle free 223 configurations in about 19 hours CPU time (on a single CPU machine).We remark that we use our own algorithm to compute the lexicographically least representative of the isomorphism class of a matrix. The complexity of this algorithm is exponential in the size of the input. No fast algorithm to solve this problem is known.Alternately, the idea ofcanonical augmentation due to McKay [14] can be used. In this method, the lexicographically least representative is replaced by a canonical representative (that in almost all cases is different from the lexicographically least representative). We also tried this method, using nauty [15] to compute the canonical representative. We found that orderly generation using lexicographically least representatives worked better for us. This may not be seen as a critique of “canonical augmentation”. We simply did not try very hard, so a comparison is unfair. We remark that while canonical representatives of an isomorphism class may be computed faster than lexicographically least representatives, the procedure is still exponential. Again, no fast (i.e., polynomial) algorithm to solve this problem is known.



---

*Source: 767361-2010-09-16.xml*