|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 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.
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER