Threshold functions for small subgraphs in simple graphs and multigraphs
From MaRDI portal
Abstract: We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of emph{patchworks} to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.
Recommendations
Cites work
- (k+1)-Cores Have k-Factors
- \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph
- A Generalisation of Stirling's Formula.
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
- Analytic combinatorics
- Analytic combinatorics in several variables.
- Asymptotic enumeration and limit laws of planar graphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration of sparse multigraphs with given degrees
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Central limit theorems in the configuration model
- Counting graphs and null models of complex networks: configuration model and extensions
- Distribution of subgraphs of random regular graphs
- Enumeration of graphs with a heavy-tailed degree sequence
- Further results on random cubic planar graphs
- Graphs with degree constraints
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- scientific article; zbMATH DE number 1111371 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- Limit laws for self-loops and multiple edges in the configuration model
- On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
- On the threshold for k-regular subgraphs of random graphs
- Quivers and representations.
- Random graphs and complex networks. Volume 1
- Random graphs with a given degree sequence
- Regular subgraphs of random graphs
- Short cycles in random regular graphs
- Small subgraphs of random regular graphs
- Some problems in the enumeration of labelled graphs
- Strongly balanced graphs and random graphs
- Subgraph statistics in subcritical graph classes
- Subgraphs of dense random graphs with specified degrees
- Subgraphs of random graphs with specified degrees
- The birth of the giant component
- The first \(k\)-regular subgraph is large
- The first cycles in an evolving graph
- The number of graphs and a random graph with a given degree sequence
- The property of having a k-regular subgraph has a sharp threshold
- Threshold functions for small subgraphs
- Triadic closure in configuration models with unbounded degree fluctuations
- Upper tails for subgraph counts in random graphs
- When are small subgraphs of a random graph normally distributed?
Cited in
(6)- Threshold functions for small subgraphs: an analytic approach
- Counting directed acyclic and elementary digraphs
- Optimal subgraph structures in scale-free configuration models
- The simple graph threshold number (r,s,a,t) when r 3 is odd and a 2 is even
- Counting connected graphs with large excess
- Exact enumeration of satisfiable 2-SAT formulae
This page was built for publication: Threshold functions for small subgraphs in simple graphs and multigraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189830)
