Two star exponential random graph models (ERGMs) are an interesting special case of both general ERGMs and mean-field Ising models. In this paper, we study two star ERGMs conditioning on the edge density $p$. We begin with an analytic characterization of the replica symmetric region, where the conditional model is close in cut distance to the Erd\H{o}s--R\'enyi random graph $G(n,p)$. We prove that this region is twice as large as the corresponding region for the unconditional model. To study refined properties of the conditional model, we then analyze the global Kawasaki algorithm for sampling from it. Within the replica symmetric region, and under the additional condition that $4\beta p(1-p)<0.5$ when $|p-1/2|\lesssim 0.4632$, where $\beta$ is the model parameter, we prove metastable fast mixing of the Kawasaki algorithm. As corollaries, we obtain a weak Poincar\'e inequality and use it to deduce concentration inequalities of optimal order for conditional subgraph counts. The additional condition $4\beta p(1-p)<1/2$ if $|p-1/2|\lesssim 0.4632$ comes from our proof technique of contractive coupling. This bottleneck did not appear in previous studies applying the contractive coupling technique to unconditional ERGMs.
We consider the voter model on the giant component of a hyperbolic random graph, which is a spatial scale-free network, in the sparse and linear-giant regime $\alpha\in(1/2,1)$. We find that the quenched expected consensus time has order $n^{2-1/\alpha}$, as the number of vertices $n\to\infty$, with probability arbitra...
This paper derives a variational representation for the limiting free energy, whose maximizers determine the asymptotic structure of typical samples from the model, and establishes finite-temperature symmetry breaking for both these models and complement the rigorous results with numerical experiments.
B. Bhattacharya, Pierfrancesco Dionigi, Ankana Ganguly et al.· 0 citations
We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph $G(n,p)$. Here we aim for first-order asymptotics for the quantity $\mathbb{P}[X=k]$ with $X$ the number of triangles in $G(n,p)$ and $0 \le k \le (1-\epsilon) \mathbb{E}X$, in the sparse...
Jade Lintott, Will Perkins, Corrine Yap· 0 citations
Classical central limit theorems (CLTs) for log-partition functions of Ising models on Erd\H{o}s-R\'enyi random graphs lead to degenerate limits in the high-temperature regime when self-loops are absent. In this paper, we fill this surprising gap in the more general context of Ising models on inhomogeneous random graph...
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the...
We consider the adjacency matrix of a uniformly random simple $d$-regular graph on $N$ vertices. For every fixed $d\geq3$ and every fixed bulk energy, we prove that the rescaled eigenvalue point process converges to the $\mathrm{Sine}_1$ process with intensity $1/\pi$. We also establish universality of consecutive gaps...
