Kolmogorov complexity arguments in combinatorics (Q1328399)

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.