Kolmogorov Random Graphs and the Incompressibility Method

DOI10.1137/S0097539797327805zbMath0939.68054arXivmath/0110203MaRDI QIDQ4943756

Paul M. B. Vitányi, John Tromp, Harry Buhrman, Ming Li

Publication date: 19 March 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0110203

zbMATH Keywords

algorithmic information theoryrandom graphsKolmogorov complexityenumeration of graphsincompressibility method

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (4)

On some putative graph-theoretic counterexamples to the principle of the identity of indiscernibles ⋮ Describing finite groups by short first-order sentences ⋮ Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks ⋮ Kolmogorov random graphs only have trivial stable colorings.

This page was built for publication: Kolmogorov Random Graphs and the Incompressibility Method