This part deals with questions on random matrices with combinatorial nature. Here are a few examples:

(1) What is the probability that a random sign matrix is singular ?

(2) Show that a random sign matrix has a real eigenvalue, with high probability.

(3) Show that the adjacency matrix of a random regular graph with degree at least 3 is non-singular with probability tending to one, as the number of vertices tends to infinity.

For many more questions and results, see this survey.

Representative publications:

(1) T. Tao and V. Vu, On the singular probability of random Bernoulli matrices, JAMS.

The probability (call it p_n)  in question is conjectured to be (1/2+ o(1))^n, roughly the probability that there are two equal rows (or columns), perhaps the most notorious problem in the field.  Already in the 1960s, Komlos showed that it is o(1), and later improved it to O(n^{-1/2}).  In mid 1990s, the Rutgers team of Kahn, Komlos and Szemeredi obtained the first exponential bound .999^n. Here, Tao and I improved the bound to (3/4+o(1))^n. The main idea being an Inverse Theorem of Freiman type. (See Additive Combinatorics). The bound is improved later to (1/2 +o(1))^{n/2} by Bourgain, Wood and myself, but the Inverse Theorem remains the same and plays a crucial role.

(2) K. Costello, T.Tao and V. Vu, Random symmetric matrices are almost surely singular, Duke Math.

Here we prove that the singular probability of a random symmetric Bernoulli matrix tends to zero as the size of the matrix tends to infinity, solving an open question posed by B. Weiss in the 1980s. This result can be seen as the symmetric version of Komlos 1960s result mentioned above, but due to symmetry, it is much harder to prove. The core of the proof is a quadratic Littlewood-Offord type theorem, which is interesting in itself (see, for instance,  this recent paper of Razborov and Viola for an application in computer science).

I conjectured that the singularity probability is also (1/2+o(1))^n as in the non-symmetric case. We are very still far from there, although considerable progresses have been made recently by H. Nguyen and R. Vershynin.

(3) T. Tao and V. Vu, On the permanent of random Bernoulli matrices, Adv Math.

We showed that the permanent of a random matrix of size n is typically of order n^{1/2n }. Prior to this result, it was not known whether the permanent is typically non-zero.