No abstract uploaded!

In a uniform random recursive$k$-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to$n$, chooses$k$uniform random parents from among the nodes of smaller index. If$S$_{$n$}is the shortest path distance from node$n$to the root, then we determine the constant$σ$such that$S$_{$n$}/log$n$→$σ$in probability as$n$→∞. We also show that max_{1≤$i$≤$n$}$S$_{$i$}/log$n$→$σ$in probability.

General upper tail estimates are given for counting edges in a random induced subhypergraph of a fixed hypergraph ℋ, with an easy proof by estimating the moments. As an application we consider the numbers of arithmetic progressions and Schur triples in random subsets of integers. In the second part of the paper we return to the subgraph counts in random graphs and provide upper tail estimates in the rooted case.

We consider a general class of $N\times N$ random matrices whose entries $h_{ij}$ are independent up to a symmetry constraint, but not necessarily identically distributed. Our main result is a local semicircle law which improves previous results [14] both in the bulk and at the edge. The error bounds are given in terms of the basic small parameter of the model, $\max_{i,j} \E \abs{h_{ij}}^2$. As a consequence, we prove the universality of the local $n$-point correlation functions in the bulk spectrum for a class of matrices whose entries do not have comparable variances, including random band matrices with band width $W\gg N^{1-\e_n}$ with some $\e_n>0$ and with a negligible mean-field component. In addition, we provide a coherent and pedagogical proof of the local semicircle law, streamlining and strengthening previous arguments from [17,19,6].

We consider the ensemble of adjacency matrices of Erd{\H o}s-R\'enyi random graphs, i.e.\ graphs on $N$ vertices where every edge is chosen independently and with probability $p \equiv p(N)$. We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption $p N \gg N^{2/3}$, we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erd{\H o}s-R\'enyi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erd{\H o}s-R\'enyi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least $4 + \epsilon$ moments.