Exponential random graph models with soft clique constraints
Abstract
Let r≥3 be fixed, and let Gn be the set of all simple graphs with vertex set [n]={1,…,n}. We consider an exponential random graph model which gives higher probability to G ∈ Gn than to H ∈ Gn if G has fewer r-cliques than H. But all graphs in Gn have positive probability. The degree to which graphs with fewer r-cliques are given higher probability is determined by a positive weight w. We prove that, asymptotically almost surely as n → ∞, a random graph from Gn has a vertex partition into r−1 parts of roughly equal size, the density of edges between the parts is close to 1/2, and for every ε > 0 the density of edges within any part is less than ε. The asymptotic structural properties are independent of the weight w as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.
Related
- Critical fluctuations in the edge--triangle exponential random graph models
- Colorful Exponential Random Graph Models
- Clique counts under degree and matching constraints
- The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
BibTeX
@misc{tousinejad2026exponential,
title = {{Exponential random graph models with soft clique constraints}},
author = {Yasmin Tousinejad and Vera Koponen},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30869},
eprint = {2608.30869},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30869},
}
RIS
TY - UNPB
TI - Exponential random graph models with soft clique constraints
AU - Yasmin Tousinejad
AU - Vera Koponen
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30869
UR - https://arxiv.org/abs/2608.30869
AB - Let r≥3 be fixed, and let G_n be the set of all simple graphs with vertex set [n]={1,…,n}. We consider an exponential random graph model which gives higher probability to G ∈ G_n than to H ∈ G_n if G has fewer r-cliques than H. But all graphs in G_n have positive probability. The degree to which graphs with fewer r-cliques are given higher probability is determined by a positive weight w. We prove that, asymptotically almost surely as n → ∞, a random graph from G_n has a vertex partition into r−1 parts of roughly equal size, the density of edges between the parts is close to 1/2, and for every ε > 0 the density of edges within any part is less than ε. The asymptotic structural properties are independent of the weight w as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.
ER -