2019/04/23 by Ferber, Asaf, Jain, Vishesh, Luh, Kyle +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1904.10425
Let ε1, \dotsc, εn be i.i.d. Rademacher random variables taking values ± 1 with probability 1/2 each. Given an integer vector \boldsymbola = (a1, \dotsc, an), its concentration probability is the quantity ρ(\boldsymbola):=supx∈ ℤPr(ε1 a1+…+εn an = x). The Littlewood-Offord problem asks for bounds on ρ(\boldsymbola) under various hypotheses on \boldsymbola, whereas the inverse Littlewood-Offord problem, posed by Tao and Vu, asks for a characterization of all vectors \boldsymbola for which ρ(\boldsymbola) is large. In this paper, we study the associated counting problem: How many integer vectors \boldsymbola belonging to a specified set have large ρ(\boldsymbola)? The motivation for our study is that in typical applications, the inverse Littlewood-Offord theorems are only used to obtain such counting estimates. Using a more direct approach, we obtain significantly better bounds for this problem than those obtained using the inverse Littlewood--Offord theorems of Tao and Vu and of Nguyen and Vu. Moreover, we develop a framework for deriving upper bounds on the probability of singularity of random discrete matrices that utilizes our counting result. To illustrate the methods, we present the first `exponential-type' (i.e., exp(-nc) for some positive constant c) upper bounds on the singularity probability for the following two models: (i) adjacency matrices of dense signed random regular digraphs, for which the previous best known bound is O(n-1/4) due to Cook; and (ii) dense row-regular \0,1\-matrices, for which the previous best known bound is OC(n-C) for any constant C>0 due to Nguyen.