A classical result of Kleitman determines the maximum number f(n, s) of subsets in a family <InlineEquation ID="IEq1"> <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 sets that do not contain distinct sets <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$F_1,F_2,\dots ,F_s$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>F</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>F</mi> <mi>s</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> that are pairwise disjoint in the case <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n\equiv 0,-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≡</mo> <mn>0</mn> <mo>,</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> (mod s). Katona and Nagy determined the maximum size of a family of subsets of an n-element set that does not contain <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$A_1,A_2,\dots ,A_t,B_1,B_2,\dots ,B_t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>A</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>A</mi> <mi>t</mi> </msub> <mo>,</mo> <msub> <mi>B</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>B</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>B</mi> <mi>t</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\bigcup _{i=1}^t A_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mo>⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>t</mi> </msubsup> <msub> <mi>A</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\bigcup _{i=1}^t B_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mo>⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>t</mi> </msubsup> <msub> <mi>B</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> being disjoint. In this paper, we consider the problem of finding the maximum number <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\textrm{vex}(n,K_{s\times t})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>vex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mi>s</mi> <mo>×</mo> <mi>t</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in a family <InlineEquation ID="IEq8"> <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> without sets <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$F^1_1,\dots ,F^1_t,\dots ,F^s_1,\dots ,F^s_t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>F</mi> <mn>1</mn> <mn>1</mn> </msubsup> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msubsup> <mi>F</mi> <mi>t</mi> <mn>1</mn> </msubsup> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msubsup> <mi>F</mi> <mn>1</mn> <mi>s</mi> </msubsup> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msubsup> <mi>F</mi> <mi>t</mi> <mi>s</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$G_j=\bigcup _{i=1}^tF^j_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>G</mi> <mi>j</mi> </msub> <mo>=</mo> <msubsup> <mo>⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>t</mi> </msubsup> <msubsup> <mi>F</mi> <mi>i</mi> <mi>j</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation> <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$j=1,2,\dots ,s$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> are pairwise disjoint. We determine the asymptotics of <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$2^n-\textrm{vex}(n,K_{s\times t})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>-</mo> <mtext>vex</mtext> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mi>s</mi> <mo>×</mo> <mi>t</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$n\equiv -1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≡</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> (mod s) for all t, and if <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$n\equiv 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≡</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> (mod s), <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$t\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and show that in this latter case the asymptotics of the <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$t=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> subcase is different from both the <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$t=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$t\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> subcases.

On a Generalization of a Result of Kleitman

期刊论文
出版模式：

开放获取
发表日期：

2025年8月2日

查看全文

Ryan R. Martin,
Balázs Patkós

摘要

A classical result of Kleitman determines the maximum number f(n, s) of subsets in a family ${{\mathcal {F}}}\subseteq 2^{[n]}$ $F \subseteq 2^{[n]}$ of sets that do not contain distinct sets $F_1,F_2,\dots ,F_s$ $F_{1}, F_{2}, \dots, F_{s}$ that are pairwise disjoint in the case $n\equiv 0,-1$ $n \equiv 0, - 1$ (mod s). Katona and Nagy determined the maximum size of a family of subsets of an n-element set that does not contain $A_1,A_2,\dots ,A_t,B_1,B_2,\dots ,B_t$ $A_{1}, A_{2}, \dots, A_{t}, B_{1}, B_{2}, \dots, B_{t}$ with $\bigcup _{i=1}^t A_i$ $⋃_{i = 1}^{t} A_{i}$ and $\bigcup _{i=1}^t B_i$ $⋃_{i = 1}^{t} B_{i}$ being disjoint. In this paper, we consider the problem of finding the maximum number $\textrm{vex}(n,K_{s\times t})$ $vex (n, K_{s \times t})$ in a family ${{\mathcal {F}}}\subseteq 2^{[n]}$ $F \subseteq 2^{[n]}$ without sets $F^1_1,\dots ,F^1_t,\dots ,F^s_1,\dots ,F^s_t$ $F_{1}^{1}, \dots, F_{t}^{1}, \dots, F_{1}^{s}, \dots, F_{t}^{s}$ such that $G_j=\bigcup _{i=1}^tF^j_i$ $G_{j} = ⋃_{i = 1}^{t} F_{i}^{j}$ $j=1,2,\dots ,s$ $j = 1, 2, \dots, s$ are pairwise disjoint. We determine the asymptotics of $2^n-\textrm{vex}(n,K_{s\times t})$ $2^{n} - vex (n, K_{s \times t})$ if $n\equiv -1$ $n \equiv - 1$ (mod s) for all t, and if $n\equiv 0$ $n \equiv 0$ (mod s), $t\ge 3$ $t \geq 3$ and show that in this latter case the asymptotics of the $t=2$ $t = 2$ subcase is different from both the $t=1$ $t = 1$ and $t\ge 3$ $t \geq 3$ subcases.