Existence of Steiner quadruple systems with minimum colorable derived designs: smallest unknown orders and auxiliary candelabra designs for infinite families

An $\mathrm{mcDSQS}(v)$ is a Steiner quadruple system $\mathrm{SQS}(v)$ (a Steiner system $\mathrm{S}(3,4,v)$) whose derived design at every point is a minimum colorable Steiner triple system, i.e., admits a block-coloring into $\chi'(v-1)$ partial parallel classes, where $\chi'(v-1)$ denotes the minimum chromatic index over all Steiner triple systems of order $v-1$ (a partial parallel class being a set of pairwise disjoint blocks). Introduced by Tan and Zhou (2025) as the $v\equiv 2\pmod 6$ generalization of Steiner quadruple systems with resolvable derived designs ($\mathrm{RDSQS}$), these systems govern the smallest alphabet size of certain non-binary diameter perfect constant-weight codes and, through the $\mathrm{RDSQS}$-to-LKTS pipeline, produce large sets of Kirkman triple systems. Tan and Zhou constructed the first infinite family $\mathrm{mcDSQS}(2\cdot 9^{m}+2)$ and a new family $\mathrm{RDSQS}(2^{2m+1}+2)$, and posed concrete existence targets which remain open: an $\mathrm{mcDSQS}(38)$ and an $\mathrm{RDSQS}(52)$ (the smallest unknown mcDSQS order with $v\ge 20$ and the smallest unknown RDSQS order), the auxiliary candelabra designs $\mathrm{gcDCQS}(20^{4}:0)$, $\mathrm{gcDCQS}(32^{4}:0)$, and $\mathrm{gcDCQS}(18^{4}:2)$ together with an $\mathrm{FDGDD}(3,4,5\{18\})$ or $\mathrm{RDGDD}(3,4,5\{18\})$, whose existence would yield — via the paper's own already-proven lifting constructions — infinite $\mathrm{mcDSQS}$ families at orders $5\cdot 4^{n}$, $2^{2n+1}$, and $18\cdot 4^{n}+2$, respectively, together with the broader goal of more effective recursive constructions for $\mathrm{mcDSQS}(v)$. The problem asks for constructions of these designs (or proofs of nonexistence) and for recursive machinery that broadens the known existence spectrum.

Background

