Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userModerate deviations of subgraph counts in the ErdH{o}s-Renyi random graphs $G(n,m)$ and $G(n,p)$
126
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the ErdH{o}s-Renyi random graph $G(n,m)$. Our approach is based on applying Freedmans inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.
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 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 finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. ErdH{o}s posed the following problem in 1990: For which graphs $H$ is it true that every graph on $n$ vertices and ${rm ex}(n,H)+1$ edges contains at least two $H$s? Perhaps this is always true. We solve the second part of this problem in the negative by proving that for every integer $kge 4,$ there exists a graph $H$ of order $k$ and at least two orders $n$ such that there exists a graph of order $n$ and size ${rm ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$-cycle. We also prove that for every integer $n$ with $6le nle 11,$ there exists a graph of order $n$ and size ${rm ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order $n$ and size ${rm ex}(n,C_4)+1$ is $2.$
We study the homological algebra of edge ideals of Erd{o}s-Renyi random graphs. These random graphs are generated by deleting edges of a complete graph on $n$ vertices independently of each other with probability $1-p$. We focus on some aspects of these random edge ideals - linear resolution, unmixedness and algebraic invariants like the Castelnuovo-Mumford regularity, projective dimension and depth. We first show a double phase transition for existence of linear presentation and resolution and determine the critical windows as well. As a consequence, we obtain that except for a very specific choice of parameters (i.e., $n,p := p(n)$), with high probability, a random edge ideal has linear presentation if and only if it has linear resolution. This shows certain conjectures hold true for large random graphs with high probability even though the conjectures were shown to fail for determinstic graphs. Next, we study asymptotic behaviour of some algebraic invariants - the Castelnuovo-Mumford regularity, projective dimension and depth - of such random edge ideals in the sparse regime (i.e., $p = frac{lambda}{n}, lambda in (0,infty)$). These invariants are studied using local weak convergence (or Benjamini-Schramm convergence) and relating them to invariants on Galton-Watson trees. We also show that when $p to 0$ or $p to 1$ fast enough, then with high probability the edge ideals are unmixed and for most other choices of $p$, these ideals are not unmixed with high probability. This is further progress towards the conjecture that random monomial ideals are unlikely to have Cohen-Macaulay property (see De Loera et al. 2019a,2019b) in the setting when the number of variables goes to infinity but the degree is fixed.
A multi-class single-server system with general service time distributions is studied in a moderate deviation heavy traffic regime. In the scaling limit, an optimal control problem associated with the model is shown to be governed by a differential game that can be explicitly solved. While the characterization of the limit by a differential game is akin to results at the large deviation scale, the analysis of the problem is closely related to the much studied area of control in heavy traffic at the diffusion scale.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
