Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] A Combinatorial Theorem Proven by Kolmogorov Complexity

Expand Messages
  • Lance Fortnow
    During the rump session of complexity , Nikolai Vereshchagin presented a combinatorial theorem that he proved using Kolmogorov complexity. Let A be a finite
    Message 1 of 1 , Jul 11, 2003
    • 0 Attachment
      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 nc sets each of which is nc-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: KB(x,y), KB(x), KB(y), KB(x|y) and KB(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is nc-good for some c.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 7/11/2003 03:22:56 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.