skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Fluctuations of subgraph counts in graphon based random graphs
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ý, Pelekis, and Šileikis [17] 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)|-\frac{1}{2}}$$ . 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 centred 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 generalised $$U$$ -statistics developed by Janson and Nowicki [22]. 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.  more » « less
Award ID(s):
2046393
PAR ID:
10425511
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Combinatorics, Probability and Computing
Volume:
32
Issue:
3
ISSN:
0963-5483
Page Range / eLocation ID:
428 to 464
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Transactions of the American Mathematical Society)
    We develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdős-Rényi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime. As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an L 3 L^3 graphon. In particular, we define a notion of the critical window in this setting. The L 3 L^3 assumption ensures that the model is in the Erdős-Rényi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel’s RGIV model inside the critical window (see D.J. Aldous and B. Pittel [Random Structures Algorithms 17 (2000), pp. 79–102]). Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs (see E. Lubetzky and Y. Peled [Israel J. Math. 252 (2022), pp. 187–214]). In Bhamidi et al. [Scaling limits and universality II: geometry of maximal components in dynamic random graph models in the critical regime, In preparation], we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Ruciński and Wormald’s random graph process with degree restrictions provided an additional technical condition about the barely subcritical behavior of this model can be proved (see A. Ruciński and N. C. Wormald [Combin. Probab. Comput. 1 (1992), pp. 169–180]). 
    more » « less
  2. ; (, The Electronic Journal of Combinatorics)
    This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $$5 5$, any $L^p$-graphon $$w$$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of $$\Lambda(w)$$. When viewing $$w$$ as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless $$w$$. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of $$L^\infty$$-graphons was answered. 
    more » « less
  3. ; (, IFAC-PapersOnLine)
    We investigate the H-property for step-graphons. Specifically, we sample graphs G_n on n nodes from a step-graphon and evaluate the probability that G_n has a Hamiltonian decomposition in the asymptotic regime as n goes to infinity. It has been shown in our earlier work that for almost all step-graphons, this probability converges to either zero or one. We focus in this paper on the residual case where the zero-one law does not apply. We show that the limit of the probability still exists and provide an explicit expression of it. We present a complete proof of the result and validate it through numerical studies. 
    more » « less
  4. (, Random Structures & Algorithms)
    We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsityω(1/n): inhomogeneous random graphs with roughly equal expected degrees,W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results. 
    more » « less
  5. ; (, Random Structures & Algorithms)
    Call a hereditary family F of graphs strongly persistent if there exists a graphon W such that in all subgraphons W0 of W , F is precisely the class of finite graphs that have positive density in W0. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. We call graphons with the self-similarity property above weakly random. A hereditary family F is said to have the weakly random Erdos–Hajnal property (WR) if every graphon that is a limit of graphs in F has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with “few” prime graphs. We also extend some of the results above to structures in finite relational languages by using the theory of theons. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email