Kolmogorov complexity arguments in combinatorics

DOI10.1016/0097-3165(94)90064-7zbMath0804.68068OpenAlexW2142703137MaRDI QIDQ1328399

Paul M. B. Vitányi, Ming Li

Publication date: 12 January 1995

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(94)90064-7

zbMATH Keywords

combinatoricsapplications of Kolmogorov complexity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Information storage and retrieval of data (68P20) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

New applications of the incompressibility method. II ⋮ Compressibility, laws of nature, initial conditions and complexity ⋮ Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Kolmogorov complexity and random graphs
• An information-theoretic method in combinatorial theory
• Combinatorial foundations of information theory and the calculus of probabilities
• A Theory of Program Size Formally Identical to Information Theory
• A Problem on Tournaments
• On a Combinatorial Problem in Number Theory
• Determination of a Subset from Certain Combinatorial Properties
• The definition of random sequences
• On a Problem in Graph Theory

This page was built for publication: Kolmogorov complexity arguments in combinatorics