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

Diskr. Mat., 2006 Volume 18, Issue 3, Pages 102–114 (Mi dm63)

This article is cited in 2 papers

The distributions of the numbers of finite subgraphs in random nonhomogeneous hypergraphs

A. V. Shapovalov


Abstract: We consider two random hypergraphs with $n$ vertices and $M=M(n)$ edges among which $M_i=M_i(n)$ edges consist of $i$ non-ordered vertices, $i=0,1,\dots,m$, $M=M_0+M_1+\ldots+M_m$. The choice of vertices for each edge is realised by equiprobable sampling with replacement from $n$ possible vertices for the former random hypergraph and by that without replacement for the latter one. We investigate the distribution of the numbers of subgraphs isomorphic to given subgraphs as $n\to\infty$, $M=M(n)$. The notion of degree and balanced subgraphs are extended to nonhomogeneous hypergraphs. The limit multivariate Poisson theorem for the numbers of strictly balanced subgraphs of equal degrees is obtained. A threshold function for presence of a subgraph isomorphic to an arbitrary finite hypergraph is constructed. Such results have been obtained for random graphs by P. Erdős, A. Rényi, B. Bollobás, and for homogeneous hypergraphs (that is, for $M=M_m$) by the author.

UDC: 519.2

Received: 10.06.2005

DOI: 10.4213/dm63


 English version:
Discrete Mathematics and Applications, 2006, 16:4, 371–383

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025