Sharp norm-moment orders for random graph matrices

What are the exact polynomial and logarithmic orders of operator-norm moments for graph-shaped matrices in the globally injective dense independent-sign model? A fixed graph shape specifies boundary and interior index roles.

Why it matters and what counts as progress

Why it matters: Sharp orders identify the logarithmic factors left undetermined by separator-based bounds with polylogarithmic slack.

What counts as progress: Matching upper and lower moment bounds for every fixed shape and p>0, including isolated roles, minimum separators and attached floating components.

How the problem developed

13 Sept 2026 · Asymptotic formula [1]
Huibo Xu, Shi Fu, Youming Qiao, and Dacheng Tao Derived sharp polynomial and logarithmic orders for expected operator norms of graph matrices in the dense Rademacher model, closing a polylogarithmic gap for fixed graph shapes.

AI contribution

AI-assisted proof gives sharp graph-matrix norm orders

For each fixed finite simple graph shape in the globally injective dense independent-sign model and fixed p>0, the pth norm moment has matching upper and lower orders n^((h+i₀−s)/2)log(2n)^(b*/2), with h the role count, i₀ isolated interior roles, s the minimum boundary-separator size and b* the largest attached floating-component count over minimum separators.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (Lean 4/Mathlib build and all-theorem axiom audit)

Human understandingFew