Horsley, Daniel ORCID: 0000-0001-9971-7148 and Ó Catháin, Padraig ORCID: 0000-0002-7963-9688 (2022) Good sequencings of partial Steiner systems. 0925-1022, 90 . pp. 2375-2383. ISSN Designs, Codes and Cryptography
Abstract
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.
Metadata
Item Type: | Article (Published) |
---|---|
Refereed: | Yes |
Uncontrolled Keywords: | Point sequencing; Point ordering; Steiner system |
Subjects: | Mathematics |
DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Humanities and Social Science > Fiontar agus Scoil na Gaeilge |
Publisher: | Springer |
Official URL: | https://doi.org/10.1007/s10623-022-01085-5 |
Copyright Information: | © 2022 The Authors. |
Funders: | Open Access funding enabled and organized by CAUL and its Member Institutions, Australian Research Council grants DP150100506 and FT160100048. |
ID Code: | 29110 |
Deposited On: | 05 Oct 2023 12:26 by Vidatum Academic . Last Modified 05 Oct 2023 12:26 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Creative Commons: Attribution 4.0 266kB |
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record