Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge deviation for uniform graphs with given degrees
129
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Consider the random graph sampled uniformly from the set of all simple graphs with a given degree sequence. Under mild conditions on the degrees, we establish a Large Deviation Principle (LDP) for these random graphs, viewed as elements of the graphon space. As a corollary of our result, we obtain LDPs for functionals continuous with respect to the cut metric, and obtain an asymptotic enumeration formula for graphs with given degrees, subject to an additional constraint on the value of a continuous functional. Our assumptions on the degrees are identical to those of Chatterjee, Diaconis and Sly (2011), who derived the almost sure graphon limit for these random graphs.
rate research
Read More
For $ninmathbb N$ let $Theta^{(n)}$ be a random vector uniformly distributed on the unit sphere $mathbb S^{n-1}$, and consider the associated random probability measure $mu_{Theta^{(n)}}$ given by setting [ mu_{Theta^{(n)}}(A) := mathbb{P} left[ langle U, Theta^{(n)} rangle in A right],qquad U sim text{Unif}([-1,1]^n) ] for Borel subets $A$ of $mathbb{R}$. It is known that the sequence of random probability measures $mu_{Theta^{(n)}}$ converges weakly to the centered Gaussian distribution with variance $1/3$. We prove a large deviation principle for the sequence $mu_{Theta^{(n)}}$ with speed $n$ and explicit good rate rate function given by $I( u(alpha)) := - frac{1}{2} log ( 1 - ||alpha||_2^2)$ whenever $ u(alpha)$ is the law of a random variable of the form begin{align*} sqrt{1 - ||alpha||_2^2 } frac{Z}{sqrt 3} + sum_{ k = 1}^infty alpha_k U_k, end{align*} where $Z$ is standard Gaussian independent of $U_1,U_2,ldots$ which are i.i.d. $text{Unif}[-1,1]$, and $alpha_1 geq alpha_2 geq ldots $ is a non-increasing sequence of non-negative reals with $||alpha||_2<1$. We obtain a similar result for projections of the uniform distribution on the discrete cube ${-1,+1}^n$.
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.
Let $(a_k)_{kinmathbb N}$ be a sequence of integers satisfying the Hadamard gap condition $a_{k+1}/a_k>q>1$ for all $kinmathbb N$, and let $$ S_n(omega) = sum_{k=1}^ncos(2pi a_k omega),qquad ninmathbb N,;omegain [0,1]. $$ The lacunary trigonometric sum $S_n$ is known to exhibit several properties typical for sums of independent random variables. In this paper we initiate the investigation of large deviation principles (LDPs) for $S_n$. Under the large gap condition $a_{k+1}/a_ktoinfty$, we prove that $(S_n/n)_{ninmathbb N}$ satisfies an LDP with speed $n$ and the same rate function $tilde{I}$ as for sums of independent random variables with the arcsine distribution, but show that the LDP may fail to hold when we only assume the Hadamard gap condition. However, we prove that in the special case $a_k=q^k$ for some $qin {2,3,ldots}$, $(S_n/n)_{ninmathbb N}$ satisfies an LDP with speed $n$ and a rate function $I_q$ different from $tilde{I}$. We also show that $I_q$ converges pointwise to $tilde I$ as $qtoinfty$ and construct a random perturbation $(a_k)_{kinmathbb N}$ of the sequence $(2^k)_{kinmathbb N}$ for which $a_{k+1}/a_kto 2$ as $ktoinfty$, but for which $(S_n/n)_{ninmathbb N}$ satisfies an LDP with the rate function $tilde{I}$ as in the independent case and not, as one might na{i}vely expect, with rate function $I_2$. We relate this fact to the number of solutions of certain Diophantine equations. Our results show that LDPs for lacunary trigonometric sums are sensitive to the arithmetic properties of $(a_k)_{kinmathbb N}$. This is particularly noteworthy since no such arithmetic effects are visible in the central limit theorem by Salem and Zygmund or in the law of the iterated logarithm by Erdos and Gal. Our proofs use a combination of tools from probability theory, harmonic analysis, and dynamical systems.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
