When are small subgraphs of a random graph normally distributed?

DOI10.1007/BF00718031MaRDI QIDQ1092512zbMATH OpenFDO

Authors Andrzej Ruciński

Publication date 1988

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00718031

zbMATH Keywords

asymptotically normally distributedPoisson convergencerandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Limit theorems in probability theory (60F99)

Review text

Let G be a graph and let \(X_ n\) count copies of G in a random graph K(n,p). The random variable \((X_ n-E(X_ n))/\sqrt{Var(X_ n)}\) is asymptotically normally distributed if and only if \(np^ m\to \infty\) and \(n^ 2(1-p)\to \infty\), where \(m=\max \{e(H)/| H| :\) \(H\subset G\}.\) In addition to, and in connection with this main result we investigate the formula for \(Var(X_ n)\) and the Poisson convergence of \(X_ n\).

Recommendations

• scientific article; zbMATH DE number 747034
• Upper tails for subgraph counts in random graphs
• Subgraph counts in random graphs using incomplete U-statistics methods
• Distribution of subgraphs of random regular graphs
• A functional limit theorem for random graphs with applications to subgraph count statistics

Cites work

• Every graph is contained in a sparsest possible balanced graph
• scientific article; zbMATH DE number 3889584 (Why is no real title available?)
• scientific article; zbMATH DE number 4041966 (Why is no real title available?)
• scientific article; zbMATH DE number 4087713 (Why is no real title available?)
• scientific article; zbMATH DE number 3620754 (Why is no real title available?)
• On random simplices in product distributions
• Poisson convergence and random graphs
• Strongly balanced graphs and random graphs
• Subgraph counts in random graphs using incomplete U-statistics methods

Cited in

(94)

• On the number of induced subgraphs of a random graph
• Subgraph counts in random graphs using incomplete U-statistics methods
• Convex hulls of dense balanced graphs
• Asymptotic normality of subcubes in random subgraphs of the \(n\)-cube
• On the number of subgraphs of a specified form embedded in a random graph
• When is a scale-free graph ultra-small?
• Threshold functions for small subgraphs: an analytic approach
• Central limit theorems in the configuration model
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• Upper tails for subgraph counts in random graphs
• Weighted dependency graphs
• Anti-concentration for subgraph counts in random graphs
• Stein's method of exchangeable pairs in multivariate functional approximations
• Large cycles in random generalized Johnson graphs
• Normal limiting distributions for systems of linear equations in random sets
• Upper tails via high moments and entropic stability
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Central limit theorems for patterns in multiset permutations and set partitions
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Unions of random trees and applications
• On the number of weakly connected subdigraphs in random \(k\)NN digraphs
• Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
• Normal approximation for sums of weighted \(U\)-statistics -- application to Kolmogorov bounds in random subgraph counting
• On the missing log in upper tail estimates
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
• Upper tail bounds for stars
• Local limit theorems via Landau-Kolmogorov inequalities
• The deletion method for upper tail estimates
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• A simplified second-order Gaussian Poincaré inequality in discrete setting with applications
• A large deviation result on the number of small subgraphs of a random graph
• Picker-chooser fixed graph games
• The lower tail: Poisson approximation revisited
• Distribution of the number of spanning regular subgraphs in random graphs
• The missing log in large deviations for triangle counts
• Sub-Gaussian tails for the number of triangles in G( n, p)
• A concentration result with application to subgraph count
• scientific article; zbMATH DE number 2127720 (Why is no real title available?)
• The probability of non-existence of a subgraph in a moderately sparse random graph
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• A functional limit theorem for random graphs with applications to subgraph count statistics
• Moderate deviations via cumulants
• Poisson convergence and semi-induced properties of random graphs
• On tree census and the giant component in sparse random graphs
• Asymptotic distributions in random graphs with applications to social networks
• Induced subgraphs in sparse random graphs with given degree sequences
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Fundamentals of Stein's method
• Concentration of non‐Lipschitz functions and applications
• Law of the iterated logarithm for random graphs
• KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDŐS–RÉNYI RANDOM GRAPH
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Normal approximation for generalized \(U\)-statistics and weighted random graphs
• Central limit theorem for statistics of subcritical configuration models
• The Distribution of Patterns in Random Trees
• A local central limit theorem for triangles in a random graph
• Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon
• The number of perfect matchings, and the nesting properties, of random regular graphs
• A limit theorem for small cliques in inhomogeneous random graphs
• The number of triangles in random intersection graphs
• scientific article; zbMATH DE number 7763253 (Why is no real title available?)
• Fluctuations of subgraph counts in graphon based random graphs
• Subgraph distributions in dense random regular graphs
• Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
• Kolmogorov bounds for decomposable random variables and subgraph counting by the Stein-Tikhomirov method
• Triangles and subgraph probabilities in random regular graphs
• The upper tail problem for induced 4‐cycles in sparse random graphs
• Local limit theorems for subgraph counts
• On the concentration of the chromatic number of random graphs
• Normal approximation of subgraph counts in the random-connection model
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Moderate deviations for functionals over infinitely many Rademacher random variables
• Local central limit theorem for triangle counts in sparse random graphs
• Functional central limit theorem for the simultaneous subgraph count of dynamic Erdős-Rényi random graphs
• Limit laws for the generalized Zagreb indices of random graphs
• Normal to Poisson phase transition for subgraph counting in the random-connection model
• Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime
• Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
• Degree of balance in random signed graphs
• Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
• Moderate deviations of triangle counts -- the lower tail (extended abstract)
• Berry-Esseen bounds for functionals of independent random variables
• Goodness-of-fit via count statistics in dense random simplicial complexes
• Functional central limit theorem for the subgraph count of the voter model on dynamic random graphs
• Uncovering a graph
• Normal approximation for subgraph count in random hypergraphs
• A short proof of a central limit theorem for the order of the giant component and k-core
• Higher-order graphon theory: fluctuations, degeneracies and inference
• Sparse random graphs with many triangles
• The behaviour of (n over \(k,\dots ,k,n-ik)c^ i/i!\) is asymptotically normal
• The asymptotic distributions of generalized U-statistics with applications to random graphs
• A transition of limiting distributions of large matchings in random graphs
• Variance of the subgraph count for sparse Erdős-Rényi graphs

This page was built for publication: When are small subgraphs of a random graph normally distributed?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092512)