Quasi-cliques in inhomogeneous random graphs

Abstract

Given a graph \(G\) and a constant \(\gamma \in [0,1]\), let \(\omega^{(\gamma)}(G)\) be the largest integer \(r\) such that there exists an \(r\)-vertex subgraph of \(G\) containing at least \(\gamma \binom{r}{2}\) edges. It was recently shown that \(\omega^{(\gamma)}(G)\) is highly concentrated when \(G\) is an Erd\H{o}s-R\'enyi random graph (Balister, Bollob\'as, Sahasrabudhe, Veremyev, 2019). This paper provides a simple method to extend that result to a setting of inhomogeneous random graphs, showing that \(\omega^{(\gamma)}(G)\) remains concentrated on a small range of values even if \(G\) is an inhomogeneous random graph. Furthermore, we give an explicit expression for \(\omega^{(\gamma)}(G)\) and show that it depends primarily on the largest edge probability of the graph \(G\).