When do the Kahn-Kalai bounds provide nontrivial information?

Abstract The Park-Pham theorem (previously known as the Kahn-Kalai conjecture) bounds the critical probability, $p_{c}(\mathcal{F})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> </mml:math> , of the a nontrivial property $\mathcal{F}\subseteq 2^{X}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>X</mml:mi> </mml:msup> </mml:math> that is closed under supersets by the product of a universal constant K , the expectation threshold of the property, $q(\mathcal{F})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>q</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> </mml:math> , and the logarithm of the size of the property’s largest minimal element, $\log \ell (\mathcal{F})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>log</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> </mml:math> . That is, the Park-Pham theorem asserts that $p_{c}(\mathcal{F})\leq Kq(\mathcal{F})\log \ell (\mathcal{F})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>K</mml:mi> <mml:mi>q</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> </mml:math> . Since the critical probability $p_{c}(\mathcal{F})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> </mml:math> always satisfies $p_{c}(\mathcal{F})&lt;1$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:math> , 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}) &lt; 1$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> <mml:mi>q</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>)</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:math> ? 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 $ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:math> , 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}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> 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}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> must occupy an ever-widening ‘wedge’ in $2^{X_{n}}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msup> </mml:math> : the further $\mathcal{F}_{n}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> climbs up $2^{X_{n}}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msup> </mml:math> in one area, the further it must spread down and across $2^{X_{n}}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msup> </mml:math> in another.