Cliques in dense inhomogeneous random graphs1. Issue 2 (4th April 2017)

• Record Type: Journal Article
• Authors: Doležal, Martin; Hladký, Jan; Máthé, András
• Is Part Of: Random structures & algorithms. Volume 51:Issue 2(2017)
• Page Start: 275
• Page End: 314
• Publication Date: 2017-04-04
• Subjects: random graphs -- graph limits -- clique number; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20715
• Languages: English
• ISSNs: 1042-9832

Abstract

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