Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph

2020/07/25 by Cristian Giardinà, Giardinà, Cristian, Claudio Giberti +3
Mathematics · Physics and Astronomy · #05C35 #05C80 #82B26 #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #math-ph #math.MP #math.PR #msc:05C35 #msc:05C80 #msc:82B26

paper · pdf · doi:10.48550/arxiv.2007.12971

19 pages, 11 figures

arxiv created 2021/01/08 · arxiv updated 2021/01/11

Abstract

We study the pressure of the "edge-triangle model", which is equivalent to the cumulant generating function of triangles in the Erdös-Rényi random graph. By analyzing finite graphs of increasing volume, as well as the graphon variational problem in the infinite volume limit, we locate a curve in the parameter space where a one-step replica symmetry breaking transition occurs. Sampling a large graph in the broken symmetry phase is well described by a graphon with a structure very close to the one of an equi-bipartite graph.

Related

• Limit theorems for exponential random graphs
• A variant of the Erdos-Renyi random graph process
• Statistics for the triangle density in ERGM and its mean-field approximation
• The large deviation principle for the Erdős-Rényi random graph
• Limit theorems for walks and triangles on Erdös-Rényi random graphs with large interaction radius