Very large cliques in a scale-free random graph

Abstract

In this short article we consider a preferential attachment random graph model with edge steps, studied by Alves, Ribeiro and Sanchis. Starting with an initial graph ${\mathbb{G}}_1$ formed by a vertex with a self-loop attached to it, the model evolves as follows. At every subsequent (discrete) time step, either with probability $p$ we add a vertex to the graph and connect it to exactly one of the older vertices selected with probability proportional to its degree, or with probability $1-p$ we add one edge between two existing vertices, both selected (independently) with probability proportional to their degrees. Let $\omega (\mathbb{G})$ be the clique number of a graph $\mathbb{G}$, i.e.\ the number of vertices in a largest complete subgraph of ${\mathbb{G}}_{}$. Alves, Ribeiro and Sanchis showed that, for any given $\epsilon >0$, we have $\omega ({\mathbb{G}}_{2t})\ge t^{\frac{1-p}{2-p}(1-\epsilon )}$ with high probability (i.e.\ with probability tending to $1$ as $t\to \infty$). Here we strengthen this bound by showing that, for any function $f:\mathbb{N}\mapsto \mathbb{N}$ that satisfies $f(t)\to \infty$ as $t\to \infty$, with high probability \[ω(\mathbb{G}_{2t}) = Ω\left(t^{\frac{1-p}{2-p}}\Big(\log^{\frac{1}{2-p}}(t)f(t)\Big)^{-1}\right).\]

12 pages