اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRegularity method and large deviation principles for the ErdH{o}s--Renyi hypergraph
173
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 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 empi
rical 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 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 pai
rs 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.
In this article, we develop a framework to study the large deviation principle for matrix models and their quantiz
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.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
