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

Sharpening of the Erdős–Ko–Rado theorem

  • Péter Frankl,
  • Gyula O. H. Katona,
  • Kartal Nagy

摘要

If a family \(\mathcal {F}\) F of k-element subsets of an n-element set is intersecting, then the sum of the sizes of the pairwise intersections of any \(\ell \) members of the family is at least \({\ell \atopwithdelims ()2}\) 2 . The classic result of Erdős, Ko and Rado says that under the condition \(2k\le n\) 2 k n an intersecting family of k-element subsets of an n-element set cannot have more than \({n-1\atopwithdelims ()k-1}\) n - 1 k - 1 members. Is this weaker condition for the sum of the sizes of the pairwise intersections sufficient to have the conclusion of the Erdős–Ko–Rado theorem? We will see that much more is true, the bound \({\ell \atopwithdelims ()2}\) 2 can be replaced by \({\ell -1\atopwithdelims ()2}+1\) - 1 2 + 1 .