Skip to main navigation Skip to search Skip to main content

Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon

  • University Paris 13
  • École des ponts

Research output: Contribution to journalArticlepeer-review

Abstract

We give asymptotics for the cumulative distribution function (CDF) for degrees of large dense random graphs sampled from a graphon. The proof is based on precise asymptotics for binomial random variables. This result is a first step for giving a nonparametric test for identifying the degree function of a large random graph. Replacing the indicator function in the empirical CDF by a smoother function, we get general asymptotic results for functionals of homomorphism densities for partially labeled graphs. This general setting allows to recover recent results on asymptotics for homomorphism densities of sampled graphon.

Original languageEnglish
Pages (from-to)94-149
Number of pages56
JournalRandom Structures and Algorithms
Volume58
Issue number1
DOIs
Publication statusPublished - 1 Jan 2021

Keywords

  • binomial distribution
  • cumulative distribution function of degrees
  • dense graph
  • graphon
  • homomorphism density
  • partially labeled graph
  • random measure

Fingerprint

Dive into the research topics of 'Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon'. Together they form a unique fingerprint.

Cite this