Large deviations of subgraph counts for sparse Erdős–Rényi graphs

N Cook, A Dembo - Advances in Mathematics, 2020 - Elsevier
For any fixed simple graph H=(V, E) and any fixed u> 0, we establish the leading order of the
exponential rate function for the probability that the number of copies of H in the Erdős …

Upper tails via high moments and entropic stability

M Harel, F Mousset, W Samotij - Duke Mathematical Journal, 2022 - projecteuclid.org
Suppose that X is a bounded-degree polynomial with nonnegative coefficients on the p-
biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper …

Full large deviation principles for the largest eigenvalue of sub-Gaussian Wigner matrices

NA Cook, R Ducatez, A Guionnet - arXiv preprint arXiv:2302.14823, 2023 - arxiv.org
We establish precise estimates for the probability of rare events of the largest eigenvalue of
Wigner matrices with sub-Gaussian entries. In contrast to the case of Wigner matrices with …

Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices

F Augeri - arXiv preprint arXiv:2401.11925, 2024 - arxiv.org
Let $\Xi $ be the adjacency matrix of an Erd\H {o} sR\'enyi graph on $ n $ vertices and with
parameter $ p $ and consider $ A $ a $ n\times n $ centered random symmetric matrix with …

Spectral edge in sparse random graphs: Upper and lower tail large deviations

BB Bhattacharya, S Bhattacharya, S Ganguly - 2021 - projecteuclid.org
In this paper, we consider the problem of estimating the joint upper and lower tail large
deviations of the edge eigenvalues of an Erdős–Rényi random graph G n, p, in the regime of …

Large deviations in random Latin squares

M Kwan, A Sah, M Sawhney - Bulletin of the London …, 2022 - Wiley Online Library
In this note, we study large deviations of the number NN of intercalates (2× 2 2*2
combinatorial subsquares which are themselves Latin squares) in a random n× nn*\,n Latin …

Upper tails for edge eigenvalues of random graphs

BB Bhattacharya, S Ganguly - SIAM Journal on Discrete Mathematics, 2020 - SIAM
The upper tail problem for the largest eigenvalue of the Erdös--Rényi random graph G_n,p
is to estimate the probability that the largest eigenvalue of the adjacency matrix of G_n,p …

Large deviations of the largest eigenvalue of supercritical sparse Wigner matrices

F Augeri, A Basak - arXiv preprint arXiv:2304.13364, 2023 - arxiv.org
Consider a random symmetric matrix with iid~ entries on and above its diagonal that are
products of Bernoulli random variables and random variables with sub-Gaussian tails. Such …

Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

S Ganguly, K Nam - Probability Theory and Related Fields, 2022 - Springer
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 iid random conductances on the …

On the upper tail problem for random hypergraphs

YP Liu, Y Zhao - Random Structures & Algorithms, 2021 - Wiley Online Library
The upper tail problem in a random graph asks to estimate the probability that the number of
copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by …