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 sparse6 format,
the vertex labelings vertex-names-psi3.g and vertex-names-psi4.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 propert \(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):

method	minimum	q1	median	mean	q3	maximum
clique	86	118.50	145.5	142.2333	152.25	316
scip_ass	474	2245.50	2739.0	3368.9333	3673.50	9804
scip_pop	532	2111.50	3045.0	4082.1000	4533.50	12266
scip_pop2	519	2245.25	3096.5	4443.5667	5116.00	14707

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 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\)), 55 of them are fully computed
6 are stub components
There are 12610 unfinished vertices
There are at least 1601 and at most 1606 components
In 8 components we have found other KNP unitals apart from the ones in \(V_0\)
We have found 25641 new unitals
There are no new unitals in 2 components

id	compsize	knps	fullcomp	new	img.link
1-8-etc	7596	8	FALSE	7588	img
2	2	2	TRUE	0	NA
3	4	1	TRUE	3	img
4	3	1	TRUE	2	img
5	2	1	TRUE	1	img
6-50	13	2	TRUE	11	img
7-61	160	5	TRUE	155	img
9-26	55	2	TRUE	53	img
10	3	1	TRUE	2	img
11	4	1	TRUE	3	img
12	5	1	TRUE	4	img
15	3	1	TRUE	2	img
16	4	1	TRUE	3	img
18	4	1	TRUE	3	img
19	5	1	TRUE	4	img
20	2	1	TRUE	1	img
22-58-62	404	3	TRUE	401	img
23	21	1	TRUE	20	img
24	44	1	TRUE	43	img
27	4	1	TRUE	3	img
28	12	1	TRUE	11	img
34-57	401	14	TRUE	387	img
40	7	1	TRUE	6	img
41	3	1	TRUE	2	img
42	8	1	TRUE	7	img
43	62	1	TRUE	61	img
44	162	1	TRUE	161	img
45	3	1	TRUE	2	img
47	5	1	TRUE	4	img
48	5	1	TRUE	4	img
49	3	1	TRUE	2	img
52	3	1	TRUE	2	img
53	9	1	TRUE	8	img
54	3	1	TRUE	2	img
56	36	1	TRUE	35	img
59	226	1	TRUE	225	img
60	5	1	TRUE	4	img
63	2	1	TRUE	1	img
64	5	1	TRUE	4	img
66	3	1	TRUE	2	img
67	3	1	TRUE	2	img
69	2	1	TRUE	1	img
70-1629-etc	3487	6	FALSE	3481	img
341	2	1	TRUE	1	img
1420-1421-etc	185	18	TRUE	167	img
1424-1429-etc	1342	22	FALSE	1320	img
1425-1426-etc	986	22	TRUE	964	img
1427-1476	10	2	TRUE	8	img
1428	3	2	TRUE	1	img
1430-1489-1530	8	3	TRUE	5	img
1434-1435-etc	264	16	TRUE	248	img
1437-1439-1546-1548	19	4	TRUE	15	img
1444-1446-etc	432	10	TRUE	422	img
1445	4	4	TRUE	0	NA
1447	2	1	TRUE	1	img
1450	2	1	TRUE	1	img
1451-1461-1471	8	3	TRUE	5	img
1456	2	1	TRUE	1	img
1459	3	1	TRUE	2	img
1460	46	1	TRUE	45	img
1463	2	1	TRUE	1	img
1475	7	1	TRUE	6	img
1479-1498-1539	8	3	TRUE	5	img
1484	4	1	TRUE	3	img
1494	2	1	TRUE	1	img
1496	2	1	TRUE	1	img
1503	10	1	TRUE	9	img
1506	2	1	TRUE	1	img
1508-1509	1478	4	FALSE	1474	img
1515	2	1	TRUE	1	img
1518	7	1	TRUE	6	img
1524-1528	268	2	TRUE	266	img
1526	2	1	TRUE	1	img
1533	2	1	TRUE	1	img
1536	2	1	TRUE	1	img
1543	7	1	TRUE	6	img
1550	155	1	TRUE	154	img
1552	8	1	TRUE	7	img
1556	4	1	TRUE	3	img
1563-1564-1566-1575-1579	4035	5	FALSE	4030	img
1567	2	1	TRUE	1	img
1569	2	1	TRUE	1	img
1570	2	1	TRUE	1	img
1571-1572-1576	22	3	TRUE	19	img
1573	4	1	TRUE	3	img
1581	2	1	TRUE	1	img
1582	3	1	TRUE	2	img
1583-1584	13	2	TRUE	11	img
1585	2	1	TRUE	1	img
1592	514	13	TRUE	501	img
1594	2	1	TRUE	1	img
1595	2	1	TRUE	1	img
1597	4	1	TRUE	3	img
1598	4	1	TRUE	3	img
1602	3	1	TRUE	2	img
1605	2	1	TRUE	1	img
1606	2	1	TRUE	1	img
1614	3	1	TRUE	2	img
1615	3	1	TRUE	2	img
1616	3	1	TRUE	2	img
1617	3	1	TRUE	2	img
1622	2	1	TRUE	1	img
1623	2	1	TRUE	1	img
1624	2	1	TRUE	1	img
1625-1652	43	3	TRUE	40	img
1630-1759	164	2	TRUE	162	img
1633	2	1	TRUE	1	img
1634	2	1	TRUE	1	img
1635	4	1	TRUE	3	img
1636	2	1	TRUE	1	img
1637	4	1	TRUE	3	img
1641	9	1	TRUE	8	img
1645	19	1	TRUE	18	img
1647	2	1	TRUE	1	img
1649	2	1	TRUE	1	img
1653	2	1	TRUE	1	img
1657	2	1	TRUE	1	img
1658	2	1	TRUE	1	img
1663	324	10	TRUE	314	img
1673	5	1	TRUE	4	img
1674	13	1	TRUE	12	img
1676	2	1	TRUE	1	img
1679	2	1	TRUE	1	img
1692	13	3	TRUE	10	img
1693	2	1	TRUE	1	img
1694	3	1	TRUE	2	img
1696	3	1	TRUE	2	img
1701	3	1	TRUE	2	img
1702	2	1	TRUE	1	img
1703	3	1	TRUE	2	img
1706	3	1	TRUE	2	img
1710	2	1	TRUE	1	img
1717	2	1	TRUE	1	img
1718	2	1	TRUE	1	img
1723	2	1	TRUE	1	img
1726	2	1	TRUE	1	img
1729	2	1	TRUE	1	img
1731	2	1	TRUE	1	img
1736	3	1	TRUE	2	img
1737	2	1	TRUE	1	img
1749	11	2	TRUE	9	img
1750-1751-1752	2557	3	FALSE	2554	img
1755	2	1	TRUE	1	img
1757	2	1	TRUE	1	img
1758	2	1	TRUE	1	img
1772	3	1	TRUE	2	img
1774	3	1	TRUE	2	img
1777	3	1	TRUE	2	img

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).

	1-8-etc	70-1629-etc	1424-1429-etc	1508-1509	1563-1564-1566-1575-1579	1750-1751-1752
