Cliques in dense inhomogeneous random graphs
2017
The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant math formula of the Erdős–Renyi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of math formula for each fixed n, and give examples of graphons for which math formula 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. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
12
Citations
NaN
KQI