The asymptotic singularity conjecture for random 0/1-matrices

From papers

Let PdP_d be the probability that a random 0/10/1-matrix of size (d+1)×(d+1)(d+1)\times(d+1) is singular; equivalently, in the associated ±1\pm1 model, let PdP_d denote the probability that a random ±1\pm1-matrix of size (d+1)×(d+1)(d+1)\times(d+1) is singular. Singularity-probability conjecture. The probability is asymptotically dominated by zero rows or columns and by pairs of equal rows or equal columns:

Pd2(d+12)12dd22d.P_d\sim 2\binom{d+1}{2}\frac{1}{2^d}\sim\frac{d^2}{2^d}.

Equivalently, a singular random ±1\pm1-matrix has, with probability tending to one in the stated sense, two rows or two columns that are equal or opposite. The conjecture refines the known lower and upper bounds, but the source gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Günter M. Ziegler, “Lectures on 0/1-polytopes”, arXiv:math/9909177 (1999).

Solutions 0

No solutions have been posted yet.