Kolmogorov Random Graphs and the Incompressibility Method

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
LaTeX 9 pages

Keywords

Combinatorics, 05C78, 94A17, 05C80, 05C70, 05C30, 05C35, 68R99

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/62437

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0110203
 http://arxiv.org/abs/math/0110203
 H. Buhrman, M. Li, J. Tromp and P.M.B. Vitanyi, Kolmogorov random graphs and the incompressibility method, SIAM J. Comput., 29:2(2000), 590--599

Collections

arXiv