On partial Steiner $(n,r,\ell )$-system process

Abstract

For given integers $r$ and $\ell$ such that $2⩽\ell ⩽r-1$, an $r$-uniform hypergraph $H$ is called a partial Steiner $(n,r,\ell )$-system, if every subset of size $\ell$ lies in at most one edge of $H$. In particular, partial Steiner $(n,r,2)$-systems are also called linear hypergraphs. The partial Steiner $(n,r,\ell )$-system process starts with an empty hypergraph on vertex set $[n]$ at time $0$, the $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ edges arrive one by one according to a uniformly chosen permutation, and each edge is added if and only if it does not overlap any of the previously-added edges in $\ell$ or more vertices. In this paper, we show with high probability, independent of $\ell$, the sharp threshold of connectivity in the algorithm is $\frac{n}{r}\log n$ and the very edge which links the last isolated vertex with another vertex makes the partial Steiner $(n,r,\ell )$-system connected.

part text overlap with arXiv:1908.06333

References in corpus (2)

• The existence of designs II
• On Wormald's differential equation method