Combinatorics Seminar - Kyle Luh

December 1, 2017
Thursday, December 7, 2017 - 10:20am to 11:15am
Cockins Hall 240
Kyle Luh

Title: Embedding Large Graphs in Random Graphs

SpeakerKyle Luh (Harvard University)

Abstract: In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 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 $p\gg (n^{-1}\log^{1/\Delta}n)^{2/(\Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. We will also 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}$ simultaneously.

Seminar URLhttps://u.osu.edu/probability/

S M T W T F S
 
 
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28