Block‐avoiding point sequencings

DOI10.1002/JCD.21770MaRDI QIDQ6186657zbMATH OpenOpenAlexFDO

Authors Simon R. Blackburn, Tuvi Etzion

Publication date 2 February 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

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

zbMATH Keywords

point orderingpoint sequencingSteiner quadruple systemSteiner triple system

Mathematics Subject Classification ID

Triple systems (05B07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $n$ and $ell$ be positive integers. Recent papers by Kreher, Stinson and Veitch have explored variants of the problem of ordering the points in a triple system (such as a Steiner triple system, directed triple system or Mendelsohn triple system) on $n$ points so that no block occurs in a segment of $ell$ consecutive entries (thus the ordering is locally block-avoiding). We describe a greedy algorithm which shows that such an ordering exists, provided that $n$ is sufficiently large when compared to $ell$. This algorithm leads to improved bounds on the number of points in cases where this was known, but also extends the results to a significantly more general setting (which includes, for example, orderings that avoid the blocks of a design). Similar results for a cyclic variant of this situation are also established. We construct Steiner triple systems and quadruple systems where $ell$ can be large, showing that a bound of Stinson and Veitch is reasonable. Moreover, we generalise the Stinson--Veitch bound to a wider class of block designs and to the cyclic case. The results of Kreher, Stinson and Veitch were originally inspired by results of Alspach, Kreher and Pastine, who (motivated by zero-sum avoiding sequences in abelian groups) were interested in orderings of points in a partial Steiner triple system where no segment is a union of disjoint blocks. Alspach~emph{et al.} show that, when the system contains at most $k$ pairwise disjoint blocks, an ordering exists when the number of points is more than $15k-5$. By making use of a greedy approach, the paper improves this bound to $9k+O(k^{2/3})$.

Recommendations

• Block-avoiding point sequencings of arbitrary length in Steiner triple systems
• Block-avoiding sequencings of points in Steiner triple systems
• Block avoiding point sequencings of partial Steiner systems
• Block-avoiding point sequencings of Mendelsohn triple systems
• Good point sequencings of Steiner triple systems

Cites work

• Block-avoiding point sequencings of arbitrary length in Steiner triple systems
• Block-avoiding point sequencings of directed triple systems
• Block-avoiding point sequencings of Mendelsohn triple systems
• Block-avoiding sequencings of points in Steiner triple systems
• scientific article; zbMATH DE number 3912395 (Why is no real title available?)
• Lexicographic codes: Error-correcting codes from game theory
• Nonsequenceable Steiner triple systems
• On Quadruple Systems
• On strongly sequenceable abelian groups
• Some Remarks on the Triple Systems of Steiner.
• Towards a Large Set of Steiner Quadruple Systems
• Variations on the sequenceable theme
• Verification of a Conjecture of Th. Skolem.

Cited in

(2)

• Block avoiding point sequencings of partial Steiner systems
• Asymptotic existence of egalitarian Steiner 2-designs

This page was built for publication: Block‐avoiding point sequencings

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