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)

Abstract

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.

Keywords

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

Edition

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

For citation

Kuzyrin N.N., Lazarev D.O. Analysis of size of the largest dense subgraph of random hypergraph. Proceedings of the Institute for System Programming, vol. 29, issue 6, 2017, pp. 213-220. DOI: 10.15514/ISPRAS-2017-29(6)-12.

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