Труды Института системного программирования РАН (Oct 2018)

Analysis of size of the largest dense subgraph of random hypergraph

  • N. N. Kuzyrin,
  • D. O. Lazarev

DOI
https://doi.org/10.15514/ISPRAS-2017-29(6)-12
Journal volume & issue
Vol. 29, no. 6
pp. 213 – 220

Abstract

Read online

Random networks are often described using Erdos-Renyi model of random graph . 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 was evaluated. It was shown, that if , then is almost surely c-dense; the upper and lower bounds for the size of maximal -dense subgraph almost surely included in were determined; in case when , the upper bound for the maximal size of c-dense subgraph almost surely included in was attained.

Keywords