Subgraphs of dense random graphs with specified degrees
From MaRDI portal
Abstract: Let d = (d1, d2, ..., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph. Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n. Our approach is the multidimensional saddle-point method. This extends the enumerative work of McKay and Wormald (1990) and is analogous to the theory developed for bipartite graphs by Greenhill and McKay (arXiv:math/0701600, 2009).
Recommendations
Cites work
- Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
- Asymptotic enumeration of tournaments with a given score sequence
- Probability Inequalities for Sums of Bounded Random Variables
- Random dense bipartite graphs and directed graphs with specified degrees
- The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs
- The number of matchings in random regular graphs and bipartite graphs
Cited in
(31)- The spectral gap of random regular graphs
- Subgraph counts for dense random graphs with specified degrees
- The densest subgraph problem in sparse random graphs
- On the maximum number of common neighbours in dense random regular graphs
- Dense subgraphs in the H-free process
- Random graphs with a given degree sequence
- Sprinkling with random regular graphs
- Uniform generation of spanning regular subgraphs of a dense graph
- Random dense bipartite graphs and directed graphs with specified degrees
- Induced subgraphs in sparse random graphs with given degree sequences
- Subgraph distributions in dense random regular graphs
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- The degree sequence of random graphs from subcritical classes
- Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
- Asymptotic enumeration of sparse uniform hypergraphs with given degrees
- The number of graphs and a random graph with a given degree sequence
- Subgraphs of random graphs with specified degrees
- On subgraphs with degrees of prescribed residues in the random graph
- scientific article; zbMATH DE number 4164910 (Why is no real title available?)
- Counting loopy graphs with given degrees
- Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
- Threshold functions for small subgraphs: an analytic approach
- Factorisation of the complete graph into spanning regular factors
- ASYMPTOTIC ENUMERATION OF SYMMETRIC INTEGER MATRICES WITH UNIFORM ROW SUMS
- Threshold functions for small subgraphs in simple graphs and multigraphs
- The switch Markov chain for sampling irregular graphs and digraphs
- Sandwiching dense random regular graphs between binomial random graphs
- Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
- First order distinguishability of sparse random graphs
- Extreme degrees in random subgraphs of regular graphs
- The minimum number of spanning trees in regular multigraphs
This page was built for publication: Subgraphs of dense random graphs with specified degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2998852)
