Spectra of large random trees

Details Spectra of large random trees Spectra of large random trees

2009-03-20

arxiv.org/abs/0903.3589v3

Mathematics

Probability

40 pages, 4 figures, revised in light of referees' comments. In particular, the treatment of the "random comb" example in the

Scientific paper

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees, we show that the empirical spectral distributions for each of a number of random tree models converge to a deterministic (model dependent) limit as the number of vertices goes to infinity. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain precise asymptotics on the mass assigned to zero by the empirical spectral measures via the connection with the cardinality of a maximal matching. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, non-negative random variables with finite expected value. We greatly extend a celebrated result obtained by Schwenk for the uniform random trees by showing that, under mild conditions, with probability converging to one, the spectrum of a realization is shared by at least one other tree. For the the linear preferential attachment model with parameter $a > -1$, we show that the suitably rescaled $k$ largest eigenvalues converge jointly.

Affiliated with

Also associated with

No associations

Rating

Spectra of large random trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spectra of large random trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectra of large random trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642543