Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA sample-path large deviation principle for dynamic ErdH{o}s-Renyi random graphs
145
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a symmetric phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a symmetry breaking regime, where the conditional structure is not a block model with compatible dimensions. This identifies a reentrant phase transition phenomenon for this problem---analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
