Block avoiding point sequencings of partial Steiner systems

DOI10.1007/S10623-022-01085-5MaRDI QIDQ2673985zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Horsley, Padraig Ó Catháin

Publication date 22 September 2022

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2111.00858

zbMATH Keywords

point orderingpoint sequencingSteiner system

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Triple systems (05B07)

Abstract: A partial $(n,k,t{)}_{l}ambda$-system is a pair $(X,mathcalB)$ where $X$ is an $n$-set of vertices and $mathcalB$ is a collection of $k$-subsets of $X$ called blocks such that each $t$-set of vertices is a subset of at most $lambda$ blocks. A sequencing of such a system is a labelling of its vertices with distinct elements of $0,ldots,n-1$. A sequencing is $ell$-block avoiding or, more briefly, $ell$-good if no block is contained in a set of $ell$ vertices with consecutive labels. Here we give a short proof that, for fixed $k$, $t$ and $lambda$, any partial $(n,k,t{)}_{l}ambda$-system has an $ell$-good sequencing for some $ell=Theta(n^{1/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"{e}te show that the value of $ell$ cannot be increased beyond $Theta((nlogn{)}^{1/t})$. A special case of our result shows that every partial Steiner triple system (partial $(n,3,2{)}_1$-system) has an $ell$-good sequencing for each positive integer $ellleq0.0908,n^{1/2}$.

Review text

A partial \((n, k, t)_\lambda\)-system is a pair\((X, \mathcal{B})\) where \(X\) is an \(n\)-set of vertices and \(\mathcal{B}\) is a collection of \(k\)-subsets of \(X\) called blocks such that each \(t\)-set of vertices is a subset of at most \(\lambda\) blocks. A sequencing of such a system is a labelling of its vertices with distinct elements of \(\{0,\ldots, n-1\}\). A sequencing is \(\ell\)-good if no block is contained in a set of \(\ell\) vertices with consecutive labels. In the paper, some new results are presented: when \(n\) became large and when the parameters \(k\), \(t\), \(\lambda\) and \(\ell\) satisfied certain conditions, any partial \((n, k, t)_\lambda\)-system has an \(\ell\)-good sequencing. So, the results of \textit{S. R. Blackburn} and \textit{T. Etzion} [``Block-avoiding point sequencings, J. Comb. Des. 29, No. 6, 339--366 (2021; \url{doi:10.1002/jcd.21770})] are improved as well as those of \textit{D. R. Stinson} and \textit{S. Veitch} [Australas. J. Comb. 77, Part 1, 87--99 (2020; Zbl 1444.05026)]. As an application, when some parameters took special values, this paper also got some concrete examples, which are shown in the form of corollaries.

Recommendations

• Block-avoiding sequencings of points in Steiner triple systems
• On partial parallel classes in partial Steiner triple systems
• Block-avoiding point sequencings of arbitrary length in Steiner triple systems
• Block partitions of sequences
• Good point sequencings of Steiner triple systems
• An extremal problem on potentially \(K_{p,1,1}\)-graphic sequences
• scientific article; zbMATH DE number 2246360
• scientific article; zbMATH DE number 67598
• Nonsequenceable Steiner triple systems
• Note on asymptotically good packings

Cites work

• Block-avoiding point sequencings of arbitrary length in Steiner triple systems
• Block-avoiding point sequencings of directed triple systems
• Block-avoiding point sequencings of Mendelsohn triple systems
• Block-avoiding sequencings of points in Steiner triple systems
• Block‐avoiding point sequencings
• Note on independent sets in steiner systems
• On independent sets in hypergraphs
• On the chromatic number of set systems
• On the independence number of Steiner systems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(7)

• Block-avoiding point sequencings of Mendelsohn triple systems
• Block-avoiding point sequencings of arbitrary length in Steiner triple systems
• Good point sequencings of Steiner triple systems
• Block-avoiding sequencings of points in Steiner triple systems
• Nonsequenceable Steiner triple systems
• Block‐avoiding point sequencings
• Sequencing Partial Steiner Triple Systems

This page was built for publication: Block avoiding point sequencings of partial Steiner systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673985)