Existence spectrum of large sets of Kirkman triple systems

A large set of Kirkman triple systems, LKTS($v$), is a partition of all triples on a $v$-point set into $v-2$ pairwise disjoint Kirkman triple systems, i.e., resolvable Steiner triple systems. Such a partition can exist only when $v \equiv 3 \pmod{6}$, and determining for exactly which orders it does exist — in particular whether it exists for every such order — is one of the best-known open problems in combinatorial design theory, going back to Sylvester in connection with Kirkman's schoolgirl problem. Liu and Lei (2023) obtained new infinite families via Steiner quadruple systems with resolvable derived designs but left the general spectrum open. According to Wang (2026, arXiv:2607.21521), LKTS($v$) is now known for every admissible order below 200 except possibly 57 and 87, which are the smallest remaining cases, and no asymptotic or complete solution is known.

Background

A Steiner triple system of order $v$, STS($v$), is a pair $(X,\mathcal{B})$ where $X$ is a $v$-element set and $\mathcal{B}$ is a collection of 3-element subsets (blocks) such that every unordered pair of points of $X$ lies in exactly one block. A partition of $\mathcal{B}$ into parallel classes — each parallel class being itself a partition of $X$ into blocks — is called a resolution, and a resolvable STS($v$) is called a Kirkman triple system, KTS($v$). The terminology goes back to Kirkman's schoolgirl problem of 1850, which asked for a resolvable STS(15); Ray-Chaudhuri and Wilson later proved that a KTS($v$) exists if and only if $v \equiv 3 \pmod{6}$.

Two STSs on the same point set are disjoint if they share no block. Since an STS($v$) contains $v(v-1)/6$ triples while the complete set of triples on $v$ points has $\binom{v}{3}$ elements, at most $v-2$ mutually disjoint STS($v$)s can coexist, and a family attaining this bound necessarily partitions all triples. Such a family is called a large set of Steiner triple systems, LSTS($v$); Lu (in a series of papers, 1983–84) and Teirlinck (1991) completely determined the LSTS spectrum: an LSTS($v$) exists if and only if $v \equiv 1, 3 \pmod{6}$ and $v \neq 7$. The resolvable analogue is much harder: a large set of Kirkman triple systems, LKTS($v$), is an LSTS($v$) in which every constituent STS($v$) is resolvable. Necessarily $v \equiv 3 \pmod{6}$. The existence question for LKTSs is attributed to Sylvester in connection with the schoolgirl problem (see the account in Wang, 2026); the first case, LKTS(15), was constructed by Denniston in 1974. The problem of determining the complete existence spectrum of LKTSs remains one of the best-known open problems in combinatorial design theory.

Progress has come from two directions. Direct constructions are known only for a sparse set of orders: 9 (Kirkman), 15 (Denniston), 33 (Schreiber), 51, 75, 105, 129 (Denniston), 201, 369 (Chang and Ge), 273 (Ge), 21, 39 (Zhou and Chang), 69, 141, 165, 213, 285, 309, 333, 111, 123, 159, 183, 195, 231, 279, 291, 339, 381 (Zheng, Chang and Zhou), together with infinite families of prime-power type (Zheng, Chang and Zhou), of order $q^{n}+2$ for suitable prime powers $q$ (Wang and Shi), and of order $2^{2n+1}+1$ (Xu and Ji). Recursive constructions include Denniston's tripling construction, its generalization to a product construction by Lei (with hypotheses weakened by Zhang and Zhu), and a recent construction of LKTS($7q+2$) from LKTS($q+2$) via a structure on an abelian group of order $q$ called a cubic orthomorphism, which exists whenever $q$ is a product of prime powers congruent to 1 modulo 6 (Wang, 2026).

A central role is played by auxiliary designs. A Steiner system $S(t,k,v)$ is a design on a $v$-point set whose blocks all have size $k$, such that every $t$-element subset of the points lies in exactly one block. For such a system, the derived design at a point $x$ is the design on $X \setminus \{x\}$ whose blocks are the blocks through $x$ with $x$ removed. A Steiner quadruple system SQS($v$) — an $S(3,4,v)$, i.e. a system of 4-element blocks in which every 3-subset of the points lies in exactly one block, which exists if and only if $v \equiv 2, 4 \pmod{6}$ — with all derived designs resolvable is called an RDSQS($v$); a theorem of Chang and Zhou's survey, restated after Yuan and Kang, states that an RDSQS($v+1$) implies an LKTS($3v$). Liu and Lei (2023) introduced a refined structure RDSQS$^{\ast}(v)$ and used it to construct RDSQS($4v$), yielding three new infinite families of RDSQSs and hence of LKTSs (its Theorem 4.4 gives LKTS($3v$) whenever $v$ is a product of elements from an explicit list of integers and families such as $7\cdot 4^{n}-1$, $3\cdot 7^{n}$, $4^{m}25^{n}-1$ and $2q^{n}+1$ for prime powers $q \equiv 7 \pmod{12}$). Related auxiliary structures such as overlarge sets (partitions of the triples of a $(v+1)$-set into KTSs each missing one point) and LR-designs (an auxiliary design type introduced by Lei in 2002 for the recursive construction of LKTSs) feed the same program (Xu and Ji, 2022, 2024). According to Wang (2026), combining all known direct and recursive results establishes LKTS($v$) for every $v < 200$ with $v \equiv 3 \pmod{6}$, with the possible exceptions of $v = 57$ and $v = 87$, which are now the smallest remaining cases of the existence problem; the general problem, however, remains far from settled.

