Kolmogorov Random Graphs and the Incompressibility Method

DOI10.1137/S0097539797327805MaRDI QIDQ4943756zbMATH OpenFDO

Authors Harry Buhrman, John Tromp, Paul M. B. Vitányi, 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 theoryenumeration of graphsincompressibility methodKolmogorov complexityrandom graphs

Mathematics Subject Classification ID

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

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.

Recommendations

• Kolmogorov complexity and random graphs
• Kolmogorov complexity arguments in combinatorics
• Kolmogorov complexity and symmetric relational structures
• scientific article; zbMATH DE number 2079851
• scientific article; zbMATH DE number 1405647

Cited in

(12)

• Kolmogorov complexity and random graphs
• Kolmogorov random graphs only have trivial stable colorings.
• 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
• Sieve methods in random graph theory
• On some putative graph-theoretic counterexamples to the principle of the identity of indiscernibles
• Kolmogorov complexity and symmetric relational structures
• scientific article; zbMATH DE number 1071771 (Why is no real title available?)
• scientific article; zbMATH DE number 1506506 (Why is no real title available?)
• scientific article; zbMATH DE number 1405647 (Why is no real title available?)
• On isomorphism-invariant antistochastic properties of random graphs
• On sequential structures in incompressible multidimensional networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943756)