|
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.
|