On the discrepancy of random low degree set systems

DOI10.1002/RSA.20935MaRDI QIDQ5136929zbMATH OpenOpenAlexFDO

Authors N. Bansal, Raghu Meka

Publication date 30 November 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.03374, https://ir.cwi.nl/pub/29306

zbMATH Keywords

discrepancyrandom set systemsparse

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: 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 in the regime when $nleqm$ and an $O(1)$ bound when $ngg{m}^t$. In this paper, we give a tight $O(sqrtt)$ bound for the entire range of $n$ and $m$, under a mild assumption that $t=Omega(loglogm{)}^2$. The result is based on two steps. First, applying the partial coloring method to the case when $n=mlo{g}^{O(1)}m$ and using the properties of the random set system we show that the overall discrepancy incurred is at most $O(sqrtt)$. Second, we reduce the general case to that of $nleqmlo{g}^{O(1)}m$ using LP duality and a careful counting argument.

Recommendations

• On the discrepancy of random low degree set systems
• On the Beck-Fiala conjecture for random set systems
• On the Beck-Fiala conjecture for random set systems
• A Fourier-analytic approach for the discrepancy of random set systems
• An improvement of the Beck-Fiala theorem

Cited in

(12)

• On the Beck-Fiala theorem
• On the Beck-Fiala conjecture for random set systems
• On the discrepancy of random matrices with many columns
• On the Beck-Fiala conjecture for random set systems
• A Fourier-analytic approach for the discrepancy of random set systems
• On the discrepancy of random low degree set systems
• An improvement of the Beck-Fiala theorem
• The Phase Transition of Discrepancy in Random Hypergraphs
• The discrepancy of random rectangular matrices
• Critical window of the symmetric perceptron
• Zero-one laws for random feasibility problems
• Weaver's discrepancy for Gaussian random vectors

This page was built for publication: On the discrepancy of random low degree set systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136929)