Threshold functions for small subgraphs in simple graphs and multigraphs
| Autor: | Collet, Gwendal, de Panafieu, Élie, Gardy, Danièle, Gittenberger, Bernhard, Ravelomanana, Vlady |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 42 pages, 5 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|