Block-avoiding point sequencings

Simon R. Blackburn

Published 2020-01-24Version 1

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) so that no block occurs in a short segment of consecutive entries (so the ordering is locally block-avoiding). The paper describes a greedy algorithm which shows that such an ordering exists, provided the number of points is sufficiently large. 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 (for example, orderings that avoid the blocks of a block design). Similar results for a cyclic variant of this situation are also established. The results above 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 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})$.