An overlarge set of Kirkman triple systems, OLKTS(v), is a partition of all triples of a (v+1)-point set into v+1 Kirkman triple systems of order v, each omitting one point; it exists only for admissible orders v congruent to 3 mod 6. Yuan and Kang (2010) introduced a recursive machinery (overlarge sets of generalized Kirkman systems) that produces the strengthened variant OLKTS*(v) for every order v that is a finite product of factors 2q^r+1 (q a prime power with q congruent to 7 mod 12) and 4^s-1, and they posed the problem studied here: determine the complete existence spectrum of OLKTS(v). Since OLKTS*(v) yields an LKTS(3v), progress along this starred route also advances the celebrated open existence problem for large sets of Kirkman triple systems.

Background

A Steiner triple system STS(v) is a pair (X, B) where X is a v-element set and B is a collection of 3-element subsets, called blocks, such that every 2-element subset of X lies in exactly one block. A parallel class is a set of blocks that partitions X, and an STS(v) is resolvable if its whole block set partitions into parallel classes; a resolvable STS(v) is called a Kirkman triple system, KTS(v), and exists exactly for v congruent to 3 modulo 6. A large set of Kirkman triple systems, LKTS(v), is a collection of v-2 KTS(v)s on a common v-set whose block sets partition all triples of that set. The corresponding large-set problem for ordinary (not necessarily resolvable) Steiner triple systems was completely settled in the 1980s and early 1990s, but the LKTS existence problem - an old question posed by Sylvester in connection with Kirkman's 1850 schoolgirl problem - remains one of the best-known open problems in combinatorial design theory: known direct constructions cover only a sparse set of orders, all at most 381, as tabulated by Wang (2026), and every recent paper in the line reiterates that the problem is far from settled.

An overlarge set of Kirkman triple systems, OLKTS(v), is the one-point-larger analogue of a large set: a (v+1)-set Y together with KTS(v)s (Y minus {y}, B_y), one for each point y in Y, whose block sets partition all triples of Y. Since every member must itself be a KTS(v), admissibility requires v congruent to 3 modulo 6. The overlarge-set problem for ordinary Steiner triple systems is completely determined, but the resolvable version is much harder, and when Yuan and Kang took it up only isolated families (such as OLKTS(9)) were known. They introduced a strengthened variant: an OLKTS*(v) is an OLKTS(v) satisfying a four-way incidence equivalence at every point - for any four distinct points y, a, b, c of Y, the statements that {a,b,c} is a block of the member omitting y, that {y,a,b} is a block of the member omitting c, that {y,a,c} is a block of the member omitting b, and that {y,b,c} is a block of the member omitting a are all equivalent. As recorded by Xu and Ji (2024), the starred condition is equivalent to the existence of an RDSQS(v+1): a Steiner quadruple system of order v+1 (a collection of 4-subsets, called blocks, of a (v+1)-set such that every 3-subset lies in exactly one block) all of whose derived triple systems are resolvable, where the derived system at a point consists of the blocks containing that point with that point deleted. The importance of the starred variant is that any such object yields an LKTS(3v); this quadruple-system route is one of the two classical mechanisms for producing large sets of Kirkman triple systems.

To generate starred orders in bulk, Yuan and Kang (2010) introduced K-OLGKS(m^u, w), overlarge sets of generalized Kirkman systems: hybrid structures that combine an overlarge set with resolvable group-divisible designs (designs whose point set is partitioned into groups of equal size m, whose blocks meet each group at most once, and whose blocks carry a parallel-class structure), together with auxiliary generalized frames F(3,3,4{m}) built from resolvable transversal designs. Using base orders 4^n-1 and 2q^r+1 (q a prime power with q congruent to 7 modulo 12), they proved a multiplicative closure - OLKTS*(u) and OLKTS*(v) together imply OLKTS*(uv) - and concluded that OLKTS*(v) exists for every finite product of such factors. Their relational frame construction, however, works only for odd m (it needs invertibility of 2 and 4 modulo m), the starred machinery is developed only for the case of one auxiliary point, and the base-component supply is limited to the two factor types, so the existence spectrum of OLKTS(v), and of OLKTS*(v), remains undetermined. Xu and Ji (2024) later weakened the starred condition to OLKTS^+(v), requiring the four-way incidence equivalence only at two distinguished special points, and this variant likewise yields an LKTS(3v).

Problem Statement

Determine the complete existence spectrum of overlarge sets of Kirkman triple systems: for every admissible order v≡3(mod6)v\equiv 3\pmod 6 with v>3v>3, decide whether an OLKTS(v) exists, where OLKTS(v) is a partition of all triples of a (v+1)(v+1)-set into v+1v+1 Kirkman triple systems of order vv, each omitting one point.

The strengthened variant OLKTS*(v) (equivalently, an RDSQS(v+1)), its multiplicative family

v=∏i=1p(2qiri+1)∏j=1t(4sj−1),v=\prod_{i=1}^{p}(2q_i^{r_i}+1)\prod_{j=1}^{t}(4^{s_j}-1),

where p+t≥1p+t\ge 1, each ri,sj≥1r_i,s_j\ge 1, and each qiq_i is a prime power satisfying qi≡7(mod12)q_i\equiv 7\pmod{12}, and the implication OLKTS*(v) ⇒\Rightarrow LKTS(3v) form part of the background and motivation of the problem.

Determining the spectrum requires an explicit or recursively certified construction for each admissible order that admits an OLKTS(v) and a proof of nonexistence for each admissible order that does not. No nonexistence result beyond the congruence admissibility condition v≡3(mod6)v\equiv 3\pmod 6 is currently known.

References

  1. Landang Yuan, Qingde Kang, On overlarge sets of Kirkman triple systems, Discrete Mathematics 310 (2010) 2119-2125, DOI 10.1016/j.disc.2010.04.006, https://doi.org/10.1016/j.disc.2010.04.006
  2. Landang Yuan, Qingde Kang, A tripling construction for overlarge sets of KTS, Discrete Mathematics 309 (2009) 975-981, DOI 10.1016/j.disc.2008.01.001, https://doi.org/10.1016/j.disc.2008.01.001
  3. Landang Yuan, Qingde Kang, Further results on overlarge sets of Kirkman triple systems, Acta Mathematica Sinica (English Series) 25 (2009) 419-434, DOI 10.1007/s10114-008-6615-4, https://doi.org/10.1007/s10114-008-6615-4
  4. Landang Yuan, Qingde Kang, Another construction for large sets of Kirkman triple systems, Designs, Codes and Cryptography 48 (2008) 35-42, DOI 10.1007/s10623-008-9168-8, https://doi.org/10.1007/s10623-008-9168-8
  5. 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
  6. 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
  7. 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
  8. 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
  9. Juanjuan Xu, Lijun Ji, New results on LR-designs and OLKTSs, Discrete Mathematics 345 (2022) 112948, DOI 10.1016/j.disc.2022.112948, https://doi.org/10.1016/j.disc.2022.112948
  10. 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, https://doi.org/10.1007/s10623-023-01221-9 (also arXiv:2210.06214)
  11. 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
  12. 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, https://doi.org/10.1007/s10623-025-01677-x (also arXiv:2503.11934)
  13. Chen Wang, A new recursive construction for large sets of Kirkman triple systems, arXiv:2607.21521 (2026), https://arxiv.org/abs/2607.21521