Randomstrasse101 Open Problems (2025) — Conjecture 1 (Sharp graph matrix bounds)

Definitions and mathematical statement

Fix a shape $\alpha$, and write $M_\alpha(n)$ for its associated random graph matrix, making the dependence on the size parameter $n$ explicit. The supplied record does not define a shape, the admissible class of shapes, the construction or probability law of $M_\alpha(n)$, or the matrix norm denoted by $\|\cdot\|$. These conventions must be recovered from the cited source before this becomes a fully specified mathematical statement.

Subject to those unresolved conventions, the supplied conjecture asserts that there exist functions $f$ and $g$, depending only on the shape, such that for every fixed admissible shape $\alpha$, \[ \mathbb{E}\|M_\alpha(n)\| =\Theta\!\left(n^{f(\alpha)}(\log n)^{g(\alpha)}\right) \qquad(n\to\infty). \] Here the asymptotic relation is taken through admissible sizes: for each fixed $\alpha$, there must be constants $0<c_\alpha\le C_\alpha<\infty$ and a threshold $n_0(\alpha)>1$ such that every admissible $n\ge n_0(\alpha)$ satisfies \[ c_\alpha n^{f(\alpha)}(\log n)^{g(\alpha)} \le \mathbb{E}\|M_\alpha(n)\| \le C_\alpha n^{f(\alpha)}(\log n)^{g(\alpha)}. \] The permitted ranges of the exponents $f(\alpha)$ and $g(\alpha)$ are not specified in the record; in particular, no integrality or sign restriction is supplied. The statement concerns the expected norm. The supplied context reports that iterated linear inequalities do not give sharp bounds for some shapes and that some shapes require additional nonconstant factors; it supplies neither definitions of those inequalities nor the examples.

Short English statement

For each fixed shape, the conjecture predicts that the expected norm of its random graph matrix has growth equal, up to positive constant factors, to a power of $n$ times a power of $\log n$, with both exponents depending only on the shape. The graph matrix model and norm remain unspecified in the supplied record.

Sources

• Local UnsolvedMath registry, permanent ID $800848$, source problem code catalogue entry; supplied title: "Randomstrasse101 Open Problems (2025) --- Conjecture 1 (Sharp graph matrix bounds)." The registry attributes the problem to Bandeira et al., records proposed year 2026, and labels it open. This is a supplied status label, not an independently verified assessment.
• Bandeira et al., Randomstrasse101: Open Problems of 2025 (2026), Conjecture 1; supplied context: "Sharp graph matrix bounds." Supplied source URL: https://arxiv.org/abs/2603.29571. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not a claim of independent source consultation.