<p>We consider families, <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> </InlineEquation> of <i>k</i>-subsets of an <i>n</i>-set. For integers <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(r\ge 2\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(t\ge 1\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> </InlineEquation> is called <i>r</i>-wise <i>t</i>-intersecting if any <i>r</i> of its members have at least <i>t</i> elements in common. The most natural construction of such a family is the full <i>t</i>-star, consisting of all <i>k</i>-sets containing a fixed <i>t</i>-set. In the case <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(r=2\)</EquationSource> </InlineEquation> the Exact Erdős-Ko-Rado Theorem shows that the full <i>t</i>-star is largest if <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="158" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\ge (t+1)(k-t+1)\)</EquationSource> </InlineEquation>. In the present paper, we prove that for <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq7.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="196" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\ge (2.5t)^{1/(r-1)}(k-t)+k\)</EquationSource> </InlineEquation>, the full <i>t</i>-star is largest in case of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq8.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(r\ge 3\)</EquationSource> </InlineEquation>. Examples show that the exponent <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_166_Article_IEq9.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(\frac{1}{r-1}\)</EquationSource> </InlineEquation> is best possible. This represents a considerable improvement on a recent result of Balogh and Linz.</p>

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

On r-wise t-intersecting Uniform Families

  • Peter Frankl,
  • Jian Wang

摘要

We consider families, \(\mathcal {F}\) of k-subsets of an n-set. For integers \(r\ge 2\) , \(t\ge 1\) , \(\mathcal {F}\) is called r-wise t-intersecting if any r of its members have at least t elements in common. The most natural construction of such a family is the full t-star, consisting of all k-sets containing a fixed t-set. In the case \(r=2\) the Exact Erdős-Ko-Rado Theorem shows that the full t-star is largest if \(n\ge (t+1)(k-t+1)\) . In the present paper, we prove that for \(n\ge (2.5t)^{1/(r-1)}(k-t)+k\) , the full t-star is largest in case of \(r\ge 3\) . Examples show that the exponent \(\frac{1}{r-1}\) is best possible. This represents a considerable improvement on a recent result of Balogh and Linz.