Graduate Students
Graduate Programs     
Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students

Apply Now
Graduate Seminar

Lisa Espig
Carnegie Mellon University
Title: Threshold for Zebraic Hamilton Cycles in Random Graphs

Abstract: When studying random graphs, we often want to know the threshold for the emergence of a particular structure. In other words, in the Erd\"os-R\'enyi random graph model $G_{n,p}$ - where we consider a graph on $n$ vertices with each edge appearing randomly with probability $p$, how large must $p$ be in order to guarantee certain structures appear in the graph with high probability? Say a perfect matching, or a Hamilton cycle? This and other thresholds are well-studied. I'll talk a bit about this and the general 'anatomy of random graphs.' Then we will find the threshold for a different kind of structure, involving random graphs with edge colorings. Namely, we will find the threshold for which a randomly 2-colored random graph contains a zebraic Hamilton cycle - one whose edges alternate between the two colors, black and white (hence the silly name).

Date: Thursday, March 28, 2013
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Brian Kell