2009/05/05 by Svante Janson, Janson, Svante, Tomasz Łuczak +3
Mathematics · #05C69 #05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C69 #msc:05C80 #msc:60C05
paper · pdf · doi:10.48550/arxiv.0905.0561
13 pages
arxiv created 2009/05/05 · arxiv updated 2009/12/01
We study the size of the largest clique ω(G(n,α)) in a random graph G(n,α) on n vertices which has power-law degree distribution with exponent α. We show that for `flat' degree sequences with α>2 whp the largest clique in G(n,α) is of a constant size, while for the heavy tail distribution, when 0<α<2, ω(G(n,α)) grows as a power of n. Moreover, we show that a natural simple algorithm whp finds in G(n,α) a large clique of size (1+o(1))ω(G(n,α)) in polynomial time.