Quantitative rigidity of random graphs under adaptive real orthogonal transformations

Let A be the adjacency matrix of a random graph whose edges are independent, with probabilities in [α, 1 − α] for fixed 0 < α ≤ 1/2. We study ordinary graph matrices QᵀAQ when the real orthogonal matrix Q may be chosen after the entire graph is observed. Uniformly over these edge laws, we prove that the probability of a nonisomorphic target obtainable with min_P rank(Q − P) ≤ r = o(√(n/log n)) is at most exp[−ω((log n)²)], where P ranges over ordinary permutation matrices. The proof combines a compatible-displacement cover, rational descent to a shared finite-field descriptor, packing and state reduction, and a deterministic localization theorem preserving the complete target. We also prove an independent bounded-block result: if every component of the bipartite support graph of Q has side size at most b = o((n/log n)^(1/3)), the exceptional probability is at most exp[−(c_α/12 − o(1))n/b], where c_α = −log(1 − α²). This permits linear total movement rank. Neither result assumes rationality, a height bound, or that Q fixes the all-ones vector. Both are restrictions on orthogonal witnesses and do not establish unrestricted determination by the adjacency spectrum.