<p>For a subfamily <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{F}\subseteq 2^{[n]}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo>⊆</mo> <msup> <mn>2</mn> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> of the Boolean lattice, consider the graph <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi mathvariant="script">F</mi> </msub> </math></EquationSource> </InlineEquation> on <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> based on the pairwise inclusion relations among its members. Given a positive integer <i>t</i>, how large can <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> be before <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi mathvariant="script">F</mi> </msub> </math></EquationSource> </InlineEquation> must contain some component of order greater than <i>t</i>?For <i>t</i> = 1, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For <i>t</i> = 2<sup><i>n</i></sup>, this question is trivial. We are interested in what happens between these two extremes.For <i>t</i> = 2<sup><i>g</i></sup> with <i>g</i> = <i>g</i>(<i>n</i>) being any integer function that satisfies <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="131" /> </InlineMediaObject> <EquationSource Format="TEX">\(g(n)=o(n/\log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> as <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq7.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\to\infty\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer.This constitutes a nontrivial generalisation of Sperner's theorem.We do so by a reduction to a Turán-type problem for rainbow cycles in properly edge-coloured graphs.Among other results, we also give a sharp answer to the question, how large can <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> be before <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1536_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_\mathcal{F}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi mathvariant="script">F</mi> </msub> </math></EquationSource> </InlineEquation>must be connected?</p>

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

Largest component in Boolean sublattices

  • J. Galliano,
  • R. J. Kang

摘要

For a subfamily \(\mathcal{F}\subseteq 2^{[n]}\) F 2 [ n ] of the Boolean lattice, consider the graph \(G_\mathcal{F}\) G F on \(\mathcal{F}\) F based on the pairwise inclusion relations among its members. Given a positive integer t, how large can \(\mathcal{F}\) F be before \(G_\mathcal{F}\) G F must contain some component of order greater than t?For t = 1, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For t = 2n, this question is trivial. We are interested in what happens between these two extremes.For t = 2g with g = g(n) being any integer function that satisfies \(g(n)=o(n/\log n)\) g ( n ) = o ( n / log n ) as \(n\to\infty\) n , we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer.This constitutes a nontrivial generalisation of Sperner's theorem.We do so by a reduction to a Turán-type problem for rainbow cycles in properly edge-coloured graphs.Among other results, we also give a sharp answer to the question, how large can \(\mathcal{F}\) F be before \(G_\mathcal{F}\) G F must be connected?