The existence spectrum of large sets of Kirkman triple systems (Sylvester's problem)

Sylvester's problem, in its modern general form, asks whether for every order $v \equiv 3 \pmod{6}$ the set of all triples of a $v$-element set can be partitioned into $v-2$ pairwise disjoint Kirkman triple systems — a large set of Kirkman triple systems, LKTS($v$). The analogous non-resolvable problem was completely solved by Lu and Teirlinck (large sets of Steiner triple systems exist for every admissible order except 7), but the resolvable version has resisted settlement for over 170 years: as of 2026 only sparse direct constructions and special recursive families are known, and a July 2026 preprint constructed LKTSs of orders 93, 177, 219, 261, and 303 for the first time. The general existence question remains open, with even some orders below 100 still unsettled.

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 2-element subset of $X$ lies in exactly one block; an STS($v$) exists if and only if $v \equiv 1,3 \pmod{6}$. The system is resolvable if its blocks can be partitioned into parallel classes, each of which is itself a partition of the point set; a resolvable STS($v$) is called a Kirkman triple system, KTS($v$), and exists if and only if $v \equiv 3 \pmod{6}$ (Ray-Chaudhuri and Wilson, 1971, which settled the existence of Kirkman triple systems for every admissible order, the general form of Kirkman's 1850 schoolgirl problem). Two STS($v$) on the same point set are disjoint if they share no block; by a counting argument at most $v-2$ mutually disjoint STS($v$) can coexist, and any $v-2$ of them necessarily partition the set of all $\binom{v}{3}$ triples. Such a partition is a large set of Steiner triple systems, LSTS($v$), and its existence spectrum was completely determined by Lu (1983–84) and Teirlinck (1991): an LSTS($v$) exists if and only if $v \equiv 1,3 \pmod{6}$ and $v \neq 7$. A large set of Kirkman triple systems, LKTS($v$), is a large set in which every constituent STS($v$) is itself resolvable — equivalently, a partition of all triples of a $v$-set into $v-2$ pairwise disjoint KTS($v$)s.

The problem originates in a question posed by Sylvester in 1850 alongside Kirkman's schoolgirl problem: can the 455 triples of 15 schoolgirls be partitioned into 13 disjoint Kirkman schoolgirl schedules? Denniston (1974) answered this affirmatively by constructing an LKTS(15), and the existence of an LKTS($v$) for every admissible order $v \equiv 3 \pmod{6}$ has since become the standard generalization, referred to in the design-theory literature simply as Sylvester's problem; it is widely regarded as one of the best-known open problems of combinatorial design theory.

Progress has come from two directions. Direct constructions settle isolated orders: Kirkman's LKTS(9), Denniston's LKTS(15), and a growing but still sparse list of orders through 381, as tabulated by Wang (2026). Recursive constructions build new large sets from old but require auxiliary structures whose own existence is difficult: a Steiner quadruple system (an $S(3,4,w)$ design, in which every 3-subset of points lies in exactly one 4-block) whose derived design at every point (the triple system obtained by deleting that point from all blocks through it) is a Kirkman system — an RDSQS($w$) — yields an LKTS($3(w-1)$) (Chang and Zhou, 2013); Denniston's tripling and Lei's (2002) product construction produce LKTS($3v$) and LKTS($uv$) from ingredient large sets under strong resolvability hypotheses that were later relaxed; Wang and Shi constructed LKTS($q^n+2$) from LKTS($q+2$) for prime powers $q \equiv 1 \pmod{6}$; and Xu and Ji obtained LKTS($2^{2n+1}+1$) from a specially structured resolvable Steiner quadruple system (a '(2,1)-RSQS*($4n$)' in their notation). Zhou and Chang (2014) contributed the infinite family LKTS($12 \cdot 7^n - 3$), built from a new family RDSQS($4 \cdot 7^n$), together with an expanded product-based spectrum. Even with all of these, the known orders remain a small fraction of the admissible values — for instance, an LKTS(93) was first constructed only in 2026.

Problem Statement

For every integer $v \equiv 3 \pmod{6}$ with $v \geq 3$, does there exist a large set of Kirkman triple systems of order $v$ — that is, a partition of all $\binom{v}{3}$ triples of a $v$-element set into $v-2$ pairwise disjoint Kirkman triple systems, where a Kirkman triple system is a resolvable Steiner triple system (a collection of 3-element blocks in which every 2-element subset of the point set lies in exactly one block, with the blocks partitionable into parallel classes, each of which partitions the point set)? Equivalently, determine the complete existence spectrum of LKTS($v$): either establish a construction that yields an LKTS($v$) for every admissible order, or prove that some admissible order admits no such partition. The case $v=3$ is trivial; the question concerns the general admissible spectrum, which Zhou and Chang (2014) and all subsequent literature leave open.

References

1. Junling Zhou, Yanxun Chang, 'A new result on Sylvester's problem', Discrete Mathematics 331 (2014) 15-19. DOI: 10.1016/j.disc.2014.04.022, https://doi.org/10.1016/j.disc.2014.04.022
2. R. H. F. Denniston, 'Sylvester's problem of the 15 schoolgirls', Discrete Mathematics 9 (1974) 229-233. DOI: 10.1016/0012-365X(74)90004-1, https://doi.org/10.1016/0012-365X(74)90004-1
3. T. P. Kirkman, 'Note on an unanswered prize question', Cambridge and Dublin Mathematical Journal 5 (1850) 255-262. No DOI (the journal predates DOI registration).
4. D. K. Ray-Chaudhuri, Richard M. Wilson, 'Solution of Kirkman's schoolgirl problem', Proceedings of Symposia in Pure Mathematics 19 (1971) 187-203. DOI: 10.1090/pspum/019/9959, https://doi.org/10.1090/pspum/019/9959
5. Jia-Xi Lu, 'On large sets of disjoint Steiner triple systems I', Journal of Combinatorial Theory, Series A 34 (1983) 140-146. DOI: 10.1016/0097-3165(83)90052-3, https://doi.org/10.1016/0097-3165(83)90052-3
6. 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 (1991) 302-305. DOI: 10.1016/0097-3165(91)90053-J, https://doi.org/10.1016/0097-3165(91)90053-J
7. Jian-guo Lei, 'On large sets of disjoint Kirkman triple systems', Discrete Mathematics 257 (2002) 63-81. DOI: 10.1016/S0012-365X(01)00470-8, https://doi.org/10.1016/S0012-365X(01)00470-8
8. Junling Zhou, Yanxun Chang, 'New results on large sets of Kirkman triple systems', Designs, Codes and Cryptography 55 (2010) 1-7. DOI: 10.1007/s10623-009-9325-8, https://doi.org/10.1007/s10623-009-9325-8
9. Yanxun Chang, Junling Zhou, 'Large sets of Kirkman triple systems and related designs', Journal of Combinatorial Theory, Series A 120 (2013) 649-670. DOI: 10.1016/j.jcta.2012.12.001, https://doi.org/10.1016/j.jcta.2012.12.001
10. Chen Wang, Cong Shi, 'Large sets of Kirkman triple systems with order $q^n+2$', arXiv:1307.3019 (2013), https://arxiv.org/abs/1307.3019; journal version: Discrete Mathematics 340 (2017) 1042-1045. DOI: 10.1016/j.disc.2016.11.008, https://doi.org/10.1016/j.disc.2016.11.008
11. Hao Zheng, Yanxun Chang, Junling Zhou, 'Direct constructions of large sets of Kirkman triple systems', Designs, Codes and Cryptography 83 (2017) 23-32. DOI: 10.1007/s10623-016-0197-4, https://doi.org/10.1007/s10623-016-0197-4
12. Hao Zheng, Yanxun Chang, Junling Zhou, 'Large sets of Kirkman triple systems of prime power sizes', Designs, Codes and Cryptography 85 (2017) 411-423. DOI: 10.1007/s10623-016-0315-3, https://doi.org/10.1007/s10623-016-0315-3
13. Juanjuan Xu, Lijun Ji, 'Large sets of Kirkman triple systems of orders $2^{2n+1}+1$', Discrete Mathematics 344 (2021) 112373. DOI: 10.1016/j.disc.2021.112373, https://doi.org/10.1016/j.disc.2021.112373
14. Yan Liu, Jianguo Lei, 'More results on large sets of Kirkman triple systems', Designs, Codes and Cryptography 91 (2023) 2677-2686. DOI: 10.1007/s10623-023-01221-9, arXiv:2210.06214, https://arxiv.org/abs/2210.06214
15. Juanjuan Xu, Lijun Ji, 'Special overlarge sets of Kirkman triple systems', Designs, Codes and Cryptography 92 (2024) 2267-2285. DOI: 10.1007/s10623-024-01386-x, https://doi.org/10.1007/s10623-024-01386-x
16. Yuli Tan, Junling Zhou, 'Steiner quadruple systems with minimum colorable derived designs: constructions and applications', Designs, Codes and Cryptography 93 (2025) 4117-4140. DOI: 10.1007/s10623-025-01677-x, arXiv:2503.11934, https://arxiv.org/abs/2503.11934
17. Chen Wang, 'A new recursive construction for large sets of Kirkman triple systems', arXiv:2607.21521 (2026). https://arxiv.org/abs/2607.21521