标题： 一个改进的贝克-菲亚拉猜想界 显示英文标题

标题： An Improved Bound for the Beck-Fiala Conjecture

摘要： 1981年，Beck和Fiala [离散应用数学，1981]猜想，给定一个集合系统$A \in \{0,1\}^{m \times n}$，其度数最多为$k$（即，$A$的每一列最多有$k$个非零值），其组合差异$\mathsf{disc}(A) := \min_{x \in \{\pm 1\}^n} \|Ax\|_\infty$最多为$O(\sqrt{k})$。此前，对此猜想的最佳已知界限要么是$O(k)$，最初由Beck和Fiala [离散应用数学]建立。 数学，1981]，或$O(\sqrt{k \log n})$，首先由 Banaszczyk [Random Struct. Algor., 1998] 证明。我们给出了一个算法证明，当$k \geq \log^5 n$时，$O(\sqrt{k \log\log n})$的改进界，从而在几乎整个$k$范围内将 Beck-Fiala 猜想提高到$O(\sqrt{\log \log n})$。 显示英文摘要

摘要： In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system $A \in \{0,1\}^{m \times n}$ with degree at most $k$ (i.e., each column of $A$ has at most $k$ non-zeros), its combinatorial discrepancy $\mathsf{disc}(A) := \min_{x \in \{\pm 1\}^n} \|Ax\|_\infty$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [Discrete Appl. Math, 1981], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [Random Struct. Algor., 1998]. We give an algorithmic proof of an improved bound of $O(\sqrt{k \log\log n})$ whenever $k \geq \log^5 n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.