Bipodal optimizers in the upper-tail variational problem for regular subgraph densities
Abstract
Let H be a fixed d-regular graph with d≥2, and let t(H,·) denote its homomorphism density. We study the upper-tail event t(H,G(n,p))≥ r|E(H)| for fixed 0<p<r<1 in a dense Erdős--Rényi random graph G(n,p). Near the Lubetzky--Zhao replica-symmetric phase boundary and away from the exceptional target density (d−1)/d, we prove that the optimizer of the Chatterjee--Varadhan variational problem on the symmetry-breaking side is bipodal (two-block) and unique up to relabeling. Its block parameters depend analytically on (p,r). To treat the exceptional boundary point, where the nonexceptional theory degenerates, we construct an analytic curve approaching that point from the symmetry-breaking side along which the unique optimizers are nonconstant rank-one bipodal graphons. In both settings, we derive asymptotic expansions of the edge-density deficit and the rate function that governs the exponential decay of the upper-tail probability. Moreover, the conditioned random graph converges in cut distance to the corresponding bipodal optimizer as n→∞. As (p,r) approaches the phase boundary from the symmetry-breaking side, the optimizers converge to their constant limits through two distinct mechanisms. For each fixed nonexceptional target density, one block shrinks to zero measure, giving convergence in L1 but not in L∞. Along the exceptional curve, both blocks remain macroscopic: their sizes tend to 1/2 and all three block densities tend to (d−1)/d, yielding convergence in L∞.
Related
- Large-scale empirical tuning and comparison of default optimizers for variational inference
- Uniqueness results for the exterior Dirichlet and Neumann problem in two dimensions for the Euler-Lagrange equations of variational integrals with linear growth
- Variational properties of Perron's extremal solutions in the Bernoulli one-phase problem
- Integrable distortion II: the p-Weil-Petersson variational problem
- A Spanning Subgraph of Conway's 99-graph
BibTeX
@misc{lim2026bipodal,
title = {{Bipodal optimizers in the upper-tail variational problem for regular subgraph densities}},
author = {Sangho Lim and Seonghyuk Im and Taeyoung Kim and Kyeongsik Nam and Hongseok Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15222},
eprint = {2609.15222},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15222},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bipodal optimizers in the upper-tail variational problem for regular subgraph densities
AU - Sangho Lim
AU - Seonghyuk Im
AU - Taeyoung Kim
AU - Kyeongsik Nam
AU - Hongseok Yang
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15222
UR - https://arxiv.org/abs/2609.15222
AB - Let H be a fixed d-regular graph with d≥2, and let t(H,·) denote its homomorphism density. We study the upper-tail event t(H,G(n,p))≥ r^|E(H)| for fixed 0<p<r<1 in a dense Erdős--Rényi random graph G(n,p). Near the Lubetzky--Zhao replica-symmetric phase boundary and away from the exceptional target density (d−1)/d, we prove that the optimizer of the Chatterjee--Varadhan variational problem on the symmetry-breaking side is bipodal (two-block) and unique up to relabeling. Its block parameters depend analytically on (p,r). To treat the exceptional boundary point, where the nonexceptional theory degenerates, we construct an analytic curve approaching that point from the symmetry-breaking side along which the unique optimizers are nonconstant rank-one bipodal graphons. In both settings, we derive asymptotic expansions of the edge-density deficit and the rate function that governs the exponential decay of the upper-tail probability. Moreover, the conditioned random graph converges in cut distance to the corresponding bipodal optimizer as n→∞. As (p,r) approaches the phase boundary from the symmetry-breaking side, the optimizers converge to their constant limits through two distinct mechanisms. For each fixed nonexceptional target density, one block shrinks to zero measure, giving convergence in L^1 but not in L^∞. Along the exceptional curve, both blocks remain macroscopic: their sizes tend to 1/2 and all three block densities tend to (d−1)/d, yielding convergence in L^∞.
ER -