RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2007 Volume 19, Issue 4, Pages 52–69 (Mi dm977)

This article is cited in 3 papers

The cycle structure of a random nonhomogeneous hypergraph on the subcritical stage of evolution

A. V. Shapovalov


Abstract: We consider a random nonhomogeneous hypergraph on $n$ vertices with $M=M(n)$ edges, $M_i=M_i(n)$ edges consist of $i$ vertices,
\begin{gather*} \lim_{n\to\infty}M_i/M=c_i,\quad c_i\ge0,\quad i=0,1,\dots,m,\\ c_0+c_1+\dots+c_m=1,\quad M=M_0+M_1+\dots+M_m. \end{gather*}
For each edge, vertices are chosen by random and equiprobable sampling with replacement out of $n$ vertices. Under the condition that $n\to\infty$ and
$$ 0<\lim_{n\to\infty}\frac Mn<\Biggl(\sum_{i=2}^mc_ii(i-1)\Biggr)^{-1} $$
we show that the probability that the random hypergraph consists of hypertrees and components with one cycle tends to one. Similar results for random graphs and random homogeneous hypergraphs have been obtained earlier.

UDC: 519.2

Received: 10.06.2005

DOI: 10.4213/dm977


 English version:
Discrete Mathematics and Applications, 2007, 17:5, 475–493

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025