Subgraphs of Dense Random Graphs with Specified Degrees

DOI10.1017/S0963548311000034zbMath1226.05228arXiv1002.3018OpenAlexW2204568583WikidataQ105583878 ScholiaQ105583878MaRDI QIDQ2998852

Brendan D. McKay

Publication date: 11 May 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.3018

zbMATH Keywords

structure of a random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items

Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees, Threshold functions for small subgraphs in simple graphs and multigraphs, The spectral gap of random regular graphs, Threshold functions for small subgraphs: an analytic approach, Subgraph distributions in dense random regular graphs, Factorisation of the complete graph into spanning regular factors, Induced subgraphs in sparse random graphs with given degree sequences, The switch Markov chain for sampling irregular graphs and digraphs, Random graphs with a given degree sequence, Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges, Asymptotic enumeration of sparse uniform hypergraphs with given degrees, ASYMPTOTIC ENUMERATION OF SYMMETRIC INTEGER MATRICES WITH UNIFORM ROW SUMS, The number of graphs and a random graph with a given degree sequence, Counting loopy graphs with given degrees, Subgraph counts for dense random graphs with specified degrees, Sandwiching dense random regular graphs between binomial random graphs, Uniform generation of spanning regular subgraphs of a dense graph, The minimum number of spanning trees in regular multigraphs

Cites Work

• The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• The number of matchings in random regular graphs and bipartite graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration of tournaments with a given score sequence
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Random dense bipartite graphs and directed graphs with specified degrees
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• Probability Inequalities for Sums of Bounded Random Variables