Steiner quadruple systems with minimum colourable derived designs at the orders 38, 44, 62, 74, 86 and 92

Abstract

A Steiner quadruple system SQS(v) has minimum colourable derived designs — it is an mcDSQS(v), in the terminology of Tan and Zhou — when the derived Steiner triple system at every one of its v points partitions into the least possible number of partial parallel classes. For v ≡ 2 (mod 6) that number is v/2, and the existence of an mcDSQS(n) for all n ≡ 2 (mod 6), n ≥ 20, is Conjecture 2 of Shi, Xia and Krotov, where it is equivalent to a statement about diameter perfect constant-weight codes. The published orders are 20, 26, 32 and 2 · 9ᵐ+2; Tan and Zhou ask, as the first of their open problems, for an mcDSQS(38). We construct an mcDSQS(v) for v = 38, 44, 62, 74, 86, 92, two designs at each order, and prove the defining property for all v points of each. Every design is cyclic, and no novelty is claimed on the design side: the cyclic SQS(v) spectrum below 100 is settled in the literature apart from v=94. The new content is the colouring. Order 74 is the value at n=1 of the family 18 · 4ⁿ+2, for which Tan and Zhou pose a separate open problem. The colourings were found by an encoding that makes explicit a second exact cover hidden in the problem: since each point of an STS(n-1) is missed by exactly one class of a minimum colouring, a minimum colouring is a pair of coupled exact covers, and every earlier method we tried left the second one implicit. Making it explicit turns instances on which a local search of 1.2 million moves stalls into instances a SAT solver closes in seconds, and removes the need for any symmetry restriction at all. We also record two structural consequences: none of the minimum colourings found here has the "Hanani" class-size profile, and at orders 38 and 74 two of our designs realise different profiles, so the profile is not an invariant of the order. All statements are machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   732a5823044c032827a2a06047eaf2247dbb54a9a99cbfe1f80569a5b753d0df