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

School of Mathematics

Research output: Contribution to journal › Article › Research › 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(d1, ⋯, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj = λn + O(n1/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 - May 2021

Access to Document

10.1017/S0963548320000498Licence: Unspecified

Cite this

@article{fb2ed55d83644c2da555a296832f96f7,

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(d1, ⋯, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj = λn + O(n1/2+ϵ) for some λ bounded away from 0 and 1.",

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

year = "2021",

month = may,

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

Y1 - 2021/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(d1, ⋯, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj = λn + O(n1/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(d1, ⋯, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj = λn + O(n1/2+ϵ) for some λ bounded away from 0 and 1.

UR - http://www.scopus.com/inward/record.url?scp=85095790506&partnerID=8YFLogxK

U2 - 10.1017/S0963548320000498

DO - 10.1017/S0963548320000498

M3 - Article

AN - SCOPUS:85095790506

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

Hypergraph models for complex discrete systems

Cite this

Subgraph counts for dense random graphs with specified degrees

Abstract

Access to Document

Other files and links

Projects

Hypergraph models for complex discrete systems

Cite this