Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T20:03:32.849Z Has data issue: false hasContentIssue false
  • English
  • Français

Subgraph counts for dense random graphs with specified degrees

Part of: Combinatorics Graph theory

Published online by Cambridge University Press:  05 November 2020

Catherine Greenhill ,
Mikhail Isaev  and
Brendan D. McKay
Catherine Greenhill*
Affiliation:
School of Mathematics and Statistics, UNSW Sydney, NSW2052, Australia
Mikhail Isaev
Affiliation:
School of Mathematical Sciences, Monash University, VIC3800, Australia
Brendan D. McKay
Affiliation:
Research School of Computer Science, Australian National University, ACT2601, Australia
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 05A16: Asymptotic enumeration
Secondary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 3 , May 2021 , pp. 460 - 497
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported by Australian Research Council Discovery Project DP190100977.

References

Barron, E. N., Cardaliaguet, P. and Jensen, R. (2003) Conditional essential suprema with applications. Appl. Math. Optim. 48 229–253.Google Scholar
Erdős, P. and Gallai, T. (1960) Graphs with prescribed degrees of vertices (Hungarian). Mat. Lapok 11 264–274.Google Scholar
Greenhill, C., Isaev, M., Kwan, M. and McKay, B. D. (2017) The average number of spanning trees in sparse graphs with given degrees. European J. Combin 63 6–25.CrossRefGoogle Scholar
Isaev, M. and McKay, B. D. (2018) Complex martingales and asymptotic enumeration. Random Struct. Algorithms 52 617–661.Google Scholar
Kim, J. H., Sudakov, B. and Vu, V. (2007) Small subgraphs of random regular graphs. Discrete Math. 307 1961–1967.Google Scholar
Krivelevich, M., Sudakov, B., Vu, V. H. and Wormald, N. C. (2001) Random regular graphs of high degree. Random Struct. Algorithms 13 346–363.CrossRefGoogle Scholar
McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 of Algorithms and Combinatorics, pp. 195–248. Springer.Google Scholar
McKay, B. D. (1985) Asymptotics for symmetric 0–1 matrices with prescribed row sums. Ars Combin. 19A 15–26.Google Scholar
McKay, B. D. (2011) Subgraphs of dense random graphs with specified degrees. Combin. Probab. Comput. 20 413–433.Google Scholar
McKay, B. D. and Wormald, N. C. (1990) Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11 565–580.Google Scholar
Moon, J. W. (1970) Counting Labelled Trees, Vol. 1 of Canadian Mathematical Monographs. Canadian Mathematical Congress.Google Scholar
Xiao, L., Yan, G., Wu, Y. and Ren, W. (2008) Induced subgraph in random regular graph. J. Systems Sci. Complexity 21 645–650.CrossRefGoogle Scholar