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 \left(\genfrac{}{}{0ex}{}{r}{2}\right)$ edges. It was recently shown that ${\omega }^{(\gamma )}(G)$ is highly concentrated when $G$ is an Erdős-Rényi random graph (Balister, Bollobás, 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$.