Kolmogorov random graphs
Harry Buhrman, Ming Li, Paul M. B. Vitanyi · 2002
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 and (ii) a new elementary proof for the number of unlabeled graphs.