Abstract:

Let G be graph, and let G_{1/2} be a random subgraph of G. If G_{1/2} is easy to color, must G be easy to color as well? In this talk, we examine this question both for arbitrary coloring and for greedy colorings. Joint work with Bhargav Narayanan and Michael Krivelevich.

Bio:

I am a Professor of Mathematics at Carnegie Mellon University. Previously, I was a Research Fellow at University of Cambridge and Churchill College, a graduate student at Princeton University under the guidance of Benny Sudakov and an undergraduate student at University of California, Berkeley, and at City College of San Francisco.

I enjoy mathematics for the ideas, pure and simple. All of mathematics is beautiful. The skeptics, who think otherwise, should check out the explanation why mathematics is natural and especially the article by Paul Lockhart on the topic.

Organizer: 马杰