The conjecture on global synchrony with negative edges

About 1 year old · traced to

Let AA be an n×nn\times n random matrix with zero diagonal and independent off-diagonal entries satisfying

Aij={1with probability 12+δ,−1with probability 12−δ.A_{ij}=\begin{cases}1&\text{with probability }\frac12+\delta,\\\\-1&\text{with probability }\frac12-\delta.\end{cases}

A matrix is globally synchronizing when the only local minima of its Kuramoto energy are the global synchronized minima. Negative-edge synchrony conjecture. For every ε>0\varepsilon>0, if δ≥(1+ε)log⁡n2n\delta\geq(1+\varepsilon)\sqrt{\frac{\log n}{2n}}, then AA is globally synchronizing with high probability. This is motivated by the Burer–Monteiro approach to community detection; high-rank versions are known, but this rank-two-type threshold remains open.

References

Primary source

Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard and Almut Rödder, “Randomstrasse101: Open Problems of 2024”, arXiv:2504.20539 (2025).

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.