{"id":"arxiv/2609.14266","url":"https://arxiv.org/abs/2609.14266","tags":["math.PR","cs.DS"],"score":0,"title":"Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses","domain":"math.PR","source":"arxiv","authors":["Huibo Xu","Shi Fu","Youming Qiao","Dacheng Tao"],"reviews":0,"subject":"math.PR","summary":"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$ isolated summation vertices, $s$ the minimum boundary-separator size, and $a_*$ maximizes an active-component count over minimum…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-13","reactions":{}}