Dense subgraphs of power-law random graphs

摘要

The problem of finding a maximal dense subgraph of a power-law random graph $G(n,alpha)$ is considered for every value of density $c in (0,1)$ and for every $alpha in (0, +infty)$. It is shown that in case $alpha 2$ a maximal $c$-dense subgraph has size $Theta_p ( n^{1-alpha/2} ) $, in case $alpha = 2$ it is limited whp, and in case $alpha 2$ it is whp less than $frac{4}{c}$.