##### 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

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