Search

Let N be the number of triangles in an Erdős–Rényi graph G (n , p) on n vertices with edge density p = d / n , where d > 0 is a fixed constant. It is well known that N weakly converges to the Poisson distribution with mean d 3 / 6 as n → ∞ . We address the upper tail problem for N, namely, we investigate how fast k must grow, so that P (N ≥ k) is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when k 1 / 3 log k < (3 2 - o (1)) 2 / 3 log n (sub-critical regime) as well as pin down the tail behavior when k 1 / 3 log k > (3 2 + o (1)) 2 / 3 log n (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost k vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately (6 k) 1 / 3 . This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades and culminating in Harel et al. (Duke Math J 171(10):2089–2192, 2022), which analyzed the problem only in the regime p ≫ 1 n. The proofs rely on several novel graph theoretical results which could have other applications. [ABSTRACT FROM AUTHOR]

The exponential random graph model (ERGM) is a central object in the study of clustering properties in social networks as well as canonical ensembles in statistical physics. Despite some breakthrough works in the mathematical understanding of ERGM, most notably by Bhamidi, Bresler, and Sly [Ann. Appl. Probab. 21 (2011), pp. 2146–2170] through the analysis of a natural Heat-bath Glauber dynamics, and by Chatterjee and Diaconis [Ann. Statist. 41 (2013), pp. 2428–2461; Eldan [Geom. Funct. Anal. 28 (2018), pp. 1548–1596; and Eldan and Gross [Ann. Appl. Probab. 28 (2018), pp. 3698–3735] via a large deviation theoretic perspective, several basic questions have remained unanswered owing to the lack of exact solvability unlike the much studied Curie-Weiss model (Ising model on the complete graph). In this paper, we establish a series of new concentration of measure results for the ERGM throughout the entire sub-critical phase , including a Poincaré inequality, Gaussian concentration for Lipschitz functions, and a central limit theorem. In addition, a new proof of a quantitative bound on the W_1-Wasserstein distance to Erdős-Rényi graphs, previously obtained by Reinert and Ross [Ann. Appl. Probab. 29 (2019), pp. 3201–3229], is also presented. The arguments rely on translating temporal mixing properties of Glauber dynamics to static spatial mixing properties of the equilibrium measure and have the potential of being useful in proving similar functional inequalities for other Gibbsian systems beyond the perturbative regime. [ABSTRACT FROM AUTHOR]

Large deviation behavior of the largest eigenvalue λ 1 of Wigner matrices including those arising from an Erdős-Rényi random graph G n , p with i.i.d. random conductances on the edges has been the topic of considerable interest. However, despite several recent advances, not much is known when the underlying graph is sparse i.e., p → 0 , except the recent works (Bhattacharya et al., Ann Probab 49(4):1847–1885, 2021and Bhattacharya and Ganguly, SIAM J Discret Math, 2020) which consider the simpler case of the graph without additional edge weights. Under sufficiently general conditions on the conductance distribution, one expects the 'dense' behavior as long as the average degree np is at least logarithmic in n. In this article we focus on the case of constant average degree i.e., p = d n for some fixed d > 0 with standard Gaussian weights. Results in Bandeira and Van Handel (Ann Probab 44(4):2479–2506, 2016) about general non-homogeneous Gaussian matrices imply that in this regime λ 1 scales like log n. We prove the following results towards a precise understanding of the large deviation behavior in this setting. (Upper tail probabilities and structure theorem): For δ > 0 , we pin down the exact exponent ψ (δ) such that P (λ 1 ≥ 2 (1 + δ) log n) = n - ψ (δ) + o (1). Further, we show that conditioned on the upper tail event, with high probability, a unique maximal clique emerges with a very precise δ dependent size (takes either one or two possible values) and the Gaussian weights are uniformly high in absolute value on the edges in the clique. Finally, we also prove an optimal localization result for the leading eigenvector, showing that it allocates most of its mass on the aforementioned clique which is spread uniformly across its vertices. (Lower tail probabilities): The exact stretched exponential behavior P (λ 1 ≤ 2 (1 - δ) log n) = exp - n ℓ (δ) + o (1) is also established. As an immediate corollary, one obtains that λ 1 is typically (1 + o (1)) 2 log n , a result which surprisingly appears to be new. A key ingredient in our proofs is an extremal spectral theory for weighted graphs obtained by an ℓ 1 - reduction of the standard ℓ 2 - variational formulation of the largest eigenvalue via the classical Motzkin-Straus theorem [37], which could be of independent interest. [ABSTRACT FROM AUTHOR]