Computational Complexity

Friday, July 11, 2003

 
A Combinatorial Theorem Proven by Kolmogorov Complexity

Posted by Lance

During the rump session of complexity, Nikolai Vereshchagin presented a combinatorial theorem that he proved using Kolmogorov complexity. Let A be a finite subset of N×N where N is the set of natural numbers. Let m be the size of A, r be the number of nonempty rows of A and c the number of nonempty columns.

We say A is good is every nonempty row has m/r elements and every nomempty column has m/c elements of A. A rectangle has this property, as does a diagonal. We say A is k-good if every nonempty row has at most km/r elements and every nonempty column has at most km/c elements. A is good if it is 1-good.

Vereshchagin's Theorem: There is a constant c such that for all finite subsets B of N×N with n = log |B| there is a partition of B into at most n^c sets each of which is n^c-good.

Vereshchagin asks whether there is a purely combinatorial proof of this theorem. If you know of one let me know.

For those who know some Kolmogorov complexity, let me sketch the proof: We label each point (x,y) of B with the following five values: K^B(x,y), K^B(x), K^B(y), K^B(x|y) and K^B(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is n^c-good for some c.

Update

5:22 AM #

Links to this post:

  <$BlogBacklinkTitle$>  

<$BlogBacklinkSnippet$>
posted by <$BlogBacklinkAuthor$> @ <$BlogBacklinkDateTime$>

Create a Link

Weblog Home

Archives