论文标题
hajnal-szemerédi定理的差异版本
A discrepancy version of the Hajnal-Szemerédi theorem
论文作者
论文摘要
完美的$ k_r $ - 在图$ g $中使用是$ g $中$ g $的$ k_r $的顶点 - 偶数副本，涵盖了$ g $的每个顶点。著名的hajnal-szemerédi定理决定了强迫完美的$ k_r $的最低学位阈值 - 在图$ g $中使用。差异的概念出现在数学的许多分支中。在图形设置中，一个人从$ \ { - 1,1 \} $中分配了图$ g $标签的边缘，并且一个寻求具有“高”差异的$ g $的子结构$ f $ f $ f $ f $（即$ f $ in $ f $ in v $ f $远非$ 0 $ $ 0 $）。在本文中，我们确定图形包含完美$ k_r $的最低度阈值。
A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$. The famous Hajnal--Szemerédi theorem determines the minimum degree threshold for forcing a perfect $K_r$-tiling in a graph $G$. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $\{-1,1\}$, and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$-tiling of high discrepancy.
