Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRegularity method and large deviation principles for the ErdH{o}s--Renyi hypergraph
173
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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 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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
