论文标题
与最大覆盖号码的相交和2美元的$ 2 $更新的超图：Erdős-Lovász主题重新审视
Intersecting and $2$-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited
论文作者
论文摘要
Erdős和Lovász注意到，$ r $统一的相交超图$ h $与最大覆盖号码，即$τ（h）= r $，必须至少具有$ \ frac {8} {3} {3} r-3 $ edges。 45年来，这一下限没有改善。我们试图通过研究一些小案例来了解真相是否非常接近这个简单的界限来理解原因。令$ q（r）$表示相交$ r $均匀的超图中的最小边数。众所周知，$ q（3）= 6 $和$ q（4）= 9 $。我们获得以下新结果：均匀性4的极端示例是唯一的。令人惊讶的是，无论如何，它都不是对称的。对于均匀性5，$ q（5）= 13 $，我们找到了3个示例，它们都不是已知的图。我们同时使用理论参数和计算机搜索。在Erdős和Lovász的脚步中，当超图是有限的投影平面的一部分时，我们也考虑了特殊情况。我们确定$ r \ in \ {3,4,5,6 \} $的确切答案。对于统一性6，有一个独特的极端例子。 在一个相关的问题中，我们尝试找到带有最大覆盖号码的$ 2 $更新的$ r $ r $均匀的超图，即$τ（h）= r-1 $。一个无限的示例家族是要采用$（2R-2）$ - 顶点套装的所有可能的$ r $ - 集。还有一个几何候选者：双皮子。这些是$λ= 2 $的对称2设计。我们确定，在18个已知实例中只有3个双胞胎是极端的。
Erdős and Lovász noticed that an $r$-uniform intersecting hypergraph $H$ with maximal covering number, that is $τ(H)=r$, must have at least $\frac{8}{3}r-3$ edges. There has been no improvement on this lower bound for 45 years. We try to understand the reason by studying some small cases to see whether the truth lies very close to this simple bound. Let $q(r)$ denote the minimum number of edges in an intersecting $r$-uniform hypergraph. It was known that $q(3)=6$ and $q(4)=9$. We obtain the following new results: The extremal example for uniformity 4 is unique. Somewhat surprisingly it is not symmetric by any means. For uniformity 5, $q(5)=13$, and we found 3 examples, none of them being some known graph. We use both theoretical arguments and computer searches. In the footsteps of Erdős and Lovász, we also consider the special case, when the hypergraph is part of a finite projective plane. We determine the exact answer for $r\in \{3,4,5,6\}$. For uniformity 6, there is a unique extremal example. In a related question, we try to find $2$-intersecting $r$-uniform hypergraphs with maximal covering number, that is $τ(H)=r-1$. An infinite family of examples is to take all possible $r$-sets of a $(2r-2)$-vertex set. There is also a geometric candidate: biplanes. These are symmetric 2-designs with $λ=2$. We determined that only 3 biplanes of the 18 known examples are extremal.
