BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give a new proof of a recent resolution by Michelen and Sahasrabudhe of a conjecture of Shepp and Vanderbei that the moduli of roots of Gaussian Kac polynomials of degree n, centered at 1 and rescaled by n2, should form a Poisson point process. We use this new approach to verify a conjecture of Michelen and Sahasrabudhe that the Poisson statistics are in fact universal.
For any fixed simple graph H=(V,E) and any fixed u>0, we establish the leading order of the exponential rate function for the probability that the number of copies of H in the Erdős--Rényi graph G(n,p) exceeds its expectation by a factor 1+u, assuming n−κ(H)≪p≪1, with κ(H)=1/(2Δ), where Δ≥1 is the maximum degree of H. This improves on a previous result of Chatterjee and the second author, who obtained κ(H)=c/(Δ∣E∣) for a constant c>0. Moreover, for the case of cycle counts we can take κ as large as 1/2. We additionally obtain the sharp upper tail for Schatten norms of the adjacency matrix, as well as the sharp lower tail for counts of graphs for which Sidorenko's conjecture holds. As a key step, we establish quantitative versions of Szemerédi's regularity lemma and the counting lemma, suitable for the analysis of random graphs in the large deviations regime.
For each n, let An=(σij) be an n×n deterministic matrix and let Xn=(Xij) be an n×n random matrix with i.i.d. centered entries of unit variance. We study the asymptotic behavior of the empirical spectral distribution μnY of the rescaled entry-wise product Yn=(n1σijXij). For our main result we provide a deterministic sequence of probability measures μn, each described by a family of Master Equations, such that the difference μnY−μn converges weakly in probability to the zero measure. A key feature of our results is to allow some of the entries σij to vanish, provided that the standard deviation profiles An satisfy a certain quantitative irreducibility property. An important step is to obtain quantitative bounds on the solutions to an associate system of Schwinger--Dyson equations, which we accomplish in the general sparse setting using a novel graphical bootstrap argument.
For each n, let An=(σij) be an n×n deterministic matrix and let Xn=(Xij) be an n×n random matrix with i.i.d. centered entries of unit variance. In the companion article Cook et al., we considered the empirical spectral distribution μnY of the rescaled entry-wise product Yn=n1An⊙Xn=(n1σijXij) and provided a deterministic sequence of probability measures μn such that the difference μnY−μn converges weakly in probability to the zero measure. A key feature in Cook et al. was to allow some of the entries σij to vanish, provided that the standard deviation profiles An satisfy a certain quantitative irreducibility property. In the present article, we provide more information on the sequence (μn), described by a family of Master Equations. We consider these equations in important special cases such as separable variance profiles σij2=didj and sampled variance profiles σij2=σ2(ni,nj) where (x,y)↦σ2(x,y) is a given function on [0,1]2. Associate examples are provided where μnY converges to a genuine limit. We study μn's behavior at zero and provide examples where μn's density is bounded, blows up, or vanishes while an atom appears. As a consequence, we identify the profiles that yield the circular law. Finally, building upon recent results from Alt et al., we prove that except maybe in zero, μn admits a positive density on the centered disc of radius ρ(Vn), where Vn=(n1σij2) and ρ(Vn) is its spectral radius.
For a fixed quadratic polynomial p in n non-commuting variables, and n independent N×N complex Ginibre matrices X1N,…,XnN, we establish the convergence of the empirical spectral distribution of PN=p(X1N,…,XnN) to the Brown measure of p evaluated at n freely independent circular elements c1,…,cn in a non-commutative probability space. The main step of the proof is to obtain quantitative control on the pseudospectrum of PN. Via the well-known linearization trick this hinges on anti-concentration properties for certain matrix-valued random walks, which we find can fail for structural reasons of a different nature from the arithmetic obstructions that were illuminated in works on the Littlewood--Offord problem for discrete scalar random walks.
Fix c∈(0,1) and let Γ be a ⌊cn⌋-regular digraph on n vertices drawn uniformly at random. We prove that when n is large, the (non-symmetric) adjacency matrix M of Γ is invertible with high probability. The proof uses a couplings approach based on the switchings method of McKay and Wormald. We also rely on discrepancy properties for the distribution of edges in Γ, recently proved by the author, to overcome certain difficulties stemming from the dependencies between the entries of M.
For the uniform random regular directed graph we prove concentration inequalities for (1) codegrees and (2) the number of edges passing from one set of vertices to another. As a consequence, we can deduce discrepancy properties for the distribution of edges essentially matching results for Erdős-Rényi digraphs obtained from Chernoff-type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee. Exchangeable pairs are constructed using two involutions on the set of regular digraphs: a well-known "simple switching" operation, as well as a novel "reflection" operation.
We prove that the (non-symmetric) adjacency matrix of a uniform random d-regular directed graph on n vertices is asymptotically almost surely invertible, assuming min(d,n−d)≥Clog2n for a sufficiently large constant C>0. The proof makes use of a coupling of random regular digraphs formed by "shuffling" the neighborhood of a pair of vertices, as well as concentration results for the distribution of edges recently obtained by the author (arXiv:1410.5595). We also apply our general approach to prove a.a.s.\ invertibility of Hadamard products Σ∘Ξ, where Ξ is a matrix of iid uniform ±1 signs, and Σ is a 0/1 matrix whose associated digraph satisfies certain "expansion" properties.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.