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

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
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
29
30
31
1
2
3
4
5
6
  1. 2021 (95)
    1. November (2)
    2. October (6)
    3. September (12)
    4. August (6)
    5. July (10)
    6. June (12)
    7. May (7)
    8. April (9)
    9. March (13)
    10. February (8)
    11. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)