The number of graphs and a random graph with a given degree sequence
From MaRDI portal
Abstract: We consider the set of all graphs on n labeled vertices with prescribed degrees D=(d_1, ..., d_n). For a wide class of tame degree sequences D we prove a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0-1 matrices with prescribed row and column sums.
Recommendations
Cites work
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
- Limits of dense graph sequences
- Matrix integrals and map enumeration: an accessible introduction
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
- Random dense bipartite graphs and directed graphs with specified degrees
- Random graphs with a given degree sequence
- Reverse Holder Inequalities for Spherical Harmonics
- Subgraphs of dense random graphs with specified degrees
Cited in
(42)- Is breaking of ensemble equivalence monotone in the number of constraints?
- Covariance structure behind breaking of ensemble equivalence in random graphs
- Detection thresholds for the \(\beta\)-model on sparse graphs
- The switch Markov chain for sampling irregular graphs and digraphs
- Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
- Testing goodness of fit of random graph models
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Asymptotic enumeration by degree sequence of graphs of high degree
- Sandwiching dense random regular graphs between binomial random graphs
- Large deviation for uniform graphs with given degrees
- On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
- Threshold functions for small subgraphs in simple graphs and multigraphs
- Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs
- Probabilistic existence of regular combinatorial structures
- Random doubly stochastic matrices: the circular law
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
- Lower bounds for contingency tables via Lorentzian polynomials
- An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
- The degree sequence of a random graph. I. The models
- MAX-plus objects to study the complexity of graphs
- Moments of uniform random multigraphs with fixed degree sequences
- Phase transition in random contingency tables with non-uniform margins
- Degree sequence of random permutation graphs
- scientific article; zbMATH DE number 5239164 (Why is no real title available?)
- Maximum entropy and integer partitions
- Independent sets of a given size and structure in the hypercube
- Friendly bisections of random graphs
- Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
- Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
- Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
- Asymptotic theory in bipartite graph models with a growing number of parameters
- Random graphs with a given degree sequence
- The guessing number of undirected graphs
- Existence and applications of finite-population samples that are exactly balanced
- External columns and chambers of vector partition functions
- Embedding theorems for random graphs with specified degrees
- Counting graphic sequences via integrated random walks
- Improved estimates for the number of non-negative integer matrices with given row and column sums
- On the maximum number of common neighbours in dense random regular graphs
- Matrices with prescribed row and column sums
- Counting loopy graphs with given degrees
This page was built for publication: The number of graphs and a random graph with a given degree sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4921886)
