Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge deviation principle for the maximal eigenvalue of inhomogeneous ErdH{o}s-Renyi random graphs
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider an inhomogeneous ErdH{o}s-Renyi random graph $G_N$ with vertex set $[N] = {1,dots,N}$ for which the pair of vertices $i,j in [N]$, $i eq j$, is connected by an edge with probability $r(tfrac{i}{N},tfrac{j}{N})$, independently of other pairs of vertices. Here, $rcolon,[0,1]^2 to (0,1)$ is a symmetric function that plays the role of a reference graphon. Let $lambda_N$ be the maximal eigenvalue of the adjacency matrix of $G_N$. It is known that $lambda_N/N$ satisfies a large deviation principle as $N to infty$. The associated rate function $psi_r$ is given by a variational formula that involves the rate function $I_r$ of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of $psi_r$, specially when the reference graphon is of rank 1.
rate research
Read More
We consider a dynamic ErdH{o}s-Renyi random graph (ERRG) on $n$ vertices in which each edge switches on at rate $lambda$ and switches off at rate $mu$, independently of other edges. The focus is on the analysis of the evolution of the associated empirical graphon in the limit as $ntoinfty$. Our main result is a large deviation principle (LDP) for the sample path of the empirical graphon observed until a fixed time horizon. The rate is $binom{n}{2}$, the rate function is a specific action integral on the space of graphon trajectories. We apply the LDP to identify (i) the most likely path that starting from a constant graphon creates a graphon with an atypically large density of $d$-regular subgraphs, and (ii) the mostly likely path between two given graphons. It turns out that bifurcations may occur in the solutions of associated variational problems.
We develop a quantitative large deviations theory for random Bernoulli tensors. The large deviation principles rest on a decomposition theorem for arbitrary tensors outside a set of tiny measure, in terms of a novel family of norms generalizing the cut norm. Combined with associated counting lemmas, these yield sharp asymptotics for upper tails of homomorphism counts in the $r$-uniform ErdH{o}s--Renyi hypergraph for any fixed $rge 2$, generalizing and improving on previous results for the ErdH{o}s--Renyi graph ($r=2$). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields (joint) upper and lower tail asymptotics for other nonlinear functionals of interest.
We consider the statistics of the extreme eigenvalues of sparse random matrices, a class of random matrices that includes the normalized adjacency matrices of the ErdH{o}s-Renyi graph $G(N,p)$. Tracy-Widom fluctuations of the extreme eigenvalues for $pgg N^{-2/3}$ was proved in [17,46]. We prove that there is a crossover in the behavior of the extreme eigenvalues at $psim N^{-2/3}$. In the case that $N^{-7/9}ll pll N^{-2/3}$, we prove that the extreme eigenvalues have asymptotically Gaussian fluctuations. Under a mean zero condition and when $p=CN^{-2/3}$, we find that the fluctuations of the extreme eigenvalues are given by a combination of the Gaussian and the Tracy-Widom distribution. These results show that the eigenvalues at the edge of the spectrum of sparse ErdH{o}s-Renyi graphs are less rigid than those of random $d$-regular graphs [4] of the same average degree.
A wide array of random graph models have been postulated to understand properties of observed networks. Typically these models have a parameter $t$ and a critical time $t_c$ when a giant component emerges. It is conjectured that for a large class of models, the nature of this emergence is similar to that of the ErdH{o}s-Renyi random graph, in the sense that (a) the sizes of the maximal components in the critical regime scale like $n^{2/3}$, and (b) the structure of the maximal components at criticality (rescaled by $n^{-1/3}$) converges to random fractals. To date, (a) has been proven for a number of models using different techniques. This paper develops a general program for proving (b) that requires three ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent, (ii) scaling exponents of susceptibility functions are the same as that of the ErdH{o}s-Renyi random graph, and (iii) macroscopic averaging of distances between vertices in the barely subcritical regime. We show that these apply to two fundamental random graph models: the configuration model and inhomogeneous random graphs with a finite ground space. For these models, we also obtain new results for component sizes at criticality and structural properties in the barely subcritical regime.
We consider the empirical eigenvalue distribution of an $mtimes m$ principal submatrix of an $ntimes n$ random unitary matrix distributed according to Haar measure. For $n$ and $m$ large with $frac{m}{n}=alpha$, the empirical spectral measure is well-approximated by a deterministic measure $mu_alpha$ supported on the unit disc. In earlier work, we showed that for fixed $n$ and $m$, the bounded-Lipschitz distance between the empirical spectral measure and the corresponding $mu_alpha$ is typically of order $sqrt{frac{log(m)}{m}}$ or smaller. In this paper, we consider eigenvalues on a microscopic scale, proving concentration inequalities for the eigenvalue counting function and for individual bulk eigenvalues.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
