Borel Local Lemma: arbitrary random variables and limited exponential growth
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914610072780800 |
|---|---|
| author | Bernshteyn, Anton Yu, Jing |
| author_facet | Bernshteyn, Anton Yu, Jing |
| contents | The Lovász Local Lemma (the LLL for short) is a powerful tool in probabilistic combinatorics that is used to verify the existence of combinatorial objects with desirable properties. Recent years saw the development of various "constructive" versions of the LLL. A major success of this research direction is the Borel version of the LLL due to Csóka, Grabowski, Máthé, Pikhurko, and Tyros, which holds under a subexponential growth assumption. A drawback of their approach is that it only applies when the underlying random variables take values in a finite set. We present an alternative proof of a Borel version of the LLL that holds even if the underlying random variables are continuous and applies to dependency graphs of limited exponential growth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11571 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Borel Local Lemma: arbitrary random variables and limited exponential growth Bernshteyn, Anton Yu, Jing Combinatorics Logic Probability The Lovász Local Lemma (the LLL for short) is a powerful tool in probabilistic combinatorics that is used to verify the existence of combinatorial objects with desirable properties. Recent years saw the development of various "constructive" versions of the LLL. A major success of this research direction is the Borel version of the LLL due to Csóka, Grabowski, Máthé, Pikhurko, and Tyros, which holds under a subexponential growth assumption. A drawback of their approach is that it only applies when the underlying random variables take values in a finite set. We present an alternative proof of a Borel version of the LLL that holds even if the underlying random variables are continuous and applies to dependency graphs of limited exponential growth. |
| title | Borel Local Lemma: arbitrary random variables and limited exponential growth |
| topic | Combinatorics Logic Probability |
| url | https://arxiv.org/abs/2412.11571 |