Труды Института системного программирования РАН (Oct 2018)
Analysis of size of the largest dense subgraph of random hypergraph
Abstract
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