The conjecture on global synchrony with negative edges

From papers

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+ε)logn2n\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.

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

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

Solutions 0

No solutions have been posted yet.