Randomstrasse101 Open Problems (2024) — Conjecture 3 (Global Synchrony with negative edges)

Definitions and mathematical statement

For each positive integer $n$, let $A^{(n)}\in{\mathbb{R}}^{n\times n}$ be a random matrix with $A^{(n)}_{ii}=0$ and, for every $i\ne j$, \[ \Pr\left(A^{(n)}_{ij}=1\right)=\frac12+\delta_n, \qquad \Pr\left(A^{(n)}_{ij}=-1\right)=\frac12-\delta_n. \] The probabilities require $-\tfrac12\leq\delta_n\leq\tfrac12$. The conjectured regime is, for a fixed $\varepsilon>0$, \[ (1+\varepsilon)\sqrt{\frac{\log n}{2n}} \leq\delta_n\leq\frac12 \] for all sufficiently large $n$. Here $\log$ denotes the natural logarithm, and the subscript on $\delta_n$ permits dependence on $n$.

Supplied conjecture, with unresolved definitions. Under the intended random matrix model, $A^{(n)}$ is globally synchronizing with high probability in this regime. Writing $\mathcal G_n$ as a placeholder for the intended class of globally synchronizing matrices, the asserted conclusion is \[ \Pr\left(A^{(n)}\in\mathcal G_n\right)\longrightarrow 1 \qquad\text{as }n\longrightarrow\infty. \] The supplied record does not define global synchronization, its associated dynamics, or the initial conditions and quantifiers that determine membership in $\mathcal G_n$. It also specifies only entrywise marginal probabilities: it does not state whether $A^{(n)}$ is symmetric or which entries are independent. Consequently, neither $\mathcal G_n$ nor the joint probability law is determined by the supplied text, and the displayed limit is a formal rendering of the claimed conclusion rather than a fully specified mathematical conjecture. The asymptotic formulation allows admissible bias sequences; the source does not explicitly specify uniformity in the bias parameter.

Short English statement

The supplied conjecture predicts that a random matrix with zero diagonal and entries in $\{-1,1\}$ becomes globally synchronizing with probability tending to one when its positive bias is at least $(1+\varepsilon)\sqrt{\log n/(2n)}$, for every fixed $\varepsilon>0$. A precise statement requires the missing definition of global synchronization and the intended joint distribution of the entries.

Sources

• Local UnsolvedMath registry, permanent ID $800838$, exact source problem code catalogue entry, AMR Open Problem Lists. The supplied record labels this problem open; that label is supplied curation, not an independently verified mathematical or literature assessment.
• Bandeira et al., Randomstrasse101: Open Problems of 2024 (2025), Conjecture 3, https://arxiv.org/abs/2504.20539. The supplied attribution and context are "Global Synchrony with negative edges"; the registry gives Bandeira et al. as proposers and 2025 as the proposed year.
• Supplied provenance: accessed 2026-10-16; extraction method arxiv_latex; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. These are supplied provenance details; the linked source was not independently accessed or verified for this draft.