Super-logarithmic cliques in dense inhomogeneous random graphs

2019/03/04 by McKinley, Gweneth · 1 citation
#05C69 (Secondary) #05C80 (Primary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1903.01495

Abstract

In the theory of dense graph limits, a graphon is a symmetric measurable function W:[0,1]²→ [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted \mathbbG(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 \mathbbG(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 \mathbbG(n,W) will be Θ(√(n)) almost surely. We also give a family of examples with clique number Θ(n^α) for any α∈(0,1), and some conditions under which the clique number of \mathbbG(n,W) will be o(√(n)), ω(√(n)), or Ω(n^α) for α∈(0,1).

Cited by

• Inhomogeneous random 2-SAT

Related

• Counting cliques in a random graph
• First-order asymptotics for the structure of the inhomogeneous random graph
• Clique packings in random graphs
• Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups
• The Erdős-Rényi Random Graph Conditioned on Every Component Being a Clique