← All problems

Kahn–Komlós–Szemerédi conjecture on singularity of random Bernoulli matrices

8 years old · traced to

Let AnA_n be an n×nn\times n matrix with independent and identically distributed Rademacher random variables, taking values ±1\pm1 with equal probability. Write

\gpn=P(An is non-invertible).\gp_n=\mathbb{P}(A_n\text{ is non-invertible}).

The notation an=o(bn)a_n=o(b_n) means lim⁡n→∞an/bn=0\lim_{n\to\infty}a_n/b_n=0.

Kahn–Komlós–Szemerédi conjecture.

\gpn=(12+o(1))n.\gp_n=\left(\frac12+o(1)\right)^n.

The conjectured leading contribution comes from pairs of identical rows or columns up to reversal of sign, and the statement concerns the principal obstruction to invertibility for random Rademacher matrices.

References

Status

Source: Anirban Basak and Mark Rudelson, “Sharp transition of the invertibility of the adjacency matrices of sparse random graphs”, arXiv:1809.08454 (2021).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.