Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma

Autor:	Mourad, Daniel
Rok vydání:	2024
Předmět:	Mathematics - Logic Mathematics - Combinatorics 05C15 05D40 03D99 68Q87 F.2.2 F.4.1 G.2.1
Druh dokumentu:	Working Paper
Popis:	The lefthanded Lov\'asz local lemma (LLLL) is a generalization of the Lov\'asz local lemma (LLL), a powerful technique from the probabilistic method. We prove a computable version of the LLLL and use it to effectivize a collection of results on the existence of certain types of non-repetitive sequences via the LLL and LLLL. This represents the first constructive proof of these results. Comment: 36 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2406.10564 Zobrazit plný text záznamu View this record from Arxiv