Steiner Quadruple Systems with Minimum Colorable Derived Designs: Constructions and Applications
Yuli Tan, Junling Zhou · 2025
Read Steiner Quadruple Systems with Minimum Colorable Derived Designs: Constructions and Applications by Yuli Tan, Junling Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11934.txt.
Introduction
Tan and Zhou build Steiner systems whose inner designs use as few colors as can be in twenty twenty-five. A Steiner system packs items into blocks so each small group sits in just one block. Coloring asks that blocks of one color never overlap in a set way. The smallest color count for triple systems was known, and they lift the idea to four item blocks.
They give step by step builds that grow large systems from small ones. One build is new even for the older, looser class. Their main wins are endless families of both classes at set sizes. The results also settle when a kind of perfect code can exist at those sizes.
Catalog record
| CREATOR | Yuli Tan, Junling Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11934
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Steiner Quadruple Systems with Minimum Colorable Derived Designs: Constructions and Applications Yuli Tan, Junling Zhou Abstract An r r -block-coloring, simply r r -coloring, of a Steiner triple system STS ( v ) \mathrm{STS}(v) is a partition of the block set into r r color classes, each color class being a partial parallel class. The chromatic index of STS ( v ) \mathrm{STS}(v) , denoted by χ ′ ( v ) \chi^{\prime}(v) , is the smallest r r for which an r r -coloring of an STS ( v ) \mathrm{STS}(v) exists. A minimum colorable Steiner triple system mcSTS ( v ) \mathrm{mcSTS}(v) is an STS ( v ) \mathrm{STS}(v) admitting a χ ′ ( v ) \chi^{\prime}(v) -coloring. We generalize the notion of an RDSQS \mathrm{RDSQS} (a Steiner quadruple system SQS \mathrm{SQS} with resolvable derived designs) to mcDSQS \mathrm{mcDSQS} , representing an SQS \mathrm{SQS} whose derived design at every point is minimum colorable. This is motivated from an application in non-binary diameter perfect codes. The purpose of this paper is to display a few recursive constructions to produce mcDSQS \mathrm{mcDSQS} s via Steiner systems S ( 3 , K , v ) \mathrm{S}(3,K,v) with certain properties. Among others, a construction for mcDSQS \mathrm{mcDSQS} s is developed, which is also new even for RDSQS \mathrm{RDSQS} s; special constructions concentrating only on mcDSQS ( 6 n + 2 ) \mathrm{mcDSQS}(6n+2) s are demonstrated as well. As the main results, both a new infinite family of RDSQS ( 6 n + 4 ) \mathrm{RDSQS}(6n+4) s and the first infinite family of mcDSQS ( 6 n + 2 ) \mathrm{mcDSQS}(6n+2) s are constructed. To be specific, an RDSQS ( 2 2 m + 1 + 2 ) \mathrm{RDSQS}(2^{2m+1}+2) and an mcDSQS ( 2 ⋅ 9 m + 2 ) \mathrm{mcDSQS}(2\cdot 9^{m}+2) are proved to exist, in which the former class gives rise to a new infinite family of large sets of Kirkman triple systems. As applications, the smallest q q is determined such that a diameter perfect constant-weight ( n , 1 4 ( n 3 ) , 6 , 4 ) q (n,\frac{1}{4}\tbinom{n}{3},6;4)_{q} code exists where n ∈ { 2 ⋅ 9 m + 2 : m ≥ 1 } ⋃ { 2 2 m + 1 + 2 : m ≥ 0 } n\in\{2\cdot 9^{m}+2:m\geq 1\}\bigcup\{2^{2m+1}+2:m\geq 0\} . Keywords : Steiner quadruple system, minimum colorable, derived design, large set, Kirkman triple system, diameter perfect code The research was supported by National Natural Science Foundation of China (12171028, 12371326). 1 Introduction and preliminaries Let X be a set of v points and K a set of positive integers. Let \mathcal{G} be a collection of subsets (called groups or holes ) of X which partition X . A group divisible t -design of order v with block sizes from K , denoted by \mathrm{GDD}(t,K,v) , is a triple (X,\mathcal{G},\mathcal{B}) with the following properties: (1) \mathcal{B} is a family of subsets of X (called blocks ), each having cardinality in K ; (2) each block of \mathcal{B} intersects any given group in at most one point; (3) each t -subset of X from t distinct groups is contained in exactly one block. The type of the \mathrm{GDD} is defined to be the multiset T=\{|G|:G\in\mathcal{G}\} of group sizes. We also use g_{1}^{a_{1}}g_{2}^{a_{2}}\ldots g_{r}^{a_{r}} to denote the type, which means that there are a_{i} groups of size g_{i} , 1\leq i\leq r . A \mathrm{GDD}(t,\{k\},v) is also denoted by \mathrm{GDD}(t,k,v) . A \mathrm{GDD}(t,k,kn) of type n^{k} is known as a transversal t -design and denoted by \mathrm{TD}(t,k,n) . If (X,\mathcal{G},\mathcal{B}) is a \mathrm{GDD}(t,K,v) of type 1^{v} , then we omit the notation of \mathcal{G} and call (X,\mathcal{B}) a Steiner t -system , also denoted \mathrm{S}(t,K,v) . The notation \mathrm{S}(t,k,v) is used for K=\{k\} . An \mathrm{S}(2,3,v) is a Steiner triple system \mathrm{STS}(v) and an \mathrm{S}(3,4,v) is a Steiner quadruple system \mathrm{SQS}(v) . It is well-known that an \mathrm{STS}(v) exists if and only if v\equiv 1,3\pmod{6} [ 10 ] and an \mathrm{SQS}(v) exists if and only if v\equiv 2,4\pmod{6} [ 7 ] . Let (X,\mathcal{G},\mathcal{B}) be a \mathrm{GDD} and Y\subseteq X . A partial parallel class ( \mathrm{PPC} ) of Y is a collection of pairwise disjoint blocks contained in Y . A parallel class ( \mathrm{PC} ) of Y is a \mathrm{PPC} that partitions Y . We say that (X,\mathcal{G},\mathcal{B}) is resolvable , denoted by \mathrm{RGDD} , if \mathcal{B} can be partitioned into \mathrm{PC} s of X . An \mathrm{RGDD}(t,k,v) of type 1^{v} is a resolvable \mathrm{S}(t,k,v) , denoted by \mathrm{RS}(t,k,v) . An \mathrm{RS}(2,3,v) is a Kirkman triple system \mathrm{KTS}(v) . A \mathrm{KTS}(v) exists if and only if v\equiv 3\pmod{6} [ 12 , 15 ] . Two \mathrm{KTS}(v) s on the same set X are said to be disjoint if they have no blocks in common. A large set of Kirkman triple system of order v , denoted by \mathrm{LKTS}(v) , is a partition of all triples of a v -element set X into v-2 pairwise disjoint \mathrm{KTS}(v) s. Although the problem of the existence of \mathrm{LKTS}(v) s has a long history, it remains pretty much open. Let (X,\mathcal{B}) be an \mathrm{S}(t,k,v) . For any point x\in X , let \mathcal{B}_{x}=\{B\setminus\{x\}:x\in B,B\in\mathcal{B}\} . Then (X\setminus\{x\},\mathcal{B}_{x}) is an \mathrm{S}(t-1,k-1,v-1) , which is said to be the derived design of (X,\mathcal{B}) at the point x . An \mathrm{S}(t,k,v) with resolvable derived designs , abbreviated to \mathrm{RDS}(t,k,v) , refers to an \mathrm{S}(t,k,v) whose derived design at every point is resolvable. We use the notation \mathrm{RDSQS}(v) to denote an \mathrm{SQS}(v) with resolvable derived designs. \mathrm{RDSQS} s play an important role in recursive constructions of large sets of Kirkman triple systems (see [ 3 , 11 , 22 ] ). Theorem 1.1 ( [ 3 , 22 ] ) . If there exists an \mathrm{RDSQS}(v+1) , then there exists an \mathrm{LKTS}(3v) . We know that the necessary condition for the existence of an \mathrm{RDSQS}(v) is v\equiv 4\pmod{6} as a \mathrm{KTS}(v) exists if and only if v\equiv 3\pmod{6} . An \mathrm{SQS}(v) with v\equiv 2\pmod{6} dose not have a resolvable derived design, but one may instead ask for a derived design with a partition of the blocks into minimum number of PPCs. We introduce the concept of block-coloring. An r -block-coloring , or simply r -coloring , of a design is a partition of the block set into r color classes, each color class being a \mathrm{PPC} . The collection of the r \mathrm{PPC} s is called a resolution . The chromatic index of a design \mathcal{D} , denoted by \chi^{\prime}(\mathcal{D}) , is the smallest r for which \mathcal{D} admits an r -coloring. The chromatic index of Steiner systems \mathrm{S}(t,k,v) , denoted by \chi^{\prime}_{t,k}(v) , is defined as \chi^{\prime}_{t,k}(v)=\mathop{\min}_{\mathcal{D}\text{ is an }S(t,k,v)}\chi^{\prime}(\mathcal{D}). For convenience, the notation \chi^{\prime}(v) is used for \chi^{\prime}_{2,3}(v) . If \mathcal{D} is a resolvable \mathrm{S}(t,k,v) , then \chi^{\prime}_{t,k}(\mathcal{D}) equals {k\tbinom{v}{t}}/{v\tbinom{k}{t}} . Therefore, \chi^{\prime}(v) equals (v-1)/2 for v\equiv 3\pmod{6} because of the existence of a \mathrm{KTS}(v) . The unique \mathrm{STS}(7) has chromatic index 7 as each pair of blocks has an intersection point. There are two nonisomorphic \mathrm{STS}(13) s and each