多部超图的不变覆盖

INVARIANT COVERS OF MULTIPARTITE HYPERGRAPHS

https://arxiv.org/pdf/2602.10849

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

1. 引言

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

无限超图的覆盖尚未得到如此广泛的研究，但见，例如，[A85]，[AH92]，[BZ19]，和 [Ko19]。我们在本文中不假设超图的有限性，但事实证明，所考虑的问题可以归结为有限情况，见第 2 节中的有限迹定理。特别是，Lovász 的估计及其由 Aharoni, Holzman 和 Krivelevich [AHK96] 提出的推广（见第 2 节）被证明对无限超图也是有效的。

本文的主要结果是 Aharoni–Holzman–Krivelevich 界的一个对称类比（见第 3 节）。以下是该结果的最简单特例。

打开网易新闻 查看精彩图片

  1. 有限近似

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

  1. 对称性的代价

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

  1. 开放问题

已知 [AHK96] Lovász 的估计是紧的（sharp）（正如 [AHK96] 中的大多数推广一样）。对称类比的紧性是一个开放问题。即使是在最简单的情况下，即针对三部 3-超图的 Lovász 估计的对称类比，我们也不知道答案。

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

原文链接：https://arxiv.org/pdf/2602.10849