Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909226723442688 |
|---|---|
| author | Mourad, Daniel |
| author_facet | Mourad, Daniel |
| contents | The lefthanded Lovász local lemma (LLLL) is a generalization of the Lovász 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10564 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma Mourad, Daniel Logic Combinatorics 05C15, 05D40, 03D99, 68Q87 F.2.2; F.4.1; G.2.1 The lefthanded Lovász local lemma (LLLL) is a generalization of the Lovász 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. |
| title | Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma |
| topic | Logic Combinatorics 05C15, 05D40, 03D99, 68Q87 F.2.2; F.4.1; G.2.1 |
| url | https://arxiv.org/abs/2406.10564 |