Kolmogorov Random Graphs and the Incompressibility Method

Simple item page
dc.creatorBuhrman, Harry
dc.creatorLi, Ming
dc.creatorTromp, John
dc.creatorVitanyi, Paul
dc.date2001-10-18
dc.date.accessioned2026-07-07T04:43:56Z
dc.date.available2026-07-07T04:43:56Z
dc.descriptionWe 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.
dc.descriptionLaTeX 9 pages
dc.identifierhttps://arxiv.org/abs/math/0110203
dc.identifierhttp://arxiv.org/abs/math/0110203
dc.identifierH. 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
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/62437
dc.subjectCombinatorics
dc.subject05C78, 94A17, 05C80, 05C70, 05C30, 05C35, 68R99
dc.titleKolmogorov Random Graphs and the Incompressibility Method
dc.typetext

Files

Collections

arXiv