Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T06:19:50.805Z Has data issue: false hasContentIssue false

Large Cliques in a Power-Law Random Graph

Published online by Cambridge University Press:  14 July 2016

Svante Janson*
Affiliation:
Uppsala University
Tomasz Łuczak*
Affiliation:
Adam Mickiewicz University
Ilkka Norros*
Affiliation:
VTT Technical Research Centre of Finland
*
∗ Postal address: Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden. Email address: svante.janson@math.uu.se
∗∗ Postal address: Faculty of Mathematics and Computer Science, Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznań, Poland. Email address: tomasz@amu.edu.pl
∗∗∗ Postal address: VTT Technical Research Centre of Finland, PO Box 1000, 02044 VTT, Finland. Email address: ilkka.norros@vtt.fi
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2010