|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
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 message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER