Spring 2012 talk schedule
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
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.
If time allows, I will discuss few new methods developed in recent years, leading to the establishment of several old conjectures.