Problem Statement

Determine the complete existence spectrum of large sets of Kirkman triple systems: for exactly which positive integers $v$ does an LKTS($v$) — a partition of all $\binom{v}{3}$ triples on a $v$-point set into $v-2$ pairwise disjoint Kirkman triple systems, where a Kirkman triple system is a Steiner triple system (a collection of 3-element blocks in which every pair of points lies in exactly one block) whose block set splits into parallel classes, each parallel class itself partitioning the $v$ points into blocks — exist?

The order must satisfy $v \equiv 3 \pmod{6}$ (each constituent KTS requires it, since a KTS($v$) exists only for such orders), and $v = 3$ is trivial. A complete solution must either:

1. prove that an LKTS($v$) exists for every $v \equiv 3 \pmod{6}$ (for example, through a uniform construction, an asymptotic existence theorem for all sufficiently large admissible orders combined with explicit constructions for the remaining finite set, or a reduction of all admissible orders to finitely many auxiliary designs plus those designs' construction); or

2. establish a classification, proving nonexistence of an LKTS($v$) for at least one admissible order $v$ and determining exactly which admissible orders admit one.

Either answer must cover every admissible order, including the smallest currently unresolved cases LKTS(57) and LKTS(87), for which no construction or nonexistence proof is known. Constructing LKTS(57) or LKTS(87) alone would constitute major partial progress but would not by itself close the problem, since the required classification extends over all $v \equiv 3 \pmod{6}$.

References

1. Yan Liu, Jianguo Lei, More results on large sets of Kirkman triple systems, Designs, Codes and Cryptography 91(8):2677–2686 (2023), DOI 10.1007/s10623-023-01221-9; preprint arXiv:2210.06214, https://arxiv.org/abs/2210.06214
2. Chen Wang, A new recursive construction for large sets of Kirkman triple systems, preprint arXiv:2607.21521 (2026), https://arxiv.org/abs/2607.21521
3. 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; preprint arXiv:2503.11934, https://arxiv.org/abs/2503.11934
4. Yanxun Chang, Junling Zhou, Large sets of Kirkman triple systems and related designs, Journal of Combinatorial Theory, Series A 120(3):649–670 (2013), DOI 10.1016/j.jcta.2012.12.001, https://doi.org/10.1016/j.jcta.2012.12.001
5. Juanjuan Xu, Lijun Ji, Large sets of Kirkman triple systems of orders $2^{2n+1}+1$, Discrete Mathematics 344(6):112373 (2021), DOI 10.1016/j.disc.2021.112373, https://doi.org/10.1016/j.disc.2021.112373
6. Chen Wang, Cong Shi, Large sets of Kirkman triple systems with order $q^{n}+2$, Discrete Mathematics 340(5):1042–1045 (2017), DOI 10.1016/j.disc.2016.11.008, https://doi.org/10.1016/j.disc.2016.11.008
7. Hao Zheng, Yanxun Chang, Junling Zhou, Large sets of Kirkman triple systems of prime power sizes, Designs, Codes and Cryptography 85(3):411–423 (2017), DOI 10.1007/s10623-016-0315-3, https://doi.org/10.1007/s10623-016-0315-3
8. Juanjuan Xu, Lijun Ji, New results on LR-designs and OLKTSs, Discrete Mathematics 345:112948 (2022), DOI 10.1016/j.disc.2022.112948, https://doi.org/10.1016/j.disc.2022.112948
9. Juanjuan Xu, Lijun Ji, Special overlarge sets of Kirkman triple systems, Designs, Codes and Cryptography 92:2267–2285 (2024), DOI 10.1007/s10623-024-01386-x, https://doi.org/10.1007/s10623-024-01386-x
10. Jia-Xi Lu, On large sets of disjoint Steiner triple systems I, Journal of Combinatorial Theory, Series A 34(2):140–146 (1983), DOI 10.1016/0097-3165(83)90052-3, https://doi.org/10.1016/0097-3165(83)90052-3
11. Luc Teirlinck, A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems, Journal of Combinatorial Theory, Series A 57(2):302–305 (1991), DOI 10.1016/0097-3165(91)90053-J, https://doi.org/10.1016/0097-3165(91)90053-J
12. R. H. F. Denniston, Sylvester's problem of the 15 schoolgirls, Discrete Mathematics 9:229–233 (1974), DOI 10.1016/0012-365X(74)90004-1, https://doi.org/10.1016/0012-365X(74)90004-1
13. D. K. Ray-Chaudhuri, R. M. Wilson, Solution of Kirkman's schoolgirl problem, Proceedings of Symposia in Pure Mathematics 19:187–203 (1971), DOI 10.1090/pspum/019/9959, https://doi.org/10.1090/pspum/019/9959