3. 超图上的 Turán 问题

前几节给出的简短证明使极值图论中的问题看似简单. 实际上, 我们刚才讨论许多的内容的一般性版本仍然是开放性问题. 在这里, 我们叙述一个以困难而著称的开放性问题, 即 Mantel/Turán 的超图版本.

我们定义一个 $r$-uniform 的超图由一个顶点集 $V$ 和一个边集 $E$ 组成, 其中 $E$ 里的每条边现在都是 $V$ 的 $r$ 个元素构成的子集. 普通的图就对应了 $2$-uniform 的超图.

问题 3.1. 没有四面体 ¹的 $n$ 个顶点的 $3$-uniform 超图中, 最多有多少条边 (也就是 $E$ 中的三元组个数) ?

Turán 提出了以下构造, 并推测它是最优的.

命题 3.2 (Turán). 令 $V$ 是一组 $n$ 个顶点集. 将 $V$ 分成 3 个 (大致) 相等的集合 $V_1,V_2,V_3$. 添加一个三元组 $\{x,y,z\}$ 到 $e(G)$ 如果它满足以下四个条件之一:

•	$x,y,z$ 在不同的分区
•	$x,y\in V_1$ 且 $z\in V_2$
•	$x,y\in V_2$ 且 $z\in V_3$
•	$x,y\in V_3$ 且 $z\in V_1$

(...)Turán 构造的四面体-free $3-uniform$ 超图

请读者自行检验所构建的 $3$-uniform 超图是否无四面体, 并且边密度 ²为 $5/9$.

另一方面, 最著名的密度上限约为 0.562, 这是最近使用旗代数 (Flag Algebras) 技术得到的.

1.	^ 译者注: 即四个点, 他们之间连了 $\left(\genfrac{}{}{0ex}{}{4}{3}\right)$ 条超图的边
2.	^ 译者注: 边密度是指 ${\lim }_{n\to \infty }m(n)/\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. 这里 $n$ 是点数, $m(n)$ 是所构造的 $n$ 个点的图中的边数.