Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

"Embedding Large Graphs in Random Graphs"

Location: 
Date & time: Monday, 03 April 2017 at 2:00PM - 3:00PM

 

Kyle Luh, Yale University

"Embedding Large Graphs in Random Graphs"
Time: 2:00 PM
Location: Hill 705
Abstract: In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let \(Deltageq 5\), \(varepsilon > 0\) and let \(H\) be a graph on \((1-varepsilon)n\) vertices and with maximum degree \(Delta\). We show that a random graph \(G_{n,p}\) with high probability contains a copy of \(H\), provided that \(pgg (n^{-1}log^{1/Delta}n)^{2/(Delta+1)}\). Our assumption on \(p\) is optimal up to the \(polylog\) factor. Time permitting, we will discuss recent progress on the "universality" problem, which entails finding the threshold for all graphs of degree at most \(Delta\) to appear in \(G_{n,p}\) emph{simultaneously}.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.