Counting connected graphs and hypergraphs via the probabilistic method
Counting connected graphs and hypergraphs via the probabilistic method
复制标题
通过概率方法计算连通图和超图
DOI：
10.1002/rsa.20160
复制
发表时间：
2007
影响因子：
1
通讯作者：
Vishal Sanwalani
中科院分区：
文献类型：
--
作者：
A. Coja;Cristopher Moore;Vishal Sanwalani
虽然稀疏随机图或超图连通的可能性呈指数级下降，但概率为 1 − o(1) 的图具有“巨型组件”，在给定其边和顶点的数量的情况下，该图是均匀分布的连通图。这个简单的观察使我们能够估计具有 ((d − 1)−1 + ε)n ≤ m = o(nlnn) 条边的 n 个顶点上的连通图的数量，更一般地说是连通的 d-均匀超图的数量，其中 ε > 0 任意小但与 n 无关。我们还估计二项式随机超图 Hd(n,p) 相连的概率，并确定 Hd(n,p) 相连的预期边数。这扩展了 Bender 等人之前的工作。 （随机结构算法 1 (1990), 127–169）关于连通图的数量。而本德等人。 （1990）基于连通图数量满足的递归关系，因此该论证在某种程度上是枚举性的，我们提出了一种纯粹的概率方法。 © 2007 Wiley periodicals, Inc. 随机结构，2007 年
While it is exponentially unlikely that a sparse random graph or hypergraph is connected, with probability 1 − o(1) such a graph has a “giant component” that, given its numbers of edges and vertices, is a uniformly distributed connected graph. This simple observation allows us to estimate the number of connected graphs, and more generally the number of connected d‐uniform hypergraphs, on n vertices with ((d − 1)−1 + ε)n ≤ m = o(nlnn) edges, where ε > 0 is arbitrarily small but independent of n. We also estimate the probability that a binomial random hypergraph Hd(n,p) is connected, and determine the expected number of edges of Hd(n,p) given that it is connected. This extends prior work of Bender et al. (Random Struct Algorithm 1 (1990), 127–169) on the number of connected graphs. While Bender et al. (1990) is based on a recursion relation satisfied by the number of connected graphs, so that the argument is to some extent enumerative, we present a purely probabilistic approach. © 2007 Wiley Periodicals, Inc. Random Struct., 2007