| | |
| | |
Stat |
Members: 3645 Articles: 2'501'711 Articles rated: 2609
20 April 2024 |
|
| | | |
|
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 | Affiliation: | CWI), Ming Li (University of Waterloo), John Tromp (CWI), and Paul Vitanyi (CWI and University of Amsterdam | Abstract: | 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. | Source: | arXiv, math.CO/0110203 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
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 Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |