Sharp norm bounds for graph matrices
Let $\alpha$ be a shape: a small fixed graph whose vertex set $V(\alpha)$ is partitioned into an ordered left part $U_\alpha$ and an ordered right part $V_\alpha$. For i.i.d. Rademacher variables $(\varepsilon_{i,j})_{i < j}$, with $\varepsilon_{j,i} = \varepsilon_{i,j}$, the graph matrix $M_\alpha$ (Ahn, Medarametla and Potechin) is the $n^{|U_\alpha|} \times n^{|V_\alpha|}$ matrix, with rows and columns indexed by ordered tuples of distinct elements of $[n]$, $$M_\alpha = \sum_{\varphi} \Bigl(\prod_{(i,j) \in E(\alpha)} \varepsilon_{\varphi(i),\varphi(j)}\Bigr)\, e_{\varphi(U_\alpha)}\, e_{\varphi(V_\alpha)}^{\mathsf T},$$ summed over injective maps $\varphi : V(\alpha) \to [n]$. The moment method gives functions $f$ and $g$ of $\alpha$ with $\Omega(n^{f(\alpha)}) \le \mathbb{E}\|M_\alpha\| \le O(n^{f(\alpha)} (\log n)^{g(\alpha)})$. The matrix chaos inequalities of Bandeira, Lucca, Nizić-Nikolac and van Handel remove the logarithmic factor for some shapes, and some shapes do carry extra non-constant factors.
Problem. Prove or disprove that there are functions $f$ and $g$, depending only on the shape $\alpha$, such that $$\mathbb{E}\|M_\alpha\| = \Theta\bigl(n^{f(\alpha)} (\log n)^{g(\alpha)}\bigr).$$
Source: Nizić-Nikolac, Open Problem 31 of Randomstrasse101, in “Sharp Bounds for Graph Matrices” (2025); Entry 14 of arXiv:2603.29571.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- graph matrices, matrix chaos, random matrices, Randomstrasse101, Sum-of-Squares
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2025,
author = {Bandeira, Afonso S. and Dmitriev, Daniil and Lucca, Kevin and Nizi{\'c}-Nikolac, Petar and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2025},
year = {2026},
eprint = {2603.29571},
archivePrefix = {arXiv}
}
@misc{ahn2016graph,
author = {Ahn, Kwangjun and Medarametla, Dhruv and Potechin, Aaron},
title = {Graph matrices: norm bounds and applications},
year = {2016},
eprint = {1604.03423},
archivePrefix = {arXiv}
}
@inproceedings{bandeira2025chaos,
author = {Bandeira, Afonso S. and Lucca, Kevin and Nizi{\'c}-Nikolac, Petar and van Handel, Ramon},
title = {Matrix chaos inequalities and chaos of combinatorial type},
booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)},
pages = {795--805},
year = {2025}
}
Resolution claims
Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model, including overlapping or empty matrix boundaries, we prove $\mathbb E\|M_α\|=Θ_α(n^{(v+h-s)/2}(\log n)^{a_*/2})$, where $v$ counts vertices, $h$ …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-03 | Open → Solution claimed | The registry's curators | Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses v1 recorded from arXiv:2609.14266v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00059, "Sharp norm bounds for graph matrices", clopen.solutions.