Kolmogorov random graphs and the incompressibility method
Kolmogorov random graphs and the incompressibility method
复制标题
DOI：
10.1137/s0097539797327805
复制
发表时间：
1999-12-06
影响因子：
1.6
通讯作者：
Vitányi, P
中科院分区：
文献类型：
--
作者：
Buhrman, H;Li, M;Vitányi, P
我们调查的拓扑，组合，统计和枚举性质的有限图高Kolmogorov复杂性（几乎所有的图）使用新的不可压缩性方法。示例结果是（i）标记图的有序标记子图的数量（可能重叠）的均值和方差作为其随机性不足的函数（福尔斯达不到最大可能的Kolmogorov复杂度）和（ii）未标记图的数量的一个新的初等证明。
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.