Rutgers Discrete Math Seminar Fall 2009

of the eigenvalues. In the 1950s, Wigner proved his famous semi-cirle law (subsequently extended by Anord, Pastur and others), which established the global distribution of the eigenvalues of random Hermitian matrices.
In the last fifty years or so, the focus of the theory has been on the local distributions, such as the distribution of the gaps between consecutive eigenvalues, the k-point correlations, the local fluctuation of a particular eigenvalue, or the distribution of the least singular value. Many of these problems have connections to other fields of mathematics, such as combinatorics, number theory, statistics and numerical linear algebra.
Most of the local statistics can be computed explicitly for random matrices with gaussian entries (GUE or GOE), thanks to Ginibre's formulae of the joint density of eigenvalues. It has been conjectured that these results can be extended to other models of random matrices. This is generally known as the Universality phenomenon, with several specific conjectures posed by Wigner, Dyson, Mehta etc.
In this talk, we would like to discuss recent progresses concerning the Universality phenomenon, focusing on a recent result (obtained jointly with T. Tao), which asserts that all local statistics of eigenvalues of a random matrix are determined by the first four moments of the entries. This (combining with results of Johansson, Erdos-Ramirez-Schlein-Yau and many others) provides answers to several old problems.

matrices (both symmetric and non-symmetric models). There will be many open questions. The topics include:
(1) The singularity problem: How often is a random matrix singular ?
(2) The determinant problem: How large is the typical determinant of a random matrix ? How is it distributed ?
(3) The permanent problem: How large is the typical permanent of a random matrix and how often is it equal zero ?
(4) The eigenvector problems: How does a typical eigenvector look like ?
(5) The permanent estimating problem: One can use a random determinant to estimate the permanent of a deterministic matrix. How accurate is this estimator ?

about the structure and properties of H. Unfortunately, results of that kind do not seem to be true if we replace the minor containment by induced subgraph containment. One of the few conjectures about general behavior of graphs with certian induced subgraphs forbidden is the Erdos Hajnal Conjecture. It states that for every fixed graph H there exists a constant δ(H), such that if a graph G has no iduced subgraph isomorphic to H, then G contains a big clique or a big stable set of size |V(G)|^δ(H).
The Erdos Hajal Conjecture is known to be true for graphs H on at most four vertices, but there are some five-vertex graphs for which the conjecture is still open. One of such graphs is a path of length four (edges). We prove that if a graph G does not contain as induced subgraphs a path of length four or the complement of a path of length five, then G contains a clique or a stable set of size |V(G)|^(1/6).
This is joint work with Yori Zwols.

defined by certain combinatorial structures. Inspired by the similarity of the definitions of L_p norms, trace norms, and Gowers norms, we introduce and study a wide class of norms containing these, as well as many other norms. It will be proven that every norm in this class must satisfy a Cauchy-Schwarz-Gowers type inequality. I will show an application of this inequality to a conjecture of Sidorenko about subgraph densities.

normal form. Let G(k,n) be the number of k-SAT functions of n variables. We show that G(3,n) is asymptotic to 2^{n + {n \choose 3}}, a strong form of a conjecture of Bollobas, Brightwell and Leader. (Joint with Jeff Kahn)

certain conjectures of Hardy and Littlewood concerning the number of primes vectors p = (p_1,...,p_n) in some box which satisfy the equation Ap = b. The number of such solutions should be determined, asymptotically, by "local" considerations and our aim is to prove this provided that A is "nondegenerate" (which, sadly, means we do not propose to resolve the twin prime or Goldbach conjectures).
In 2006 we reduced this task to that of proving two families of conjectures. We established the first of these in 2007, leaving the task of proving the second family of conjectures, known as the "inverse conjectures for the Gowers norms". There is one of these for each of the so-called Gowers norms U^2,U^3,U^4,... The inverse conjecture for the U^2 norm can be proved by about one line of harmonic analysis, and the inverse conjecture for the U^3 norm was proved in a 70-page paper of Tao and I. Recently, with Tammy Ziegler, we appear to have established the general case, although we have only worked out and written up all the details in the case of the U^4 norm. The paper handling this case is a mere 40 pages long, and I propose to talk about some aspects of this result.
I shall not dwell on details of the proof, being more concerned with giving an overview of the area. I will not assume that the audience knows much (anything) about the subject at all (for example, I shall not be assuming the definition of Gowers norm).

contains a line in every direction. In this talk I will present a recent result which gives a lower bound of (q/2)^n on the size of such sets. This bound is tight to within a multiplicative factor of two from the known upper bounds. The proof extends the polyomial methods used in [Dvir 08, Saraf Sudan 08] and uses polynomials of unbounded degree. This new bound can be used to derive new results on randomness mergers and extractors which are of interest in computational complexity.
In the talk I will show the proof of the improved Kakeya bound and discuss the applications/connections to computer science.
Based on Joint work with S. Kopparty, S. Saraf and M. Sudan.

The concentration probability P(V) of V is defined as P(V):=sup_v P(eta_1 v_1+..+eta_n v_n = v). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then the concentration probability of V is O(n^{-1/2}).
In the reverse direction, Tao and Vu proved that any set of large concentration probability must have structure. In this talk, we will provide a general approach that gives an almost best possible characterization for all such V. This allows us to recover several previous forward Littlewood-Offord results, including a significant result of Stanley from the 1980s on the optimal value of P(V) when v_i are distinct.
(Joint with Van Vu, Rutgers University)

and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least Omega_d(sqrt{n}(log n)^{d/2-1}) and at most O_d(sqrt{n}(log n)^{d/2-1} loglog n).