On the discrepancy of random low degree set systems
On the discrepancy of random low degree set systems
复制标题
关于随机低度集系统的差异
DOI：
10.1002/rsa.20935
复制
发表时间：
2018
影响因子：
1
通讯作者：
Raghu Meka
中科院分区：
文献类型：
--
作者：
N. Bansal;Raghu Meka
受著名的Beck - Fiala猜想的启发，我们考虑随机设置，其中有n个元素和m个集合，每个元素位于t个随机选择的集合中。在这种情况下，Ezra和Lovett给出了n≤m时的O（(tlogt)1/2）差异界和n≤mt时的O(1)差异界。本文在t=Ω（(loglogm)2）的温和假设下，给出了n和m的整个范围的紧O(t)界。结果基于两个步骤。首先，将部分着色方法应用于n=mlogO(1)m的情况，并利用随机集系统的性质证明了所产生的总体差异不超过O(t)。其次，我们利用LP对偶性和一个细心的计数论证，将一般情况简化为n≤mlogO(1)m。
Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an O((tlogt)1/2) discrepancy bound when n ≤ m and an O(1) bound when n ≫ mt. In this paper, we give a tight O(t) bound for the entire range of n and m, under a mild assumption that t=Ω((loglogm)2) . The result is based on two steps. First, applying the partial coloring method to the case when n=mlogO(1)m and using the properties of the random set system we show that the overall discrepancy incurred is at most O(t) . Second, we reduce the general case to that of n≤mlogO(1)m using LP duality and a careful counting argument.