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

arXiv2007.12490MaRDI QIDQ6345762FDOQ6345762

Authors: Fang Tian 

Publication date: 23 July 2020

Abstract: For given integers $r$ and $ell$ such that $2leqslantellleqslantr-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 $$ 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 $fracnrlogn$ and the very edge which links the last isolated vertex with another vertex makes the partial Steiner $(n,r,ell)$-system connected.

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

This page was built for publication: On partial Steiner $(n,r,\ell)$-system process

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