Paramodifications of unitals

Paper

In the paper New Steiner systems from old ones by paramodifications we described the possibility to modify a 2-design \(D\) by redefining the parallelism of blocks, intersecting a fixed block \(b\). This modification is called \((\chi,b)\)-paramodification.

We applied this method to construct new unitals of order 3 and 4. On this home page, we present the computational results and their implementations in the computer algebra system GAP, and its package UnitalSZ.

Unital classes and paramodification graphs

Define two graphs \(\Psi_3\) and \(\Psi_4\), whose vertices are all unitals of respective orders, up to isomorphism. Two vertices are connected if and only if the corresponding unitals are paramodifications of each other. We have the following known classes of unitals:

• BBT has 909 and KRC has 4466 unitals of order 3. The intersection of BBT and KRC contains 722 unitals of order 3.
• KNP has 1777 unitals of order 4.

We studied the connected components of \(\Psi_3\) and \(\Psi_4\) which contain at least one vertex from the classes BBT, KRC or KNP.

GAP implementation

See the GAP worksheet for an implementation of the paramodification method. It requires the GAP package UnitalSZ.

You may experiment with

• the source file of the GAP worksheet,
• the computed parts of \(\Psi_3\) and \(\Psi_4\) in graph6 and sparse6 format,
• the vertex labelings psi3-vertex-names.g and psi4-vertex-names.g which identifies the GAP objects and the vertices.

Run-times

The computing of all paramodification of a unital of order \(q\) can be reduced to compute the proper \(q+1\)-coloring of a simple graph with \((q+1)(q^2-1)\) vertices. This can be done by the independent set cover method, or by different integer linear programs (ASS, POP, POP2). We have timed the run-time of finding all possible (non-isomorphic) \((\chi,b)\)-paramodifications of a unital (and it’s) block for 30 random unitals of order 4 (from the KNP library) and random blocks (the measurements are in milliseconds):

The computed components of \(\Psi_3\)

• Visualization of the connected components of \(\Psi_3\) with at least two vertices, containing BBT or KRC unitals.
• In this way we obtained 173 new unitals of order 3.
• The red edges can be obtained only by paramodification, while the regular (black) edges can be obtained also by considering only switching (a special case of paramodification).

The computed components of \(\Psi_4\)

Some general information (for further details see the table below):

• There are 1458 isolated KNP unitals
• There are 87 ‘small’ components (these only have nodes at most in \(V_1\))
• We have computed 61 ‘large’ components (these have at least one node in \(V_2\)), 59 of them are fully computed
• 2 are stub components
• There are 16518 unfinished vertices
• There are at least 1605 and at most 1606 components
• In 8 components we have found other KNP unitals apart from the ones in \(V_0\)
• We have found 36878 new unitals
• There are no new unitals in 2 components

Incomplete components of \(\Psi_4\)

Are there any isomorphic nodes between the computed stub components of the graph? F stands for false, T for true and X marks the “border” of the table (the relation is symmetric).

The growth of the graph \(\Psi_4\)

The number of the unitals found on different levels of our breadth first search. The incomplete components are denoted by red.