A Steiner system $\mathrm{S}(t,k,v)$ is a $v$-element point set together with a collection of $k$-element subsets (blocks) such that every $t$-subset of points lies in exactly one block. A Steiner quadruple system $\mathrm{SQS}(v)$ is an $\mathrm{S}(3,4,v)$; by a classical theorem of Hanani it exists if and only if $v\equiv 2,4\pmod 6$. A Steiner triple system $\mathrm{STS}(v)$ is an $\mathrm{S}(2,3,v)$. Fixing a point $x$ of an $\mathrm{SQS}(v)$ and deleting $x$ from every block containing it produces the derived design at $x$, which is an $\mathrm{STS}(v-1)$. An $r$-coloring of a design is a partition of its block set into $r$ color classes, each class being a partial parallel class (a set of pairwise disjoint blocks); the chromatic index $\chi'(\mathcal{D})$ of a design is the smallest such $r$. Writing $\chi'(v)$ for the minimum of $\chi'(\mathcal{D})$ over all Steiner triple systems $\mathcal{D}$ of order $v$, this minimum is completely known: $\chi'(v)=(v-1)/2$ when $v\equiv 3\pmod 6$, $\chi'(v)=(v+1)/2$ when $v\equiv 1\pmod 6$ and $v\notin\{7,13\}$, with the exceptions $\chi'(7)=7$ and $\chi'(13)=8$; an individual system may need more colors, never fewer. A minimum colorable system $\mathrm{mcSTS}(v)$ is one whose own chromatic index attains this minimum; for $v\equiv 3\pmod 6$ this is exactly a Kirkman triple system $\mathrm{KTS}(v)$, i.e., a resolvable $\mathrm{STS}(v)$ whose blocks partition into parallel classes (a parallel class being a partial parallel class covering every point of the system). A Steiner quadruple system with resolvable derived designs, $\mathrm{RDSQS}(v)$, is an $\mathrm{SQS}(v)$ whose derived design at every point is a $\mathrm{KTS}(v-1)$; this forces $v\equiv 4\pmod 6$. $\mathrm{RDSQS}$s matter because an $\mathrm{RDSQS}(v+1)$ yields a large set of Kirkman triple systems $\mathrm{LKTS}(3v)$ — a partition of all triples of a $3v$-set into disjoint $\mathrm{KTS}(3v)$s — and the existence of $\mathrm{LKTS}(v)$ for all admissible $v$ is a long-standing open problem going back to Kirkman's 1847 schoolgirl problem. For $v\equiv 2\pmod 6$ the derived design is an $\mathrm{STS}(v-1)$ with $v-1\equiv 1\pmod 6$, which cannot be resolvable; Tan and Zhou (2025) introduced the $\mathrm{mcDSQS}(v)$ — an $\mathrm{SQS}(v)$ whose derived design at every point is minimum colorable — as the correct analogue, coinciding with $\mathrm{RDSQS}(v)$ when $v\equiv 4\pmod 6$. The motivation comes from coding theory: a diameter perfect constant-weight code is a code $\mathcal{C}$ in the space $\mathcal{J}_{q}(n,w)$ of $q$-ary words of length $n$ and weight $w$ that meets Delsarte's code-anticode bound $|\mathcal{C}|\cdot|\mathcal{A}|\le|\mathcal{V}|$ with equality for an anticode $\mathcal{A}$ whose diameter (largest pairwise Hamming distance) is smaller than the minimum distance of $\mathcal{C}$; Etzion (2022) classified the known non-binary examples, and Shi, Xia and Krotov (2023) showed such codes arise from Steiner systems, observing in particular that the cyclic $\mathrm{SQS}(20)$ is an $\mathrm{mcDSQS}(20)$. Tan and Zhou's Corollary 1.4 states that for $n\equiv 2\pmod 6$, $n\ge 20$, the existence of an $\mathrm{mcDSQS}(n)$ forces the smallest alphabet size $q$ for which a diameter perfect constant-weight $(n,\tbinom{n}{3}/4,6;4)_{q}$ code exists to be exactly $q=n/2+1$ (similarly $\mathrm{RDSQS}(n)$ gives $q=n/2$ for $n\equiv 4\pmod 6$). Their recursive machinery rests on the candelabra quadruple system $\mathrm{CQS}(g^{n}:s)$ — a point set carrying a distinguished $s$-point stem and a partition of the remaining points into $n$ groups of size $g$, such that every triple of points not wholly contained in the union of the stem and a single group lies in exactly one block, while no triple contained in such a union lies in any block — equipped with a derived-design coloring structure: a $\mathrm{gcDCQS}(g^{n}:s)$ is a $\mathrm{CQS}(g^{n}:s)$ whose derived design at each point $x$ of a group $G$ is a good colorable incomplete Steiner triple system $\mathrm{gcSTS}(gn+s-1,g+s-1)$ on the remaining points with $(G\cup S)\setminus\{x\}$ as its hole — good colorable meaning that the blocks partition into exactly $\chi'(v)$ partial parallel classes of the point set, of which exactly $\chi'(v)-(v-h)/2$ are disjoint from the hole ($v$ the order, $h$ the hole size) — and whose derived design at each stem point is a Kirkman frame $\mathrm{KF}(g^{n})$: a group divisible design of type $g^{n}$ (a point set partitioned into $n$ groups of size $g$ with blocks meeting each group at most once, such that every pair of points from different groups lies in exactly one block) whose blocks partition into parallel classes, each covering all points outside exactly one of the groups. Relatedly, an $\mathrm{RDGDD}(3,4,v\{m\})$ or $\mathrm{FDGDD}(3,4,v\{m\})$ is a group divisible $3$-design of type $m^{v}$ — blocks of size $4$ covering every triple of points from three distinct groups exactly once — whose point-derived designs are, respectively, resolvable group divisible designs or Kirkman frames. Constructions 2.1–2.4 of the paper fill holes and lift these structures: Construction 2.1 builds an $\mathrm{mcDSQS}(gn+s)$ from a $\mathrm{gcDCQS}(g^{n}:s)$ together with the hole-filling inputs $\mathrm{mcDSQS}(g+s)$ and a good-colorable incomplete $\mathrm{SQS}(g+s,s)$ (the latter coinciding with $\mathrm{mcDSQS}(g)$ when $s=0$); Constructions 2.2/2.3 lift a $\mathrm{gcDCQS}(m^{k}:s)$ to $\mathrm{gcDCQS}(m^{n}:s)$ using an $\mathrm{RDS}(3,k+1,n+1)$ (a Steiner $3$-design with resolvable derived designs, which exists for every prime power $q$ as $\mathrm{RDS}(3,q+1,q^{n}+1)$ by their Lemma 3.8) together with an $\mathrm{RDGDD}$ or $\mathrm{FDGDD}$; and Corollary 2.6 states that for $m\equiv 4,8\pmod{12}$, a $\mathrm{gcDCQS}(m^{4}:0)$ plus an $\mathrm{mcDSQS}(m)$ yields an $\mathrm{mcDSQS}(m\cdot 4^{n})$ for all $n\ge 2$. Using this machinery, Tan and Zhou proved the existence of an $\mathrm{RDSQS}(2^{2n+1}+2)$ for all $n\ge 0$ (giving $\mathrm{LKTS}(3\cdot 2^{2n+1}+3)$) and the first infinite family $\mathrm{mcDSQS}(2\cdot 9^{m}+2)$ for $m\ge 1$, and constructed cyclic $\mathrm{mcDSQS}(26)$ and $\mathrm{mcDSQS}(32)$. Before their paper the only known $\mathrm{mcDSQS}(6n+2)$ with $n\ge 3$ was the $\mathrm{mcDSQS}(20)$ of Shi et al.; the $\mathrm{RDSQS}$ spectrum at orders $6n+4$ was known only at scattered orders from earlier recursive work (e.g., the $\mathrm{RDSQS}(4v)$ construction of Liu and Lei, 2023). The authors close their paper by noting that, because the chromatic index of an $\mathrm{STS}(v)$ equals $(v+1)/2$ only for $v\equiv 1\pmod 6$ with $v\ge 19$, direct constructions of the auxiliary designs needed for $\mathrm{mcDSQS}(6n+2)$ usually require significant computation — which is exactly why the smallest unknown instances and the specific auxiliary designs listed below are posed as open problems.

