Fluctuations of subgraph counts in graphon based random graphs

DOI10.1017/S0963548322000335MaRDI QIDQ6091052zbMATH OpenFDO

Authors Bhaswar B. Bhattacharya, Anirban Chatterjee, Svante Janson

Publication date 23 November 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.07259

zbMATH Keywords

generalised \(U\)-statisticsgraphonsinhomogeneous random graphslimit theoremssubgraph counts

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Abstract: Given a graphon $W$ and a finite simple graph $H$, with vertex set $V(H)$, denote by $X_n(H,W)$ the number of copies of $H$ in a $W$-random graph on $n$ vertices. The asymptotic distribution of $X_n(H,W)$ was recently obtained by Hladk'y, Pelekis, and v{S}ileikis (2021) in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$. Towards this we introduce a notion of $H$-regularity of graphons and show that if the graphon $W$ is not $H$-regular, then $X_n(H,W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-frac12}$. On the other hand, if $W$ is $H$-regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H,W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centered chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$. Our proofs use the asymptotic theory of generalized $U$-statistics developed by Janson and Nowicki (1991). We also investigate the structure of $H$-regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$-regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H,W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$. We give an example of this degeneracy with $H=K_{1,3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher-order degeneracies.

Recommendations

• On Subgraph Sizes in Random Graphs
• Subgraphs of Random Graphs
• Upper tails for subgraph counts in random graphs
• Subgraph counts for dense random graphs with specified degrees
• Subgraph distributions in dense random regular graphs
• scientific article; zbMATH DE number 3943865
• Anti-concentration for subgraph counts in random graphs
• Random graphs and their subgraphs
• Distribution of subgraphs of random regular graphs

Cites work

• A central limit theorem for decomposable random variables with applications to random graphs
• A functional limit theorem for random graphs with applications to subgraph count statistics
• A limit theorem for small cliques in inhomogeneous random graphs
• Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon
• Asymptotic normality of graph statistics
• Berry-Esseen bounds for generalized U-statistics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Estimating and understanding exponential random graph models
• Gaussian Hilbert Spaces
• Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
• Higher-order fluctuations in dense random graph models
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3137662 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 5070369 (Why is no real title available?)
• Large networks and graph limits
• Limit theorems for distributions invariant under groups of transformations
• Limits of dense graph sequences
• Monochromatic subgraphs in randomly colored graphons
• On the statistics of vision: The Julesz conjecture
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Subgraph counts in random graphs using incomplete U-statistics methods
• The asymptotic distributions of generalized U-statistics with applications to random graphs
• The large deviation principle for the Erdős-Rényi random graph
• The phase transition in inhomogeneous random graphs
• Universal limit theorems in graph coloring problems with connections to extremal combinatorics
• Universality of the mean-field for the Potts model
• When are small subgraphs of a random graph normally distributed?

Cited in

(11)

• Gaussian fluctuations for edge counts in high-dimensional random geometric 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
• Gaussian fluctuations of generalized U-statistics and subgraph counting in the binomial random-connection model
• Fluctuation of the largest eigenvalue of a kernel matrix with application in graphon-based random graphs
• Normal to Poisson phase transition for subgraph counting in the random-connection model
• Hoeffding-type decomposition for U-statistics on bipartite networks
• Large deviation principles for graphon sampling
• Characterization of the asymptotic behaviour of U-statistics on row-column exchangeable matrices
• Functional central limit theorem for the subgraph count of the voter model on dynamic random graphs
• Higher-order graphon theory: fluctuations, degeneracies and inference

This page was built for publication: Fluctuations of subgraph counts in graphon based random graphs

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