Large Cliques in a Power-Law Random Graph

• DOI: 10.1239/jap/1294170524
• Publication Date: 2011-01-04T20:20:29Z
• Authors: Svante Janson; Tomasz Łuczak; Ilkka Norros
• Keywords: clique; 05C69, 60C05; ta111; 05C80; Probability (math.PR); power-law random graph; 0102 computer and information sciences; 01 natural sciences; greedy algorithm; FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO); Mathematics - Probability; 05C80; 05C69, 60C05

In this paper 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, with high probability, 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 with high probability finds in G(n, α) a large clique of size (1 − o(1))ω(G(n, α)) in polynomial time.