摘要
近期，Dupré la Tour 和 Fujii 以及 Hollender, Manurangsi, Meka 和 Suksompong 的研究引入了经典差异性理论的非加性函数推广，这一工作受到公平分配应用的启发。由于许多经典的差异性技术在此背景下失效，包括线性代数方法如 Beck-Fiala 定理，是否能实现可比的非加性界限仍然广泛未解。
为了更好地理解非加性差异性，我们研究了与经典 Beck-Fiala 定理相比较的稀疏设置下的覆盖函数。我们的研究设置推广了加性 Beck-Fiala 设置、分区矩阵的秩函数和图中的边覆盖。
更具体地，假设每个 $n$ 个项目仅覆盖所有函数中的 $t$ 个元素，我们证明了一个构造性的差异性界限，该界限在 $t$、颜色数 $k$ 和 $\log n$ 上是多项式级别的。
博主点评： 本文通过将非加性差异性引入经典理论，开辟了新的研究方向，尤其在公平分配问题上具有重要的应用潜力。构造性的差异性界限为后续研究提供了理论基础，值得深入探讨。