When do the Kahn-Kalai Bounds Provide Nontrivial Information?
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909526192553984 |
|---|---|
| author | Christopherson, Bryce Alan Baretz, Jack |
| author_facet | Christopherson, Bryce Alan Baretz, Jack |
| contents | The Park-Pham theorem (previously known as the Kahn-Kalai conjecture), bounds the critical probability, $p_c(\mathcal{F})$, of the a non-trivial property $\mathcal{F}\subseteq 2^X$ that is closed under supersets by the product of a universal constant $K$, the expectation threshold of the property, $q(\mathcal{F})$, and the logarithm of the size of the property's largest minimal element, $\log\ell(\mathcal{F})$. That is, the Park-Pham theorem asserts that $p_c(\mathcal{F})\leq Kq(\mathcal{F})\log\ell(\mathcal{F})$. Since the critical probability $p_c(\mathcal{F})$ always satisfies $p_c(\mathcal{F})<1$, one may ask when the upper bound posed by Kahn and Kalai gives us more information than this--that is, when is it true that $Kq(\mathcal{F})\log\ell(\mathcal{F}) < 1$? In this short note, we provide a number of necessary conditions for this to happen and give a few sufficient conditions for the bounds to provide new (and, in fact, asymptotically perfect) information along the way. In the most interesting case where $\ell(\mathcal{F}_n)\rightarrow \infty$, we prove the following relatively strong necessary condition for the Kahn-Kalai bounds to provide nontrivial information: For every positive integer $t$, every collection of all-but-$t$ of the minimal elements of $\mathcal{F}_n$ may have nonempty intersection for only finitely many $n$. Consequently, not only must the number of minimal elements become arbitrarily large, but so too must the size of any cover. Intuitively, this means that such sequences $\mathcal{F}_n$ must occupy an ever-widening `wedge' in $2^{X_n}$: the further $\mathcal{F}_n$ climbs up $2^{X_n}$ in one area, the further it must spread down and across $2^{X_n}$ in another. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02822 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | When do the Kahn-Kalai Bounds Provide Nontrivial Information? Christopherson, Bryce Alan Baretz, Jack Combinatorics 06A07, 05C80, 60C05, 68R01 The Park-Pham theorem (previously known as the Kahn-Kalai conjecture), bounds the critical probability, $p_c(\mathcal{F})$, of the a non-trivial property $\mathcal{F}\subseteq 2^X$ that is closed under supersets by the product of a universal constant $K$, the expectation threshold of the property, $q(\mathcal{F})$, and the logarithm of the size of the property's largest minimal element, $\log\ell(\mathcal{F})$. That is, the Park-Pham theorem asserts that $p_c(\mathcal{F})\leq Kq(\mathcal{F})\log\ell(\mathcal{F})$. Since the critical probability $p_c(\mathcal{F})$ always satisfies $p_c(\mathcal{F})<1$, one may ask when the upper bound posed by Kahn and Kalai gives us more information than this--that is, when is it true that $Kq(\mathcal{F})\log\ell(\mathcal{F}) < 1$? In this short note, we provide a number of necessary conditions for this to happen and give a few sufficient conditions for the bounds to provide new (and, in fact, asymptotically perfect) information along the way. In the most interesting case where $\ell(\mathcal{F}_n)\rightarrow \infty$, we prove the following relatively strong necessary condition for the Kahn-Kalai bounds to provide nontrivial information: For every positive integer $t$, every collection of all-but-$t$ of the minimal elements of $\mathcal{F}_n$ may have nonempty intersection for only finitely many $n$. Consequently, not only must the number of minimal elements become arbitrarily large, but so too must the size of any cover. Intuitively, this means that such sequences $\mathcal{F}_n$ must occupy an ever-widening `wedge' in $2^{X_n}$: the further $\mathcal{F}_n$ climbs up $2^{X_n}$ in one area, the further it must spread down and across $2^{X_n}$ in another. |
| title | When do the Kahn-Kalai Bounds Provide Nontrivial Information? |
| topic | Combinatorics 06A07, 05C80, 60C05, 68R01 |
| url | https://arxiv.org/abs/2408.02822 |