Kolmogorov Random Graphs and the Incompressibility Method

Harry Buhrman, Ming Li, John Tromp +1

We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressib…