forgot password?
register here
Research articles
  search articles
  reviews guidelines
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
Members: 2981
Articles: 2'033'011
Articles rated: 2577

25 January 2021
  » arxiv » math.CO/0110203

 Article overview

Kolmogorov Random Graphs and the Incompressibility Method
Harry Buhrman ; Ming Li ; John Tromp ; Paul Vitanyi ;
Date 18 Oct 2001
Journal 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
Subject Combinatorics MSC-class: 05C78, 94A17, 05C80, 05C70, 05C30, 05C35, 68R99 | math.CO
AffiliationCWI), Ming Li (University of Waterloo), John Tromp (CWI), and Paul Vitanyi (CWI and University of Amsterdam
AbstractWe 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.
Source arXiv, math.CO/0110203
Services Forum | Review | PDF | Favorites   
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
of broad interest:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser CCBot/2.0 (
» my Online CV
» Free

News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2021 - Scimetrica