<p>&#xa0;&#xa0; In this paper, we obtain the following improved upper bound on the size of <i>k</i>-wise <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\( \mathcal {L} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">L</mi> </math></EquationSource> </InlineEquation>-intersecting families and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\( \mathcal {L} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">L</mi> </math></EquationSource> </InlineEquation>-differencing Sperner families modulo prime powers by employing linear algebra methods: <OrderedList> <ListItem> <ItemNumber>(1)</ItemNumber> <ItemContent> <p>Let <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\( k \ge 2 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> be an integer, <i>p</i> be a prime, <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\( q = p^{ \alpha } \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>=</mo> <msup> <mi>p</mi> <mi>α</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> be a prime power with <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\( \alpha \ge 1 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and let <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\( \mathcal {L} \subseteq \{0, 1, \dots , q-1\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">L</mi> <mo>⊆</mo> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>q</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> be a subset with size <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\( s &gt; 0 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. Suppose that <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\( \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is a family of subsets of [<i>n</i>] such that <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\( \left| F \right| \notin \mathcal {L} \pmod {q} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>F</mi> </mfenced> <mo>∉</mo> <mi mathvariant="script">L</mi> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mi>q</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for each <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\( F \in \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\( \left| F_{i_1} \cap F_{i_2} \cap \cdots \cap F_{i_k} \right| \in \mathcal {L} \pmod {q} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <msub> <mi>F</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mo>∩</mo> <msub> <mi>F</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> </msub> <mo>∩</mo> <mo>⋯</mo> <mo>∩</mo> <msub> <mi>F</mi> <msub> <mi>i</mi> <mi>k</mi> </msub> </msub> </mfenced> <mo>∈</mo> <mi mathvariant="script">L</mi> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mi>q</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for every collection of <i>k</i> distinct subsets in <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\( \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>. Then <Equation ID="Equ18"> <EquationSource Format="TEX">\( \left| \mathcal {F} \right| \le \left( k-1 \right) \left[ {{n-1} \atopwithdelims (){q-1}}+ {{n-1} \atopwithdelims (){q-2}}+ \cdots + {{n-1} \atopwithdelims (){0}} \right] . \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfenced close="|" open="|"> <mi mathvariant="script">F</mi> </mfenced> <mo>≤</mo> <mfenced close=")" open="("> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mfenced> <mfenced close="]" open="["> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> <mo>+</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>q</mi> <mo>-</mo> <mn>2</mn> </mrow> </mfrac> </mfenced> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mn>0</mn> </mfrac> </mfenced> </mfenced> <mo>.</mo> </mrow> </math></EquationSource> </Equation> If in addition there exists an integer <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\( t &lt; p \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>&lt;</mo> <mi>p</mi> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\( \left| F \right| \in \left\{ q-t, q-t+1, \dots q-1 \right\} \pmod {q} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>F</mi> </mfenced> <mo>∈</mo> <mfenced close="}" open="{"> <mi>q</mi> <mo>-</mo> <mi>t</mi> <mo>,</mo> <mi>q</mi> <mo>-</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mfenced> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mi>q</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for each <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\( F \in \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation>, then <Equation ID="Equ19"> <EquationSource Format="TEX">\( \left| \mathcal {F} \right| \le \left( k-1 \right) \left[ {{n-1} \atopwithdelims (){q-1}}+ {{n-1} \atopwithdelims (){q-2}}+ \cdots + {{n-1} \atopwithdelims (){p - t -1}} \right] . \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfenced close="|" open="|"> <mi mathvariant="script">F</mi> </mfenced> <mo>≤</mo> <mfenced close=")" open="("> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mfenced> <mfenced close="]" open="["> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> <mo>+</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>q</mi> <mo>-</mo> <mn>2</mn> </mrow> </mfrac> </mfenced> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>p</mi> <mo>-</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> </mfenced> <mo>.</mo> </mrow> </math></EquationSource> </Equation> This result not only gives an improvement to a theorem by G. Hegedüs and a theorem by Z. Xu and C. H. Yip, but also extends a theorem by L. Babai and P. Frankl.</p> </ItemContent> </ListItem> <ListItem> <ItemNumber>(2)</ItemNumber> <ItemContent> <p>Let <i>p</i> be a prime, <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\( q = p^{ \alpha } \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>=</mo> <msup> <mi>p</mi> <mi>α</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> be a prime power with <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\( \alpha \ge 1 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\( \mathcal {L} = \{l_1, l_2, \dots , l_s\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">L</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>l</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>l</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>l</mi> <mi>s</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> be a subset of <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\( \{1, 2, \dots , q-1\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>q</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Suppose that <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\( \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is a family of subsets of [<i>n</i>] satisfying that <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\( \left| F \setminus F' \right| \in \mathcal {L} \pmod {q} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>F</mi> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> </mfenced> <mo>∈</mo> <mi mathvariant="script">L</mi> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mi>q</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for all distinct pairs <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\( F, F' \in \mathcal {F} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>,</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation>. Then <Equation ID="Equ20"> <EquationSource Format="TEX">\( \left| \mathcal {F} \right| \le \left( {\begin{array}{c}n-1\\ q-1\end{array}}\right) + \left( {\begin{array}{c}n-1\\ q-2\end{array}}\right) +\cdots +\left( {\begin{array}{c}n-1\\ 0\end{array}}\right) . \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfenced close="|" open="|"> <mi mathvariant="script">F</mi> </mfenced> <mo>≤</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>+</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>q</mi> <mo>-</mo> <mn>2</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>0</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>.</mo> </mrow> </math></EquationSource> </Equation> This result extends a theorem by Z. Xu and C. H. Yip to the case of general <InlineEquation ID="IEq29"> <EquationSource Format="TEX">\( \mathcal {L} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">L</mi> </math></EquationSource> </InlineEquation> with size <InlineEquation ID="IEq30"> <EquationSource Format="TEX">\( \left| \mathcal {L} \right| = s \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi mathvariant="script">L</mi> </mfenced> <mo>=</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation>.</p> </ItemContent> </ListItem> </OrderedList></p>

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

