REVIEW
Spectral distribution for biased orientations of random graphs
Combinatorics · Submitted 7 Nov 2026 · 21 references
Pith's verdict: Clean new results on the eigenvalue distribution of biased random orientations. The proofs are rigorous and the exposition is careful. The paper is a solid contribution, suitable for a good journal.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
For biased random digraphs, the bulk spectrum follows a semicircle law while a growing number of extreme eigenvalues diverge to explicit limits at scale np_n.
The reading
What carries the argument
The central objects are the sixth-root Hermitian adjacency matrix (second kind) for oriented graphs, and its decomposition into a deterministic mean matrix M_n = (p/2)(J_n - I_n) + i p a S_n, plus a random centered matrix W_n. The argument rests on three pillars: (1) an exact diagonalization of the deterministic mean (Lemma 1) giving eigenvalues proportional to cot((θ + (j-1)π)/n), which allows explicit spectral control; (2) the classical moment method for the centered matrix (Lemma 2), counting closed walks to show convergence of spectral moments to the semicircle moments; (3) a matrix Bernstein inequality (Tropp) to bound the operator norm of W_n, and a rank-plus-norm decomposition that splits the mean into a small-rank part and a small-norm part, enabling the passage from W_n to H_n via Weyl's inequality and rank inequalities.
Extended reading notes
Core claim
The author proves two complementary spectral results for the model D(n,p,p'). Theorem 1 shows that under the mild condition n(p(1-p) + $3p^{2}$ p'(1-p')) → ∞, the empirical spectral distribution of the matrix H_n/s_n (where s_n = sqrt{nν}) converges weakly in probability to the semicircle law. This holds both for the centered matrix W_n and for the uncentered matrix H_n, as well as for the expected empirical measure. Theorem 2 gives the exact spectrum of the mean matrix M_n = E[H_n] via a cotangent formula (Lemma 1), and then shows that for sequences where np_n/log n → ∞ and p'_n tends to a limit r ≠ 1/2, the k-th largest eigenvalue λ_k(H_n) satisfies λ_k(H_n)/(np_n) → c^* / (θ^* + (k-1)π), with corresponding limits for the smallest eigenvalues. When r = 1/2, only λ_1/(np_n) → 1/2 and all other eigenvalues are o_P(np_n). Thus biased orientations create infinitely many eigenvalues on the scale np_n, while unbiased ones produce only one.
Load-bearing premise
Every unordered pair of vertices (u,v) independently decides whether an edge is present and, if present, which direction it takes; this independence is essential for the moment method, the matrix Bernstein inequality, and the exact diagonalization of the mean.
Editorial extensions
If this is right
- For any fixed k ≥ 1, the k-th largest eigenvalue of a biased random digraph scales as np_n and converges to an explicit constant depending on the limiting bias; thus the number of eigenvalues with order np_n grows with n.
- The proportion of eigenvalues outside any fixed enlargement of the semicircle bulk [(-2+ε)s_n, (2+ε)s_n] tends to zero, but the absolute count of such exceptional eigenvalues tends to infinity in probability when the bias is nonzero.
- In the unbiased special case p'=1/2, the results recover a single leading eigenvalue ∼ np_n/2 and all other eigenvalues are o_P(np_n), consistent with previous work.
- The explicit formula for the mean eigenvalues (Equation 3.5) provides a complete deterministic reference for the spectrum, useful for constructing tests of orientation bias in empirical networks.
- The semicircle law in Theorem 1 holds for any gain graph with independent entries satisfying the same variance and boundedness conditions, as the proof of Lemma 2 does not rely on the specific sixth-root weights.
Reading between the lines
- The paper's exact diagonalization suggests that for any fixed p>0 and p'≠1/2, the unscaled limiting spectral measure of the mean is a Cauchy-like distribution (Equation 6.6), which differs sharply from the semicircle shape of the bulk; this 'two-shape' behavior may be a universal feature of random matrices with a large-rank non-null mean.
- The results imply that in a statistical setting where one observes an oriented graph and wants to test whether the orientation is unbiased (p'=1/2) against a biased alternative, the scaled extreme eigenvalues (normalized by np_n) could serve as a consistent test statistic, since under unbiasedness only one eigenvalue stands out while under bias many do.
- Although the paper does not study the transition when p'_n approaches 1/2 at a rate of order n^{-1/2} (where the norm of the imaginary mean matches the bulk width), it identifies this as an open problem; the present results provide the two limiting regimes on either side of this critical window.
Original abstract
We study the Hermitian adjacency matrix of the second kind for biased orientations of Erdos-Renyi random graphs. In the model $D(n,p,p')$, an edge is present with probability $p$ and, conditional on its presence, is directed from its smaller to its larger endpoint with probability $p'$. Both parameters may depend on $n$, and biased tournaments are the special case $D(n,1,p')$. We prove a global semicircle law whenever $n(p(1-p)+3p^2p'(1-p')) \to \infty$, for both the centered and the uncentered matrix, and also for the expected empirical spectral measure. Our second theorem gives the exact spectrum of the mean matrix and the limits of the extreme eigenvalues on the scale $np$, under a sufficient density assumption. The main difference from the unbiased random orientations (where $p'=1/2$) is emergence of multiple large eigenvalues. The proofs include the closed-walk counting, control of the moment variances, an explicit diagonalization of the deterministic bias, and the passage from centered to uncentered spectral measures.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We study the Hermitian adjacency matrix of the second kind for biased orientations of Erdos-Renyi random graphs. In the model $D(n,p,p')$, an edge is present with probability $p$ and, conditional on its presence, is directed from its smaller to its larger endpoint with probability $p'$. Both parameters may depend on $n$, and biased tournaments are the special case $D(n,1,p')$. We prove a global semicircle law whenever $n(p(1-p)+3p^2p'(1-p')) \to \infty$, for both the centered and the uncentered matrix, and also for the expected empirical spectral measure. Our second theorem gives the exact spectrum of the mean matrix and the limits of the extreme eigenvalues on the scale $np$, under a sufficient density assumption. The main difference from the unbiased random orientations (where $p'=1/2$) is emergence of multiple large eigenvalues. The proofs include the closed-walk counting, control of the moment variances, an explicit diagonalization of the deterministic bias, and the passage from centered to uncentered spectral measures.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study the Hermitian adjacency matrix of the second kind for biased orientations of Erdos-Renyi random graphs. | contribution 0.97 | 0.90 | 0.04 | asserted 0.72 |
| s1 | In the model $D(n,p,p')$, an edge is present with probability $p$ and, conditional on its presence, is directed from its smaller to its larger endpoint with probability $p'$. | method 0.90 | 0.18 | 0.03 | asserted 0.99 |
| s2 | Both parameters may depend on $n$, and biased tournaments are the special case $D(n,1,p')$. | background 0.70 | 0.14 | 0.02 | asserted 0.89 |
| s3 | We prove a global semicircle law whenever $n(p(1-p)+3p^2p'(1-p')) \to \infty$, for both the centered and the uncentered matrix, and also for the expected empirical spectral measure. | result 1.00 | 0.96 | 0.59 | asserted 1.00 |
| s4 | Our second theorem gives the exact spectrum of the mean matrix and the limits of the extreme eigenvalues on the scale $np$, under a sufficient density assumption. | result 0.92 | 0.96 | 0.17 | asserted 1.00 |
| s5 | The main difference from the unbiased random orientations (where $p'=1/2$) is emergence of multiple large eigenvalues. | interpretation 0.73 | 0.76 | 0.36 | asserted 1.00 |
| s6 | The proofs include the closed-walk counting, control of the moment variances, an explicit diagonalization of the deterministic bias, and the passage from centered to uncentered spectral measures. | method 1.00 | 0.94 | 0.04 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.