Abstract

We prove concentration inequality results for geometric graph properties of an instance of the Cooper–Frieze [5] preferential attachment model with<jats:italic>edge-steps</jats:italic>. More precisely, we investigate a random graph model that at each time<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0021900221000206_inline1.png" /><jats:tex-math>$t\in \mathbb{N}$</jats:tex-math></jats:alternatives></jats:inline-formula>, with probability<jats:italic>p</jats:italic>adds a new vertex to the graph (a<jats:italic>vertex-step</jats:italic>occurs) or with probability<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0021900221000206_inline2.png" /><jats:tex-math>$1-p$</jats:tex-math></jats:alternatives></jats:inline-formula>an edge connecting two existent vertices is added (an<jats:italic>edge-step</jats:italic>occurs). We prove concentration results for the<jats:italic>global clustering coefficient</jats:italic>as well as the<jats:italic>clique number</jats:italic>. More formally, we prove that the global clustering, with high probability, decays as<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0021900221000206_inline3.png" /><jats:tex-math>$t^{-\gamma(p)}$</jats:tex-math></jats:alternatives></jats:inline-formula>for a positive function<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0021900221000206_inline4.png" /><jats:tex-math>$\gamma$</jats:tex-math></jats:alternatives></jats:inline-formula>of<jats:italic>p</jats:italic>, whereas the clique number of these graphs is, up to subpolynomially small factors, of order<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0021900221000206_inline5.png" /><jats:tex-math>$t^{(1-p)/(2-p)}$</jats:tex-math></jats:alternatives></jats:inline-formula>.</jats:p>