# Large cliques in a power-law random graph - Mathematics > Combinatorics

Large cliques in a power-law random graph - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We study the size of the largest clique $\omegaGn,\alpha$ in a randomgraph $Gn,\alpha$ on $n$ vertices which has power-law degree distributionwith exponent $\alpha$. We show that for `flat- degree sequences with$\alpha>2$ whp the largest clique in $Gn,\alpha$ is of a constant size, whilefor the heavy tail distribution, when $0<\alpha<2$, $\omegaGn,\alpha$ growsas a power of $n$. Moreover, we show that a natural simple algorithm whp findsin $Gn,\alpha$ a large clique of size $1+o1\omegaGn,\alpha$ inpolynomial time.

Autor: Svante Janson, Tomasz Łuczak, Ilkka Norros

Fuente: https://arxiv.org/