ترغب بنشر مسار تعليمي؟ اضغط هنا

Large Deviation Principles for Block and Step Graphon Random Graph Models

152   0   0.0 ( 0 )
 نشر من قبل Oleg Pikhurko
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

Borgs, Chayes, Gaudio, Petti and Sen [arXiv:2007.14508] proved a large deviation principle for block model random graphs with rational block ratios. We strengthen their result by allowing any block ratios (and also establish a simpler formula for the rate function). We apply the new result to derive a large deviation principle for graph sampling from any given step graphon.



قيم البحث

اقرأ أيضاً

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 tai l 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.
In this article, we develop a framework to study the large deviation principle for matrix models and their quantiz
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 c ut 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.
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 s um $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.
110 - Xiaofeng Xue , Yumeng Shen 2020
In this paper, we are concerned with SIR epidemics in a random environment on complete graphs, where every edges are assigned with i.i.d. weights. Our main results give large and moderate deviation principles of sample paths of this model.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا