Cliques in dense inhomogenous random graphs

0506904 - ÚI 2020 RIV US eng J - Journal Article
Doležal, M. - Hladký, Jan - Máthé, A.
Cliques in dense inhomogenous random graphs.
Random Structures and Algorithms. Roč. 51, č. 2 (2017), s. 275-314. ISSN 1042-9832. E-ISSN 1098-2418
Institutional support: RVO:67985807
Keywords : random graphs * graph limits * clique number
OECD category: Pure mathematics
Impact factor: 0.985, year: 2017
Method of publishing: Open access

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant urn:x-wiley:10429832:media:rsa20715:rsa20715-math-0001 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 urn:x-wiley:10429832:media:rsa20715:rsa20715-math-0002 for each fixed n, and give examples of graphons for which urn:x-wiley:10429832:media:rsa20715:rsa20715-math-0003 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.
Permanent Link: http://hdl.handle.net/11104/0298042