2008/04/04 by Pascal Schweitzer, Schweitzer, Pascal
Computer Science · Mathematics · #05D10 #05D40 #68Q30 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05D10 #msc:05D40 #msc:68Q30
paper · pdf · doi:10.48550/arxiv.0804.0724
8 pages, 1 figure
arxiv created 2008/04/04 · openalex publication_date 2008/04/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We reveal a connection between the incompressibility method and the Lovasz local lemma in the context of Ramsey theory. We obtain bounds by repeatedly encoding objects of interest and thereby compressing strings. The method is demonstrated on the example of van der Waerden numbers. It applies to lower bounds of Ramsey numbers, large transitive subtournaments and other Ramsey phenomena as well.