Department of Mathematics,
University of California San Diego
****************************
Combinatorics Seminar
Kevin Costello
Graduate Student, UCSD
The rank of random graphs
Abstract:
The Erdos Renyi random graph G(n,p) is generated by independently and randomly choosing whether or not to draw an edge between each pair of points, with p being the probability the edge is included. We consider the adjacency matrix of this graph, or equivalently a random symmetric matrix where each entry above the diagonal is independently chosen to be either 1 (with probability p), or 0 (with probability 1-p). We are primarily interested in the following two questions: 1. Is this matrix likely to be nonsingular? 2. If the matrix is singular, how close will it be to full rank? I will discuss answers to both of these questions in the range 0.5 ln n/n
July 31, 2006
2:00 PM
AP&M 7321
****************************