solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看135次
Threshold functions for small subgraphs in simple graphs and multigraphs. (arXiv:1807.05772v1 [math.CO])
来源于:arXiv
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. 查看全文>>