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

In: Journal of Combinatorial Designs, Vol. 29, No. 6, 06.2021, p. 339-366.

Research output: Contribution to journalArticlepeer-review

Published

Standard

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

In: Journal of Combinatorial Designs, Vol. 29, No. 6, 06.2021, p. 339-366.

Research output: Contribution to journalArticlepeer-review

Harvard

Blackburn, S & Etzion, T 2021, 'Block-avoiding point sequencings', Journal of Combinatorial Designs, vol. 29, no. 6, pp. 339-366. https://doi.org/10.1002/jcd.21770

APA

Blackburn, S., & Etzion, T. (2021). Block-avoiding point sequencings. Journal of Combinatorial Designs, 29(6), 339-366. https://doi.org/10.1002/jcd.21770

Vancouver

Blackburn S, Etzion T. Block-avoiding point sequencings. Journal of Combinatorial Designs. 2021 Jun;29(6):339-366. https://doi.org/10.1002/jcd.21770

Author

Blackburn, Simon ; Etzion, Tuvi. / Block-avoiding point sequencings. In: Journal of Combinatorial Designs. 2021 ; Vol. 29, No. 6. pp. 339-366.

BibTeX

@article{0a23279158994c1797487c0d345e84ee,
title = "Block-avoiding point sequencings",
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+\oh(k^{2/3})$.",
author = "Simon Blackburn and Tuvi Etzion",
year = "2021",
month = jun,
doi = "10.1002/jcd.21770",
language = "English",
volume = "29",
pages = "339--366",
journal = "Journal of Combinatorial Designs",
issn = "1520-6610",
publisher = "Wiley",
number = "6",

}

RIS

TY - JOUR

T1 - Block-avoiding point sequencings

AU - Blackburn, Simon

AU - Etzion, Tuvi

PY - 2021/6

Y1 - 2021/6

N2 - 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})$.

AB - 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})$.

U2 - 10.1002/jcd.21770

DO - 10.1002/jcd.21770

M3 - Article

VL - 29

SP - 339

EP - 366

JO - Journal of Combinatorial Designs

JF - Journal of Combinatorial Designs

SN - 1520-6610

IS - 6

ER -