Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
The probability of a random induced subgraph being Hamiltonian
There are several results in extremal graph theory of the following flavour: if P is any "non-trivial" property that forces Hamiltonicity, then P actually forces Hamiltonicity in a "robust" sense. For example, a graph G with minimum degree n/2 must be Hamiltonian (by Dirac's theorem), and moreover must remain Hamiltonian after deleting each edge with probability as high as 1-log(n)/n (by a result of Krivelevich-Lee-Sudakov).
In a similar spirit, Erdos and Faudree conjectured that a 2n-vertex, (n+1)-regular, a random induced subgraph, sampled uniformly at random, is Hamiltonian, with positive probability. The conjecture indicates a rather curious phase shift, as a 2n-vertex, n-regular graph may have its random induced subgraph be Hamiltonian with probability as small as n^{-1/2}) (think K_{n,n}). We recently confirmed the Erdos-Faudree conjecture, and in this talk we'll discuss the proof, which requires no background in extremal nor random graph theory.
Many open questions remain, notably, we conjecture that a similar phase shift occurs infinitely often for regular Hamiltonian graphs at much lower densities.
Based on joint works with Nemanja Draganic and Peter Keevash.