RUcore Resource Object
RUcore Resource Object
PDF-1(361.07 KB)
Uniform TitleRanks of random matrices and graphs
NameCostello, Kevin (author), Vu, Van (chair), Kahn, Jeffry (internal member), Saks, Michael (internal member), Szemeredi, Endre (internal member), Boros, Endre (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2007
Date Created2007
SubjectMathematics,
Random matrices,
Random graphs,
Graph theory
DescriptionLet Q_n be a random symmetric matrix whose entries on and above the main diagonal are independent random variables (e.g. the adjacency matrix of an Erdos-Renyi random graph). In this thesis we study the behavior of the rank of the matrix in terms of the probability distribution of the entries. One main result is that if the entries of the matrix are not too concentrated on any particular value, then the matrix will with high probability (probability tending to 1 as the size of the matrix tends to infinity) have full rank.
Other results concern the case where Q_n is sparse (each entry is 0 with high probability), and in particular on the adjacency matrix of sparse random graphs. In this case, we show that if the matrix is not too sparse than with high probability any dependency among the rows of Q_n will come from a dependency involving very few rows.
Other results concern the case where Q_n is sparse (each entry is 0 with high probability), and in particular on the adjacency matrix of sparse random graphs. In this case, we show that if the matrix is not too sparse than with high probability any dependency among the rows of Q_n will come from a dependency involving very few rows.
NotePh.D.
NoteIncludes bibliographical references (p. 64-65).
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.15810
LanguageEnglish
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization Name
RightsThe author owns the copyright to this work.
Statistical Profile