On partial parallel classes in partial Steiner triple systems

DOI10.1016/J.DISC.2020.112279MaRDI QIDQ2659191zbMATH OpenOpenAlexFDO

Authors D. R. Stinson

Publication date 25 March 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11033

zbMATH Keywords

combinatorial aspects of block designstriple systems

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Triple systems (05B07)

Abstract: For an integer $ho$ such that $1leqholeqv/3$, define $$ to be the maximum number of blocks in any partial Steiner triple system on $v$ points in which the maximum partial parallel class has size $ho$. We obtain lower bounds on $$ by giving explicit constructions, and upper bounds on $$ result from counting arguments. We show that $$ if $ho$ is a constant, and $$ if $ho=v/c$, where $c$ is a constant. When $ho$ is a constant, our upper and lower bounds on $$ differ by a constant that depends on $ho$. Finally, we apply our results on $$ to obtain infinite classes of sequenceable partial Steiner triple systems.

Review text

A partial Steiner system of order \(v\), PSTS(\(v\)) for short, is a pair \(S=(X,B)\), where \(X\) is a set of \(v\) points and \(B\) is a set of \(3\)-subsets (blocks) such that every pair of points occurs in at most one block. A partial parallel class (PPC) of size \(\rho\) in \(S\) is any set of \(\rho\) disjoint blocks. A PPC is maximum if it has size \(\rho\) and there does not exist any PPC in \(S\) of size \(\rho +1\). For an integer \(\rho\) such that \(1 \le \rho \le \frac{v}{3}\), the maximum number of blocks \(\beta(\rho,v)\) in any PSTS(\(v\)) in which the maximum PPC has size \(\rho\), is considered. Lower bounds on \(\beta(\rho,v)\) are obtained by explicit constructions. Upper bounds results are obtained by counting arguments. These results are applied to obtain sequenceable partial Steiner triple systems. Here, sequenceable means that there exists a permutation \(\pi\) of the point-set \(X\) such that no \(3t\) consecutive points in \(\pi\) are the union of \(t\) blocks, for all \(t\) with \(1\le t \le \lfloor \frac{v}{3}\rfloor\).

Recommendations

• Partial parallel classes in Steiner systems
• Partial Parallel Classes in Steiner System S(2, 3, 19)
• scientific article; zbMATH DE number 4150179
• Nonsequenceable Steiner triple systems
• scientific article; zbMATH DE number 4057524

Cites work

• A note on partial parallel classes in Steiner systems
• A second infinite family of Steiner triple systems without almost parallel classes
• scientific article; zbMATH DE number 124522 (Why is no real title available?)
• scientific article; zbMATH DE number 1314686 (Why is no real title available?)
• Nearly perfect matchings in regular simple hypergraphs
• Nonsequenceable Steiner triple systems
• On the Size of a Maximum Transversal in a Steiner Triple System
• On the Size of Partial Parallel Classes in Steiner Systems
• Steiner triple systems without parallel classes
• The existence of Room squares
• Variations on the sequenceable theme

Cited in

(16)

• Some new Kirkman signal sets
• Maximum parallel classes in 3-packings
• Block avoiding point sequencings of partial Steiner systems
• Uniform two-class regular partial Steiner triple systems
• Some NP-completeness results on partial Steiner triple systems and parallel classes.
• Binomial partial Steiner triple systems containing complete graphs
• scientific article; zbMATH DE number 4150179 (Why is no real title available?)
• Partial parallel classes in Steiner systems
• Degree sequence conditions for partial Steiner triple systems
• Partial Parallel Classes in Steiner System S(2, 3, 19)
• Maximum partial triple systems on 16 and 17 points
• Parallelism in Steiner systems
• Nonsequenceable Steiner triple systems
• Sequencing Partial Steiner Triple Systems
• Asymptotic existence of egalitarian Steiner 2-designs
• Trails of triples in partial triple systems

This page was built for publication: On partial parallel classes in partial Steiner triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659191)