scientific article; zbMATH DE number 3931058

From MaRDI portal
Publication:3705487





[For the entire collection see Zbl 0556.00015.] In this paper, the problem of multiple covering by edges the vertices of a hypergraph is considered. In particular, the two following models of random hypergraphs are considered: (i) the m edges are randomly drawn from the set of all the \(\left( \begin{matrix} n\\ h\end{matrix} \right)\) subsets of h vertices; (ii) for each edge the probability that it contains any given vertex is h/n, independently of any other vertex or edge. For both models, a threshold function \(m^ r(n)\) is derived for the property that there exists a multiple r-covering in a random hypergraph with n vertices and m edges. To this end, the number \(M^ r(n)\) of edges used to r-cover by the following simple procedure is analyzed: Choose the edges sequentially, one at a time, according either to model (i) or to model (ii), and stop when the selected edges represent an r-covering. It is shown that the sequence \(M^ r(n)\) possess a nondegenerate limit distribution, and a connection to extreme order statistics is then pointed out, enabling to explicitly derive the normalizing factors for obtaining convergence in law.











This page was built for publication:

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