Subgraph counts for dense random graphs with specified degrees. (5th May 2021)

• Record Type: Journal Article
• Authors: Greenhill, Catherine; Isaev, Mikhail; McKay, Brendan D.
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 3(2021)
• Page Start: 460
• Page End: 497
• Publication Date: 2021-05-05
• Subjects: 05A16 -- 05C80; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000498
• Languages: English
• ISSNs: 0963-5483

Abstract

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.