<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n &gt; 2k \geq 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>&gt;</mo> <mn>2</mn> <mi>k</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> and let <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathcal F \subset {[n]\choose k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo>⊂</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> <mi>k</mi> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation> be an intersecting <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-graph on <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> vertices, that is, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(F\cap F' \neq \emptyset\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>∩</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> <mo>≠</mo> <mi mathvariant="normal">∅</mi> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq6"> <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>.By the Erd\H{o}s--Ko--Rado Theorem <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(|\mathcal F| \leq { n - 1\choose k - 1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">|</mo> </mrow> <mo>≤</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation> with equality holding only for the full-star, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mathcal S_x\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">S</mi> <mi>x</mi> </msub> </math></EquationSource> </InlineEquation>, the family of all <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-sets containing the vertex <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(x\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>x</mi> </math></EquationSource> </InlineEquation>.If we exclude stars, that is, subfamilies of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\mathcal S_x\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">S</mi> <mi>x</mi> </msub> </math></EquationSource> </InlineEquation> then <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(|\mathcal F| \leq { n - 1\choose k - 1} - { n - k - 1\choose k - 1} + 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">|</mo> </mrow> <mo>≤</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> <mo>-</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> was proved by Hilton and Milner who determined the families attaining equality as well.Half a century later Han and Kohayakawa determined the next largest families.Then very recently Huang and Peng determined the fourth largest families.That is, they determined the largest families assuming that <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is not a star and it is not contained neither in the Hilton--Milner families nor in the Han--Kohayakawa families.In the present paper we provide a unified simple proof for these two theorems as well as solve the corresponding problem for <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(t \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>t</mi> </math></EquationSource> </InlineEquation>-intersecting families <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\((|F \cap F'| \geq t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>F</mi> <mo>∩</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> <mo stretchy="false">|</mo> <mo>≥</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> albeit only for<InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(n &gt; t + \max \{4t(k - t + 1)^2, 2(t + 1)^2\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>&gt;</mo> <mi>t</mi> <mo>+</mo> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mn>4</mn> <mi>t</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>,</mo> <mn>2</mn> <msup> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Concise proofs concerning the size and structure of large intersecting \(k\)-graphs

  • P. Frankl

摘要

Let \(n > 2k \geq 4\) n > 2 k 4 and let \(\mathcal F \subset {[n]\choose k}\) F [ n ] k be an intersecting \(k\) k -graph on \(n\) n vertices, that is, \(F\cap F' \neq \emptyset\) F F for all \(F, F' \in \mathcal F\) F , F F .By the Erd\H{o}s--Ko--Rado Theorem \(|\mathcal F| \leq { n - 1\choose k - 1}\) | F | n - 1 k - 1 with equality holding only for the full-star, \(\mathcal S_x\) S x , the family of all \(k\) k -sets containing the vertex \(x\) x .If we exclude stars, that is, subfamilies of \(\mathcal S_x\) S x then \(|\mathcal F| \leq { n - 1\choose k - 1} - { n - k - 1\choose k - 1} + 1\) | F | n - 1 k - 1 - n - k - 1 k - 1 + 1 was proved by Hilton and Milner who determined the families attaining equality as well.Half a century later Han and Kohayakawa determined the next largest families.Then very recently Huang and Peng determined the fourth largest families.That is, they determined the largest families assuming that \(\mathcal F\) F is not a star and it is not contained neither in the Hilton--Milner families nor in the Han--Kohayakawa families.In the present paper we provide a unified simple proof for these two theorems as well as solve the corresponding problem for \(t \) t -intersecting families \((|F \cap F'| \geq t)\) ( | F F | t ) albeit only for \(n > t + \max \{4t(k - t + 1)^2, 2(t + 1)^2\}\) n > t + max { 4 t ( k - t + 1 ) 2 , 2 ( t + 1 ) 2 } .