Using the incompressibility method to obtain local Lemma results for Ramsey-type problems

DOI10.1016/j.ipl.2008.09.030zbMath1191.68296arXiv0804.0724OpenAlexW1995117763WikidataQ124815607 ScholiaQ124815607MaRDI QIDQ976081

Pascal Schweitzer

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.0724

zbMATH Keywords

algorithmsdata compressionRamsey theoryincompressibilityLovász local Lemma

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (1)

On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma

Cites Work

• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using the incompressibility method to obtain local Lemma results for Ramsey-type problems