Cliques in dense inhomogeneous random graphs1. Issue 2 (4th April 2017) - Doležal, Martin; Hladký, Jan; Máthé, András
Abstract: The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant G ( n, W ) of the Erdős–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of G ( n, W ) for each fixed n, and give examples of graphons for which G ( n, W ) exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017