Proof Of A Conjecture Of Erdős On Triangles In Set-Systems
Proof Of A Conjecture Of Erdős On Triangles In Set-Systems
复制标题
集合系统中三角形的 Erdős 猜想的证明
DOI：
10.1007/s00493-005-0036-0
复制
发表时间：
2005
期刊：
影响因子：
1.1
通讯作者：
Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
D. Mubayi;Jacques Verstraëte
三角形是由三个集合A，B，C组成的族，使得A∩B， B∩C， C∩A都是非空的，并且$$
A \cap B \cap C = \emptyset
$$。设$$
{\user1{\mathcal{A}}}
$$为n元素集合的r元素子集族，其中不包含三角形。我们的主要结果表明，对于r≥3和n≥3r/2，我们有$$
{\left| {\user1{\mathcal{A}}} \right|} \leqslant {\left( {\begin{array}{*{20}c}
{{n - 1}} \\
{{r - 1}} \\
\end{array} } \right)}.
$$这解决了一个长期存在的猜想Erdős[7]，通过改进Bermond， Chvátal， Frankl和f<s:1> redi的早期结果。我们还证明，当且仅当$$
{\user1{\mathcal{A}}}
$$由包含固定元素的所有r元素子集组成时，等式成立。对于非均匀族也得到了类似的结果。
A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and $$
A \cap B \cap C = \emptyset
$$. Let $$
{\user1{\mathcal{A}}}
$$ be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have $$
{\left| {\user1{\mathcal{A}}} \right|} \leqslant {\left( {\begin{array}{*{20}c}
{{n - 1}} \\
{{r - 1}} \\
\end{array} } \right)}.
$$ This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if $$
{\user1{\mathcal{A}}}
$$ consists of all r-element subsets containing a fixed element.Analogous results are obtained for nonuniform families.