We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9697_Article_IEq1.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{[n]}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </msup> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9697_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="122" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{(1+o(1))(k-1){n \atopwithdelims ()\lfloor n/2\rfloor }}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mi>n</mi> <mrow> <mo>⌊</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>⌋</mo> </mrow> </mfrac> </mfenced> </mrow> </msup> </math></EquationSource> </InlineEquation>. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.

On the Number of P-free Set Systems for Tree Posets P

期刊论文
发表日期：

2025年1月30日

查看全文

József Balogh,
Ramon I. Garcia,
Michael C. Wigal

摘要

We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in $2^{[n]}$ $2^{[n]}$ is $2^{(1+o(1))(k-1){n \atopwithdelims ()\lfloor n/2\rfloor }}$ $2^{(1 + o (1)) (k - 1) (\binom{n}{⌊ n / 2 ⌋})}$ . The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.