DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Matthew Russell, Rutgers University, russell2 {at} math [dot] rutgers [dot] edu)

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title:Lower Bound Expansions for Random Bernoulli Matrices

Speaker: Stephen DeSalvo, UCLA

Date: Thursday, March 24, 2016 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A random Bernoulli matrix is an n by n matrix with each entry chosen as +/-1 with probability 1/2, independently of other entries. It was first shown by Komlos that the probability that a random Bernoulli matrix is singular tends to 0 as n tends to infinity, and later by Kahn, Komlos, and Szemeredi that the rate is exponentially decaying. The rate was later improved by Tau and Vu, and most recently by Bourgain, Vu, and Wood. We present a lower bound asymptotic expansion, conjecturally a true asymptotic expansion, by classifying the various ways in which the matrix can be singular, indexed by what we call novel integer partitions. We show that the set of novel integer partitions is both necessary and sufficient for classifying singularities, and classify all novel integer partitions with at most seven parts. This is joint work with Richard Arratia.

See: http://www.math.rutgers.edu/~russell2/expmath/