Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Electronic Theses and Dissertations bannerUC Riverside

Information Gathering on Bounded Degree Trees and Properties of Random Matrices

Creative Commons 'BY' version 4.0 license

In this thesis two questions are addressed. First is the question of the time complexity of an algorithm gathering information on a tree with unknown topology. The tree is known to have maximum depth $D$ and maximum degree $\Delta$. This has been an open problem since being asked by Chlamtac and Kutten in 1985. This thesis resolves the question with upper and lower bounds that are essentially tight. The second question this dissertation addresses is what proportion of graphs have a fixed type of spectrum. We show that at most a $2^{-c n^{3/2}}$ proportion of graphs on $n$ vertices have integral spectrum. This improves on previous results of Ahmadi, Alon, Blake, and Shparlinski, who in 2009 showed that the proportion of such graphs was exponentially small.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View