Analysis of size of the largest dense subgraph of random hypergraph
Random networks are often described using Erdos-Renyi model of random graph G(n,p). The concept of graph density is often used in random network analysis. In this article, the maximal size of c-dense subgraph almost surely included in random graph G(n,1/2) was evaluated. It was shown, that if c<1/2, then G(n,1/2) is almost surely c-dense; the upper and lower bounds for the size of maximal 1/2-dense subgraph almost surely included in G(n,1/2) were determined; in case when c>1/2 , the upper bound for the maximal size of c-dense subgraph almost surely included in G(n,1/2) was attained.
Proceedings of the Institute for System Programming, vol. 29, issue 6, 2017, pp. 213-220.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2017-29(6)-12Full text of the paper in pdf (in Russian) Back to the contents of the volume