Using the Incompressibility Method to obtain Local Lemma results for 
Ramsey-type Problems

Schweitzer, Pascal

doi:10.1016/j.ipl.2008.09.030

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Using the Incompressibility Method to obtain Local Lemma results for Ramsey-type Problems

MPS-Authors

/persons/resource/persons45438

Schweitzer, Pascal
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Schweitzer, P. (2009). Using the Incompressibility Method to obtain Local Lemma results for Ramsey-type Problems. Information Processing Letters, 109(4), 229-232. doi:10.1016/j.ipl.2008.09.030.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-18E7-3

Abstract

We reveal a connection between the incompressibility method and the Lov\'{a}sz 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. In particular we reprove that $w(k;c) \geq \frac{c^{k-3}}{k} \cdot \frac{k-1}{k}$. The method is applicable to obtain lower bounds of Ramsey numbers, large transitive subtournaments and other Ramsey phenomena as well.