Super-logarithmic cliques in dense inhomogeneous random graphs

Abstract

In the theory of dense graph limits, a graphon is a symmetric measurable function $W:[0,1{]}^2\to [0,1]$. Each graphon gives rise naturally to a random graph distribution, denoted $\mathbb{G}(n,W)$, that can be viewed as a generalization of the Erdős-Rényi random graph. Recently, Doležal, Hladký, and Máthé gave an asymptotic formula of order $\log n$ for the clique number of $\mathbb{G}(n,W)$ when $W$ is bounded away from 0 and 1. We show that if $W$ is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of $\mathbb{G}(n,W)$ will be $\Theta (\sqrt{n})$ almost surely. We also give a family of examples with clique number $\Theta (n^{\alpha })$ for any $\alpha \in (0,1)$, and some conditions under which the clique number of $\mathbb{G}(n,W)$ will be $o(\sqrt{n})$, $\omega (\sqrt{n}),$ or $\Omega (n^{\alpha })$ for $\alpha \in (0,1)$.

27 pages; a few additions made to introduction and acknowledgments