Problem Statement

Resolve the existence questions posed in Section 4 of Tan and Zhou (2025), whose common objective is to broaden the known existence spectrum of Steiner quadruple systems with minimum colorable derived designs and, through it, the applications to diameter perfect constant-weight codes and large sets of Kirkman triple systems. The concrete, jointly coherent targets are: (1) construct an mcDSQS(38) — the smallest unknown order among mcDSQS(6n+2) with n ≥ 3 (that is, v ≥ 20, where the derived design is an STS(v−1) with v−1 ≥ 19 and χ′(v−1) = v/2), the known ones being 20, 26, 32 and 2·9^m+2 — and an RDSQS(52), the smallest unknown order among RDSQS(6n+4), or prove that no such system exists; (2) construct a gcDCQS(20^4:0) and a gcDCQS(32^4:0) — auxiliary candelabra designs whose sole purpose is the lifting: by Corollary 2.6 of the source paper, whose further input mcDSQS(m) is already known at m = 20 and m = 32, a gcDCQS(20^4:0) would imply an mcDSQS(5·4^n) for every integer n ≥ 3, and a gcDCQS(32^4:0) would imply an mcDSQS(2^{2n+1}) for every integer n ≥ 4; (3) construct a gcDCQS(18^4:2) together with an FDGDD(3,4,5{18}) or an RDGDD(3,4,5{18}) — by Constructions 2.2/2.3 together with Lemma 3.8 (existence of an RDS(3,q+1,q^n+1) for every prime power q) and the filling Construction 2.1 (applied in the source paper by filling with an mcDSQS(20)), this would yield an mcDSQS(18·4^n+2) for every integer n ≥ 1; and (4) develop more effective and more widely applicable recursive constructions for mcDSQS(v), reducing the computational dependence on auxiliary small inputs. Each concrete design in (1)–(3) is resolved by a construction of that design or by a proof that no such design exists. These designs are independent targets: resolving any one of them does not require resolving the others.

References

1. Yuli Tan, Junling Zhou. Steiner quadruple systems with minimum colorable derived designs: constructions and applications. Designs, Codes and Cryptography 93(10):4117–4140, 2025. DOI: 10.1007/s10623-025-01677-x. https://doi.org/10.1007/s10623-025-01677-x
2. Yuli Tan, Junling Zhou. Steiner Quadruple Systems with Minimum Colorable Derived Designs: Constructions and Applications. arXiv:2503.11934, 2025. DOI: 10.48550/arxiv.2503.11934. https://arxiv.org/abs/2503.11934
3. Chen Wang. A new recursive construction for large sets of Kirkman triple systems. arXiv:2607.21521, 2026. https://arxiv.org/abs/2607.21521
4. Yuli Tan, Junling Zhou. Tilings of $\mathcal{H}_{q}(n,w)$ with optimal $(n,d,w)_{q}$-codes. arXiv:2512.22754, 2025; journal version in Designs, Codes and Cryptography 94, 2026. DOI: 10.1007/s10623-026-01853-7. https://arxiv.org/abs/2512.22754
5. Yan Liu, Jianguo Lei. More results on large sets of Kirkman triple systems. Designs, Codes and Cryptography 91:2677–2686, 2023. DOI: 10.1007/s10623-023-01221-9. https://doi.org/10.1007/s10623-023-01221-9 (arXiv:2210.06214)
6. Minjia Shi, Yuhong Xia, Denis S. Krotov. A family of diameter perfect constant-weight codes from Steiner systems. Journal of Combinatorial Theory, Series A 200:105790, 2023. DOI: 10.1016/j.jcta.2023.105790. https://doi.org/10.1016/j.jcta.2023.105790
7. Tuvi Etzion. Non-Binary Diameter Perfect Constant-Weight Codes. IEEE Transactions on Information Theory 68(2):891–904, 2022. DOI: 10.1109/TIT.2021.3125277. https://doi.org/10.1109/TIT.2021.3125277
8. Haim Hanani. On Quadruple Systems. Canadian Journal of Mathematics 12:145–157, 1960. DOI: 10.4153/cjm-1960-013-3. https://doi.org/10.4153/cjm-1960-013-3