The Yale Combinatorics and Probability Seminar

The Yale Combinatorics and Probability Seminar will usually meet on Fridays at 2:00 in LOM 206. It is being organized by Dan Spielman and Van Vu. We expect to host a variety of lectures by faculty, graduate students, and visitors. This link will let you sign up for the mailing list.

Spring 2012 talk schedule

Friday, April 20
Alan Frieze (CMU): Some coloring problems on random graphs
- We will discuss some problems related to coloring the edges or vertices of a random graph. In particular we will discuss results on (i) the game chromatic number; (ii) existence of rainbow Hamilton cycles; (iii) rainbow connectivity. For the game chromatic number we consider the two player game where each player takes turns in coloring the vertices of a graph G from one of k colors. Both players must color a vertex with a color distinct from its neighbors. Player A tries to ensure that all vertices of G are colored and player B tries to ensure that at some point, there is a vertex that cannot be colored. The game chromatic number is the minimum number of colors needed so that A can be guaranteed to win. We show that the game chromatic number of a random graph is within a constant factor of the chromatic number, but this factor is greater than one.
  Joint work with Tom Bohman, Simi Haber, Mikhail Lavrov, Benny Sudakov.
  We next consider coloring the edges of a graph. A set of edges S is rainbow colored if each edge of S is differently colored.
  An edge-colored graph is rainbow connected if there is a rainbow path between each pair of vertices. The rainbow connectivity of a connected graph is the minimum number of colors needed to make it rainbow connected. We prove that at the connectivity threshold, the rainbow connectivity of G(n,p) is asymptotically equal to the maximum of the number of vertices of degree one and the diameter.
  Joint work with Charalampos Tsourakakis.
  We finally discuss the threshold for a randomly edge-colored random graph to have a rainbow Hamilton cycle. We prove that with (1+o(1)) n colors, we only need 1+o(1) times the number needed to ensure that G(n,p) is Hamiltonian.
  Joint work with Po Shen-Loh
Friday, April 13
Van Vu: Computing singular vectors with random noise
- Computing the first few singular vectors of a large matrix is an operation of great practical importance. For instance, it is at the core of PCA (principal component analysis), which is probably one of the first few things one might do when one has to study a large matrix.
  In this talk, I would like to raise the following question: How accurate is the result when the original matrix is slightly perturbed by random noise? There are some surprises here, and a considerable amount of open questions.
Friday, April 6
Mokshay Madiman: Log-concave distributions, why they are interesting, and some new ways of thinking about them.
- Log-concave probability measures arise in numerous settings in probability, statistics, applied mathematics, and engineering. They have been deeply studied, particularly by probabilists, convex geometers and functional analysts. After describing some motivations from different directions for studying these objects, I will describe a new way of looking at them using information theory. In particular, I will describe why log-concave distributions in high dimensions are effectively uniformly distributed on the "shell" between 2 nested convex bodies, and why the average information content per coordinate of a random vector from a log-concave distribution is almost the same as that of a matched Gaussian distribution. These facts also lead to new, interesting formulations of Bourgain's hyperplane conjecture. Time permitting, we will also discuss a reverse entropy power inequality for log-concave measures that generalizes V. Milman's reverse Brunn-Minkowski inequality. (The talk will be based on joint work with Sergey Bobkov.)
Friday, March 30
No Seminar.
Friday, March 23
Dan Spielman: Fitting a graph to vectors.
- We ask "What is the right graph to fit to a set of vectors?" We would like to associate one vertex with each vector, and choose the edges in a natural way. We propose one solution that provides good answers to standard Machine Learning problems such as classification and regression, that has interesting combinatorial properties, and that we can compute efficiently. Joint work with Jonathan Kelner and Samuel Daitch.
Friday, March 2
Andrew Barron: Fast Capacity-Achieving Codes for the Gaussian Noise Channel
- Coding for the additive Gaussian noise channel is a probabilistic counterpart to the combinatorial geometry problem of efficient packing of spheres in R^n. Shannon provided the optimal rates in 1948, initiating a path of many developments in the field, including empirically justified practical schemes in the 1990s that are an essential part of the cell phone revolution. But the proof of computationally feasible algorithms, reliable at all rates below Shannon capacity has been lacking for the ubiquitous Gaussian noise channel. The codes we develop here are sparse superposition codes based on a high-dimensional regression model, and they have fast encoders and decoders based on iterative regression fits. In this presentation theoretical demonstration of the desired statistical properties are provided. The error probability is shown to scale favorably with the size of the code, namely, the error probability is exponentially small for all communication rates below capacity. This work is joint with Yale students Antony Joseph and Sanghee Cho.
Friday, February 24
Gil Kalai: Threshold phenomena, discrete Fourier analysis, and isoperimetry
- One of the earliest observation by Erdos and Renyi was that certain graph properties exhibit a sharp threshold behavior for random graphs when the edge probability increases. Similar phenomenon is important in the study of percolation. Discrete Fourier analysis and discrete isoperimetric results lead to very general explanation of the sharp threshold phenomena. I will describe some results and some open problems, including a highly provocative conjecture of Jeff Kahn and me regarding the location of the threshold.
Friday, February 17
Van Vu: Problems and Results concerning random matrices
- I am going to give a brief overview on the main problems in the theory of random matrices, focusing on questions concerning limiting distributions of eigenvalues.
  If time allows, I will discuss few new methods developed in recent years, leading to the establishment of several old conjectures.
Friday, February 10
Dan Spielman: An introduction to what I do and why.