Proceedings of ISP RAS

Analysis of size of the largest dense subgraph of random hypergraph

Kuzyrin N.N. (ISP RAS, Moscow, Russia; MIPT, Dolgoprudny, Moscow Region, Russia)
Lazarev D.O. (MIPT, Dolgoprudny, Moscow Region, Russia)


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.


random graph; Erdos-Renyi model; graph density; maximal dense subgraph


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)-12

Full text of the paper in pdf (in Russian) Back to the contents of the volume