Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T10:56:35.061Z Has data issue: false hasContentIssue false

Subgraph counts for dense random graphs with specified degrees

Published online by Cambridge University Press:  05 November 2020

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]

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

Type
Paper
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 229253.Google Scholar
Erdős, P. and Gallai, T. (1960) Graphs with prescribed degrees of vertices (Hungarian). Mat. Lapok 11 264274.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 625.CrossRefGoogle Scholar
Isaev, M. and McKay, B. D. (2018) Complex martingales and asymptotic enumeration. Random Struct. Algorithms 52 617661.Google Scholar
Kim, J. H., Sudakov, B. and Vu, V. (2007) Small subgraphs of random regular graphs. Discrete Math. 307 19611967.Google Scholar
Krivelevich, M., Sudakov, B., Vu, V. H. and Wormald, N. C. (2001) Random regular graphs of high degree. Random Struct. Algorithms 13 346363.CrossRefGoogle Scholar
McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 of Algorithms and Combinatorics, pp. 195248. Springer.Google Scholar
McKay, B. D. (1985) Asymptotics for symmetric 0–1 matrices with prescribed row sums. Ars Combin. 19A 1526.Google Scholar
McKay, B. D. (2011) Subgraphs of dense random graphs with specified degrees. Combin. Probab. Comput. 20 413433.Google Scholar
McKay, B. D. and Wormald, N. C. (1990) Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11 565580.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 645650.CrossRefGoogle Scholar