Printable PDF
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

****************************