<p>The Park-Pham theorem (previously known as the Kahn-Kalai conjecture) bounds the critical probability, <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi>p</mi> <mi>c</mi> </msub> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$p_{c}(\mathcal{F})$</EquationSource> </InlineEquation>, of the a nontrivial property <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> <mo>⊆</mo> <msup> <mn>2</mn> <mi>X</mi> </msup> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}\subseteq 2^{X}$</EquationSource> </InlineEquation> that is closed under supersets by the product of a universal constant <i>K</i>, the expectation threshold of the property, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <mi>q</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$q(\mathcal{F})$</EquationSource> </InlineEquation>, and the logarithm of the size of the property’s largest minimal element, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <mo>log</mo> <mi>ℓ</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\log \ell (\mathcal{F})$</EquationSource> </InlineEquation>. That is, the Park-Pham theorem asserts that <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="175" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi>p</mi> <mi>c</mi> </msub> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>K</mi> <mi>q</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> <mo>log</mo> <mi>ℓ</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$p_{c}(\mathcal{F})\leq Kq(\mathcal{F})\log \ell (\mathcal{F})$</EquationSource> </InlineEquation>. Since the critical probability <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi>p</mi> <mi>c</mi> </msub> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$p_{c}(\mathcal{F})$</EquationSource> </InlineEquation> always satisfies <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi>p</mi> <mi>c</mi> </msub> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$p_{c}(\mathcal{F})&lt;1$</EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="142" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <mi>K</mi> <mi>q</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> <mo>log</mo> <mi>ℓ</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$Kq(\mathcal{F})\log \ell (\mathcal{F}) &lt; 1$</EquationSource> </InlineEquation>? 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 <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="87" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> <mo stretchy="false">(</mo> <msub> <mi mathvariant="script">F</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mi mathvariant="normal">∞</mi> </math></EquationSource> <EquationSource Format="TEX">$\ell (\mathcal{F}_{n})\rightarrow \infty $</EquationSource> </InlineEquation>, we prove the following relatively strong necessary condition for the Kahn-Kalai bounds to provide nontrivial information: For every positive integer <i>t</i>, every collection of all-but-<i>t</i> of the minimal elements of <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">F</mi> <mi>n</mi> </msub> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}_{n}$</EquationSource> </InlineEquation> may have nonempty intersection for only finitely many <i>n</i>. 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 <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">F</mi> <mi>n</mi> </msub> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}_{n}$</EquationSource> </InlineEquation> must occupy an ever-widening ‘wedge’ in <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq12.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <msub> <mi>X</mi> <mi>n</mi> </msub> </msup> </math></EquationSource> <EquationSource Format="TEX">$2^{X_{n}}$</EquationSource> </InlineEquation>: the further <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq13.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">F</mi> <mi>n</mi> </msub> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}_{n}$</EquationSource> </InlineEquation> climbs up <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq14.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <msub> <mi>X</mi> <mi>n</mi> </msub> </msup> </math></EquationSource> <EquationSource Format="TEX">$2^{X_{n}}$</EquationSource> </InlineEquation> in one area, the further it must spread down and across <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13660_2025_3272_Article_IEq15.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <msub> <mi>X</mi> <mi>n</mi> </msub> </msup> </math></EquationSource> <EquationSource Format="TEX">$2^{X_{n}}$</EquationSource> </InlineEquation> in another.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

When do the Kahn-Kalai bounds provide nontrivial information?

  • Bryce Alan Christopherson,
  • Jack Baretz

摘要

The Park-Pham theorem (previously known as the Kahn-Kalai conjecture) bounds the critical probability, p c ( F ) $p_{c}(\mathcal{F})$ , of the a nontrivial property F 2 X $\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 ( F ) $q(\mathcal{F})$ , and the logarithm of the size of the property’s largest minimal element, log ( F ) $\log \ell (\mathcal{F})$ . That is, the Park-Pham theorem asserts that p c ( F ) K q ( F ) log ( F ) $p_{c}(\mathcal{F})\leq Kq(\mathcal{F})\log \ell (\mathcal{F})$ . Since the critical probability p c ( F ) $p_{c}(\mathcal{F})$ always satisfies p c ( F ) < 1 $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 K q ( F ) log ( F ) < 1 $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 ( F n ) $\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 F n $\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 F n $\mathcal{F}_{n}$ must occupy an ever-widening ‘wedge’ in 2 X n $2^{X_{n}}$ : the further F n $\mathcal{F}_{n}$ climbs up 2 X n $2^{X_{n}}$ in one area, the further it must spread down and across 2 X n $2^{X_{n}}$ in another.