Kahn–Komlós–Szemerédi conjecture on singularity of random Bernoulli matrices
Let be an matrix with independent and identically distributed Rademacher random variables, taking values with equal probability. Write
The notation means .
Kahn–Komlós–Szemerédi conjecture.
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
- Solved: Konstantin Tikhomirov. Singularity of random Bernoulli matrices (Annals of Mathematics, 2020) https://arxiv.org/abs/1812.09016
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.