Tutte seminar - Nick Wormald

Friday, October 26, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Small subgraph conditioning, cycle factors, restricted permutations, and combs

Speaker: Nick Wormald
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Consider a uniformly random t-dimensional lattice walk taking only nonnegative steps in each dimension, starting at 0 and finishing at some point x=(x_1, ..., x_t). Suppose that k > 0 divides m = x_1 + 2x_2 + ... + tx_t. What is the probability that such a walk includes one lattice point from each one of the set of parallel hyperplanes {(r_1, ... , r_t): r_1 + 2r_2 + ... + tr_t = ik}, i = 1, ... , n/k? Equivalently, given a collection S of integers consisting of x_i distinguishable copies of i (i = 1, ..., t), what is the probability that the partial sums of a random permutation of S include all integers ik, i = 1, ..., n/k? 
Another question: does a random 3-regular graph on n vertices possess a.a.s. (asymptotically almost surely) a 2-factor with all cycles of length exactly k (where k divides n)? 
A third question involves the comb, which is a tree consisting of a path of length about sqrt(n) having a "tooth" of length sqrt(n) attached to each vertex of the path. Does a random graph G(n,p), with p > C log n, contain a.a.s. a spanning subgraph isomorphic to a comb? This was asked by Kahn in the 1990's as a representative difficult case of the question of the threshold of appearance of an arbitrary specified spanning tree. 
Small subgraph conditioning is the glue holding these questions together. It originated in a proof that random cubic graphs are hamiltonian, and slight modifications of this proof give us the answer the second question above, provided we have a good answer to (a suitably altered version of) the first question, for a suitable range of "large" (unbounded) k and t, and wide variety of points x. 
The requisite answer to the first question is obtained using a combination of analytic, probabilistic and combinatorial techniques. 

This talk describes joint work with Jeff Kahn and Eyal Lubetzky.