1-8-etc	X	F	F	F	F	F
70-1629-etc		X	F	F	F	F
1424-1429-etc			X	F	F	F
1508-1509				X	F	F
1563-1564-1566-1575-1579					X	F
1750-1751-1752						X

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.

id	v0	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17
1-8-etc	8	45	425	7118	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
2	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
4	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
6-50	2	9	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
7-61	2	5	7	5	11	22	26	21	20	17	14	9	1	0	0	0	0	0
9-26	2	14	13	26	0	0	0	0	0	0	0	0	0	0	0	0	0	0
10	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
11	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
12	1	4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
15	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
16	1	2	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
18	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
19	1	2	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
20	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
22-58-62	3	13	20	25	23	33	59	92	136	0	0	0	0	0	0	0	0	0
23	1	4	5	6	3	2	0	0	0	0	0	0	0	0	0	0	0	0
24	1	11	20	8	4	0	0	0	0	0	0	0	0	0	0	0	0	0
27	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
28	1	4	7	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
34-57	2	6	16	24	30	38	39	34	41	33	22	9	21	39	36	11	0	0
40	1	6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
41	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
42	1	6	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
43	1	12	21	14	14	0	0	0	0	0	0	0	0	0	0	0	0	0
44	1	4	6	10	8	20	19	16	18	31	23	2	2	1	1	0	0	0
45	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
47	1	4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
48	1	1	2	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
49	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
52	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
53	1	3	5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
54	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
56	1	5	10	14	6	0	0	0	0	0	0	0	0	0	0	0	0	0
59	1	5	13	21	32	57	50	32	11	3	1	0	0	0	0	0	0	0
60	1	2	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
63	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
64	1	1	2	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
66	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
67	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
69	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
70-1629-etc	6	28	445	3008	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
341	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1420-1421-etc	18	57	102	8	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1424-1429-etc	22	112	305	650	100	104	49	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
1425-1426-etc	22	91	276	597	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1427-1476	2	3	3	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1428	2	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1430-1489-1530	3	4	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1434-1435-etc	16	68	172	8	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1437-1439-1546-1548	4	5	4	6	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1444-1446-etc	10	32	111	268	11	0	0	0	0	0	0	0	0	0	0	0	0	0
1445	4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1447	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1450	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1451-1461-1471	3	4	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1456	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1459	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1460	1	5	11	15	14	0	0	0	0	0	0	0	0	0	0	0	0	0
1463	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1475	1	2	2	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1479-1498-1539	3	4	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1484	1	2	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1494	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1496	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1503	1	3	3	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1506	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1508-1509	2	34	335	890	101	39	77	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
1515	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1518	1	2	2	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1524-1528	2	33	233	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1526	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1533	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1536	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1543	1	2	2	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1550	1	2	6	36	70	35	5	0	0	0	0	0	0	0	0	0	0	0
1552	1	2	3	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1556	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1563-1564-1566-1575-1579	5	35	137	329	800	1311	1418	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
1567	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1569	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1570	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1571-1572-1576	3	4	7	4	4	0	0	0	0	0	0	0	0	0	0	0	0	0
1573	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1581	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1582	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1583-1584	2	5	6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1585	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1592	1	3	3	7	23	51	46	41	36	34	48	69	51	27	38	22	12	2
1594	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1595	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1597	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1598	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1602	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1605	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1606	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1614	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1615	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1616	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1617	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1622	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1623	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1624	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1625-1652	2	4	9	9	11	7	1	0	0	0	0	0	0	0	0	0	0	0
1630-1759	2	7	30	49	50	18	7	1	0	0	0	0	0	0	0	0	0	0
1633	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1634	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1635	1	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1636	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1637	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1641	1	2	5	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1645	1	1	2	5	5	4	1	0	0	0	0	0	0	0	0	0	0	0
1647	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1649	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1653	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1657	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1658	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1663	1	4	9	7	25	49	18	24	41	14	17	25	23	8	22	24	13	0
1673	1	4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1674	1	4	5	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1676	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1679	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1692	1	1	2	2	3	2	2	0	0	0	0	0	0	0	0	0	0	0
1693	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1694	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1696	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1701	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1702	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1703	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1706	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1710	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1717	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1718	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1723	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1726	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1729	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1731	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1736	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1737	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1749	1	4	2	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0
1750-1751-1752	3	8	40	168	518	880	940	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA	NA
1755	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1757	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1758	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1772	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1774	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1777	1	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0