Set systems with k-wise \(\mathcal {L} \)-intersections and \( \mathcal {L} \)-differencing Sperner families modulo prime powers

  • Rudy X. J. Liu

摘要

   In this paper, we obtain the following improved upper bound on the size of k-wise \( \mathcal {L} \) L -intersecting families and \( \mathcal {L} \) L -differencing Sperner families modulo prime powers by employing linear algebra methods: (1)

Let \( k \ge 2 \) k 2 be an integer, p be a prime, \( q = p^{ \alpha } \) q = p α be a prime power with \( \alpha \ge 1 \) α 1 , and let \( \mathcal {L} \subseteq \{0, 1, \dots , q-1\} \) L { 0 , 1 , , q - 1 } be a subset with size \( s > 0 \) s > 0 . Suppose that \( \mathcal {F} \) F is a family of subsets of [n] such that \( \left| F \right| \notin \mathcal {L} \pmod {q} \) F L ( mod q ) for each \( F \in \mathcal {F} \) F F and \( \left| F_{i_1} \cap F_{i_2} \cap \cdots \cap F_{i_k} \right| \in \mathcal {L} \pmod {q} \) F i 1 F i 2 F i k L ( mod q ) for every collection of k distinct subsets in \( \mathcal {F} \) F . Then \( \left| \mathcal {F} \right| \le \left( k-1 \right) \left[ {{n-1} \atopwithdelims (){q-1}}+ {{n-1} \atopwithdelims (){q-2}}+ \cdots + {{n-1} \atopwithdelims (){0}} \right] . \) F k - 1 n - 1 q - 1 + n - 1 q - 2 + + n - 1 0 . If in addition there exists an integer \( t < p \) t < p such that \( \left| F \right| \in \left\{ q-t, q-t+1, \dots q-1 \right\} \pmod {q} \) F q - t , q - t + 1 , q - 1 ( mod q ) for each \( F \in \mathcal {F} \) F F , then \( \left| \mathcal {F} \right| \le \left( k-1 \right) \left[ {{n-1} \atopwithdelims (){q-1}}+ {{n-1} \atopwithdelims (){q-2}}+ \cdots + {{n-1} \atopwithdelims (){p - t -1}} \right] . \) F k - 1 n - 1 q - 1 + n - 1 q - 2 + + n - 1 p - t - 1 . This result not only gives an improvement to a theorem by G. Hegedüs and a theorem by Z. Xu and C. H. Yip, but also extends a theorem by L. Babai and P. Frankl.

(2)

Let p be a prime, \( q = p^{ \alpha } \) q = p α be a prime power with \( \alpha \ge 1 \) α 1 , and \( \mathcal {L} = \{l_1, l_2, \dots , l_s\} \) L = { l 1 , l 2 , , l s } be a subset of \( \{1, 2, \dots , q-1\} \) { 1 , 2 , , q - 1 } . Suppose that \( \mathcal {F} \) F is a family of subsets of [n] satisfying that \( \left| F \setminus F' \right| \in \mathcal {L} \pmod {q} \) F \ F L ( mod q ) for all distinct pairs \( F, F' \in \mathcal {F} \) F , F F . Then \( \left| \mathcal {F} \right| \le \left( {\begin{array}{c}n-1\\ q-1\end{array}}\right) + \left( {\begin{array}{c}n-1\\ q-2\end{array}}\right) +\cdots +\left( {\begin{array}{c}n-1\\ 0\end{array}}\right) . \) F n - 1 q - 1 + n - 1 q - 2 + + n - 1 0 . This result extends a theorem by Z. Xu and C. H. Yip to the case of general \( \mathcal {L} \) L with size \( \left| \mathcal {L} \right| = s \) L = s .