Kolmogorov complexity arguments in combinatorics
type: Item
instance of: scholarly article
title: Kolmogorov complexity arguments in combinatorics
zbMATH Open document ID: 0804.68068
DOI: 10.1016/0097-3165(94)90064-7
author: Ming Li
author: Paul M. B. Vitányi
published in: Journal of Combinatorial Theory. Series A
publication date: 1995-01-12T00:00:00Z
review text: This is a self-contained paper on applications of Kolmogorov complexity in combinatorics. Methods from algorithmic information theory are used to give new proofs for several well-known but highly non-trivial results in combinatorics (existence of transitive tournaments, coin weighing problem, minimal covering families of bipartite complete graphs). The proofs convince by simplicity and elegance and show the basic concepts of this beautiful theory. An outlook is given to other applications in combinatorics.
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 599874
zbMATH Keywords: applications of Kolmogorov complexity
zbMATH Keywords: combinatorics
reviewed by: Carsten Damm
MaRDI profile type: Publication
full work available at URL: 0097-3165(94)90064-7
OpenAlex ID: W2142703137
cites work: Determination of a Subset from Certain Combinatorial Properties
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: On a Problem in Graph Theory
cites work: A Problem on Tournaments
cites work: Q4065548
cites work: Q4074808
cites work: Q5547602
cites work: Kolmogorov complexity and random graphs
cites work: Q3214803
cites work: Combinatorial foundations of information theory and the calculus of probabilities
cites work: Q4023358
cites work: On a Combinatorial Problem in Number Theory
cites work: The definition of random sequences
cites work: Q4081256
cites work: An information-theoretic method in combinatorial theory
cites work: Q5573961
cites work: A Mathematical Theory of Communication
Recommended article: Combinatorial interpretation of Kolmogorov complexity
Recommended article: Q5465360
Recommended article: Q4023359
Recommended article: Q3076855
Recommended article: Q3508020
Recommended article: Kolmogorov complexity and the Recursion Theorem
Recommended article: Kolmogorov complexity and degrees of tally sets
Recommended article: Erratum to: Kolmogorov complexity arguments in combinatorics
description: scientific article; zbMATH DE number 599874