printable pdf
比利时vs摩洛哥足彩 ,
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

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