Department of Mathematics,
University of California San Diego
****************************
Math 262 - Reading in Combinatorics
Kevin Costello and Prof. Van Vu
UCSD
Singularity of random matrices
Abstract:
Let $M_n$ be a random matrix whose entries are i.i.d Bernoulli random variables and $Q_n$ be a random symmetric matrix whose upper diagonal entries are i.i.d Bernoulli random variables. We prove: \vskip .1in \noindent 1. P ($Q_n$ is singular)$= 0$($n^{-1/8+ \epsilon }$) (Costello, Tao and Vu). \vskip .1in \noindent 2. P($M_n$ is singular)$=0$ (($3/4$)$^n$) (Tao and Vu). \vskip .1in \noindent The first result answers a question of B. Weiss, posed in the early 1990s. The second improved an earlier bound ($.999^n$) of Kahn, Komlos and Szemeredi from 1995. \vskip .1in \noindent From 2:00 p.m. to 2:30 p.m., Costello will talk about ($1$). Vu will continue from 3 p.m. to 3:30 p.m. with the beginning of the proof of ($2$). The rest of the proof comes next week.
Host:
May 24, 2005
2:00 PM
AP&M 6218
****************************