#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Friday, October 26, 2012 — 3:30 PM to 4:30 PM EDT

Speaker: | Nick Wormald |
---|---|

Affiliation: | University of Waterloo |

Room: | Mathematics & Computer Building (MC) 5158 |

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.

Location

MC - Mathematics & Computer Building

5158

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.