Horsley, DanielORCID: 0000-0001-9971-7148 and Ó Catháin, PadraigORCID: 0000-0002-7963-9688
(2022)
Good sequencings of partial Steiner systems.
0925-1022, 90
.
pp. 2375-2383.
ISSN Designs, Codes and Cryptography
A partial (n, k, t)λ-system is a pair(X, B) where X is an n-set of vertices and B is a collection
of k-subsets of X called blocks such that each t-set of vertices is a subset of at most λ
blocks. A sequencing of such a system is a labelling of its vertices with distinct elements
of {0,..., n − 1}. A sequencing is -block avoiding or, more briefly, -good if no block is
contained in a set of vertices with consecutive labels. Here we give a short proof that, for
fixed k, t and λ, any partial (n, k, t)λ-system has an -good sequencing for some = �(n1/t
)
as n becomes large. This improves on results of Blackburn and Etzion, and of Stinson and
Veitch. Our result is perhaps of most interest in the case k = t +1 where results of Kostochka,
Mubayi and Verstraëte show that the value of cannot be increased beyond �((n log n)1/t
).
A special case of our result shows that every partial Steiner triple system (partial (n, 3, 2)1-
system) has an -good sequencing for each positive integer 0.0908 n1/2.