Analysis of tree spectra
Date
2018-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING : Ons bestudeer die versameling van eiewaardes (spektrum) van die nodusmatriks, Laplace se matriks en die afstandmatriks van bome. In die besonder fokus ons op die verdeling van eiewaardes in die spektra van groot vir ’n gegewe eiewaarde. Byvoorbeeld kan ons met behulp van hierdie algoritme wys dat ’n gemiddeld van 1.4%, 2.1%, 2.5% en 3.3% van die spektrum van ’n groot gesnoeide binêre boom, gemerkte wortelboom, vlak boom en gesnoeide ternêre boom onderskeidelik uit die eiewaarde 1 bestaan. Verder gee ons eksplisiete formules vir die berekening van die gemiddelde proporsie van die eiewaarde 0 in die spektrum van ’n groot eenvoudig gegenereerde boom. Ons bestudeer ook die spektra van rekursiewe bome en binêre toenemende bome. Ons wys dat die verdeling van die eiewaarde 0 (en ander eiewaardes) in hierdie lukrake bome ’n sentrale limietstelling bevredig. Ons bereken ook die gemiddeld en die variansie van die veelvoudigheid van die eiewaarde 0 in die spektrum van ’n groot rekursiewe boom en binêre toenemende boom. Die laaste hoofstuk handel oor verwante, maar ietwat ander vrae. Gegewe ’n gewortelde boom T met blare v1, v2, . . . , vn, definieer ons die voorouermatriks C(T) van T as die n × n matriks waarvoor die inskrywing in die ide ry, j-de kolom die vlak (afstand vanaf die wortel) van die eerste gemene voorouer van vi en vj is. Ons bestudeer eienskappe van hierdie matriks, veral ten opsigte van sy spektrum: ons kry verskeie bo- en ondergrense vir die eiewaardes in terme van ander boomparameters. Ons vind ook ’n kombinatoriese interpretasie vir die koëffisiënte van die karakteristieke polinoom van C(T), en toon aan dat vir d-êre bome ’n spesifieke waarde van die karakteristieke polinoom onafhanklik is van die presiese vorm van die boom. lukrake bome. Die families van lukrake bome wat in hierdie werk beskou word, is eenvoudig gegenereerde bome en toenemende bome. Ons bewys dat ons ’n aantal kopieë (twee of meer) van ’n boom H aan noduse van ’n boom T kan aanheg om sekere reële getalle in die spektra van die nodusmatriks, Laplace se matriks en die afstandmatriks van die boom wat ontstaan te “forseer”. Met hierdie konstruksie van forserende deelbome bewys ons dat die gemiddelde proporsie van ’n eiewaarde α in die spektrum van ’n groot lukrake boom minstens die gemiddelde aantal kopieë van ’n spesifieke forserende deelboom in die groot lukrake boom is. Dit lewer eksplisiete ondergrense vir die asimptotiese gemiddelde veelvoudigheid van eiewaardes vir verskillende families van lukrake bome. Ons bewys dat die gemiddelde proporsie van ’n eiewaarde α in die spektrum van die nodusmatriks en Laplace se matriks van ’n groot eenvoudig gegenereerde boom verkry kan word deur ’n stelsel funksionele vergelykings op te los. Ons gee ’n algoritme om hierdie stelsel numeries op te los
AFRIKAANSE OPSOMMING : Ons bestudeer die versameling van eiewaardes (spektrum) van die nodusmatriks, Laplace se matriks en die afstandmatriks van bome. In die besonder fokus ons op die verdeling van eiewaardes in die spektra van groot vir ’n gegewe eiewaarde. Byvoorbeeld kan ons met behulp van hierdie algoritme wys dat ’n gemiddeld van 1.4%, 2.1%, 2.5% en 3.3% van die spektrum van ’n groot gesnoeide binêre boom, gemerkte wortelboom, vlak boom en gesnoeide ternêre boom onderskeidelik uit die eiewaarde 1 bestaan. Verder gee ons eksplisiete formules vir die berekening van die gemiddelde proporsie van die eiewaarde 0 in die spektrum van ’n groot eenvoudig gegenereerde boom. Ons bestudeer ook die spektra van rekursiewe bome en binêre toenemende bome. Ons wys dat die verdeling van die eiewaarde 0 (en ander eiewaardes) in hierdie lukrake bome ’n sentrale limietstelling bevredig. Ons bereken ook die gemiddeld en die variansie van die veelvoudigheid van die eiewaarde 0 in die spektrum van ’n groot rekursiewe boom en binêre toenemende boom. Die laaste hoofstuk handel oor verwante, maar ietwat ander vrae. Gegewe ’n gewortelde boom T met blare v1, v2, . . . , vn, definieer ons die voorouermatriks C(T) van T as die n × n matriks waarvoor die inskrywing in die ide ry, j-de kolom die vlak (afstand vanaf die wortel) van die eerste gemene voorouer van vi en vj is. Ons bestudeer eienskappe van hierdie matriks, veral ten opsigte van sy spektrum: ons kry verskeie bo- en ondergrense vir die eiewaardes in terme van ander boomparameters. Ons vind ook ’n kombinatoriese interpretasie vir die koëffisiënte van die karakteristieke polinoom van C(T), en toon aan dat vir d-êre bome ’n spesifieke waarde van die karakteristieke polinoom onafhanklik is van die presiese vorm van die boom. lukrake bome. Die families van lukrake bome wat in hierdie werk beskou word, is eenvoudig gegenereerde bome en toenemende bome. Ons bewys dat ons ’n aantal kopieë (twee of meer) van ’n boom H aan noduse van ’n boom T kan aanheg om sekere reële getalle in die spektra van die nodusmatriks, Laplace se matriks en die afstandmatriks van die boom wat ontstaan te “forseer”. Met hierdie konstruksie van forserende deelbome bewys ons dat die gemiddelde proporsie van ’n eiewaarde α in die spektrum van ’n groot lukrake boom minstens die gemiddelde aantal kopieë van ’n spesifieke forserende deelboom in die groot lukrake boom is. Dit lewer eksplisiete ondergrense vir die asimptotiese gemiddelde veelvoudigheid van eiewaardes vir verskillende families van lukrake bome. Ons bewys dat die gemiddelde proporsie van ’n eiewaarde α in die spektrum van die nodusmatriks en Laplace se matriks van ’n groot eenvoudig gegenereerde boom verkry kan word deur ’n stelsel funksionele vergelykings op te los. Ons gee ’n algoritme om hierdie stelsel numeries op te los
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Binary system (Mathematics), Eigenvalues, Laplacian matrices, Trees (Graph theory), UCTD, Tree spectra