Kolmogorov Random Graphs and the Incompressibility Method

Details Kolmogorov Random Graphs and the Incompressibility Method Kolmogorov Random Graphs and the Incompressibility Method

2001-10-18

arxiv.org/abs/math/0110203v1

H. Buhrman, M. Li, J. Tromp and P.M.B. Vitanyi, Kolmogorov random graphs and the incompressibility method, SIAM J. Comput., 29

Mathematics

Combinatorics

LaTeX 9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov Random Graphs and the Incompressibility Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kolmogorov Random Graphs and the Incompressibility Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov Random Graphs and the Incompressibility Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-283930