Kolmogorov random graphs and the incompressibility method

Authors
Buhrman, H Li, M Tromp, J Vitanyi, P
Citation
H. Buhrman et al., Kolmogorov random graphs and the incompressibility method, SIAM J COMP, 29(2), 1999, pp. 590-599
Citations number
16
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
2
Year of publication
1999
Pages
590 - 599
Database
ISI
SICI code
0097-5397(199912)29:2<590:KRGATI>2.0.ZU;2-3
Abstract
We investigate topological, combinatorial, statistical, and enumeration pro perties of finite graphs with high Kolmogorov complexity (almost all graphs ) using the novel incompressibility method. Example results are (i) the mea n and variance of the number of (possibly overlapping) ordered labeled subg raphs of a labeled graph as a function of its randomness deficiency (how fa r it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.