Block avoiding point sequencings of partial Steiner systems
| Autor: | Horsley, Daniel, Catháin, Padraig Ó |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Des. Codes Cryptogr. 90 (2022) 2375-2383 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s10623-022-01085-5 |
| Popis: | 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$-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)_\lambda$-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((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 $\ell$-good sequencing for each positive integer $\ell \leq 0.0908\,n^{1/2}$. Comment: 9 pages, 0 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|