Subgraph counts for dense random graphs with specified degrees

Catherine Greenhill; Mikhail Isaev; Brendan D. McKay

doi:10.1017/S0963548320000498

Subgraph counts for dense random graphs with specified degrees

Catherine Greenhill
, Mikhail Isaev
, Brendan D. McKay

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d 1 , ..., d n ) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes d j = λn + O(n 1/2+ϵ ) for some λ bounded away from 0 and 1.

Original language	English
Pages (from-to)	460-497
Number of pages	38
Journal	Combinatorics Probability and Computing
Volume	30
Issue number	3
DOIs	https://doi.org/10.1017/S0963548320000498
Publication status	Published - 5 May 2021

Access to Document

10.1017/S0963548320000498

Cite this

@article{23fa8c40038a47449e3c4e4f08f3e338,

title = "Subgraph counts for dense random graphs with specified degrees",

abstract = "We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d 1 , ..., d n ) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes d j = λn + O(n 1/2+ϵ ) for some λ bounded away from 0 and 1.",

author = "Catherine Greenhill and Mikhail Isaev and McKay, \{Brendan D.\}",

note = "Publisher Copyright: {\textcopyright} 2020 The Author(s). Published by Cambridge University Press.",

year = "2021",

month = may,

day = "5",

doi = "10.1017/S0963548320000498",

language = "English",

volume = "30",

pages = "460--497",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Subgraph counts for dense random graphs with specified degrees

AU - Greenhill, Catherine

AU - Isaev, Mikhail

AU - McKay, Brendan D.

PY - 2021/5/5

Y1 - 2021/5/5

N2 - We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d 1 , ..., d n ) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes d j = λn + O(n 1/2+ϵ ) for some λ bounded away from 0 and 1.

AB - We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d 1 , ..., d n ) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes d j = λn + O(n 1/2+ϵ ) for some λ bounded away from 0 and 1.

UR - https://www.scopus.com/pages/publications/85095790506

U2 - 10.1017/S0963548320000498

DO - 10.1017/S0963548320000498

M3 - Article

SN - 0963-5483

VL - 30

SP - 460

EP - 497

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -

Subgraph counts for dense random graphs with specified degrees

Abstract

Access to Document

Other files and links

Fingerprint

Cite this