2020/11/02 by Ferber, Asaf, Kwan, Matthew, Sauermann, Lisa · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2011.01291
Consider a random n× n zero-one matrix with "density" p, sampled according to one of the following two models: either every entry is independently taken to be one with probability p (the "Bernoulli" model), or each row is independently uniformly sampled from the set of all length-n zero-one vectors with exactly pn ones (the "combinatorial" model). We give simple proofs of the (essentially best-possible) fact that in both models, if min(p,1-p)≥ (1+ε)log n/n for any constant ε>0, then our random matrix is nonsingular with probability 1-o(1). In the Bernoulli model this fact was already well-known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person.