Block-avoiding point sequencings. / Blackburn, Simon; Etzion, Tuvi.

In: Journal of Combinatorial Designs, 02.02.2021.

Research output: Contribution to journalArticlepeer-review

E-pub ahead of print


  • Accepted Manuscript

    Accepted author manuscript, 339 KB, PDF document

    Embargo ends: 2/02/22


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+\oh(k^{2/3})$.
Original languageEnglish
JournalJournal of Combinatorial Designs
Early online date2 Feb 2021
Publication statusE-pub ahead of print - 2 Feb 2021
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 41150486