Doctoral Degrees (Mathematical Sciences)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/852

Browse

Browsing Doctoral Degrees (Mathematical Sciences) by Author "Dadedzi, Kenneth"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Analysis of tree spectra
    (Stellenbosch : Stellenbosch University, 2018-12) Dadedzi, Kenneth; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.
    ENGLISH ABSTRACT : We study the set of eigenvalues (spectrum) of the adjacency matrix, Laplacian matrix and the distance matrix of trees. In particular, we focus on the distribution of eigenvalues in the spectra of large random trees. The families of random trees considered in this work are simply generated trees and increasing trees. We prove that attaching several copies (two or more) of a tree H to vertices in a tree T “forces" certain real numbers into the adjacency, Laplacian or distance spectrum of the resulting tree. With this construction of forcing subtrees, we prove that the mean proportion of an eigenvalue α in the spectrum of a large random tree is at least the mean number of occurrences of a specific forcing subtree in the large random tree. This gives us explicit lower bounds on the asymptotic mean multiplicity of eigenvalues for different families of random trees. We prove that the mean proportion of an eigenvalue α in the spectrum of the adjacency matrix and Laplacian matrix of a large simply generated tree can be obtained by solving a system of functional equations. We provide an algorithm to solve this system numerically for a given eigenvalue. For instance, using this algorithm, we show that on average approximately 1.4%, 2.1%, 2.5% and 3.3% of the spectrum of a large pruned binary tree, labelled rooted tree, plane tree and pruned ternary tree respectively consist of the eigenvalue 1. Further, we provide explicit formulas for computing the mean proportion of the eigenvalue 0 in the spectrum of a large simply generated tree. We also study the spectra of recursive trees and binary increasing trees. We show that the distribution of the eigenvalue 0 (and other eigenvalues) in these random trees satisfies a central limit theorem. We also compute the mean and variance of the multiplicity of the eigenvalue 0 in the spectrum of a large recursive tree and binary increasing tree. The final chapter deals with related, but somewhat different questions. Given a rooted tree T with leaves v1, v2, . . . , vn, we define the ancestral matrix C(T) of T to be the n × n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of vi and vj . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C(T), and show that for dary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.