
























We associate to a graphon $γ$ the sequence of $W$-random graphs $(G_n(γ))_{n \geq 1}$. We say that the graphon is singular if, for any finite graph $F$, the homomorphism density $t(F,G_n(γ))$ has a variance of order $O(n^{-2})$. This behavior is singular because generically, the density of a fixed finite graph $F$ in a $W$-random graph has a variance of order $O(n^{-1})$. We conjecture that the only singular graphons are the constant graphons $γ_p$ with $p \in [0,1]$, corresponding to the Erdős-Rényi random graphs $G(n,p)$. In this paper, we investigate the general properties of the singular graphons, and we show that they share many properties with the Erdős-Rényi random graphs. In particular, if $γ$ is a singular graphon, then the scaled densities $n(t(F,G_n(γ))-\mathbb{E}[t(F,G_n(γ))])$ converge in joint distribution. This generalises the central limit theorem satisfied by the Erdős-Rényi random graphs $G(n,p)$; however, the limiting distribution might be non-Gaussian if the conjecture does not hold. We also establish an equation satisfied by the characteristic polynomial of the Laplacian of the graph $G_n(γ)$ associated to a singular graphon; this opens the way to a spectral approach of the conjecture.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。