A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
复制标题
图和超图的 Hajnal-Szemerédi 定理的多部分版本
DOI：
10.1017/s096354831200048x
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
K. Markström
中科院分区：
文献类型：
--
作者：
A. Lo;K. Markström
图 G 中的完美 Kt 匹配是由 Kt 的顶点不相交副本组成的生成子图。 Hajnal 和 Szemerédi 的经典定理指出，如果 G 是 n 阶图，且最小度 δ(G) ≥ (t − 1)n/t 且 t|n，则 G 包含完美的 Kt 匹配。设 G 是一个 t 分图，其中顶点类 V1, …, Vt 的大小均为 n。我们证明，对于任何 γ > 0，如果对于每个 j ≠ i，每个顶点 x ∈ Vi 至少连接到 Vj 的 $\bigl ((t-1)/t + \gamma \bigr )n$ 个顶点，则 G 包含完美的 Kt 匹配，前提是 n 足够大。因此，我们渐进地验证了 Fischer [6] 的猜想。此外，我们考虑根据代码协议对超图进行推广。
A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.