PIMS/SFU Discrete Math Seminar: Sam Johnson

Abstract: Given a set of directions S \\subseteq {0,1,-1}^2 \\setminus {(0,0)}, we wish to count the number of lattice walks of length n on S restricted to the quarter plane. For most sets S, this amountsto a full generation of all walks of length n, an intensive task for largevalues of n. We seek instead combinatorial proofs for experimentally known asymptotic estimates for these quantities, and exhibit a tight upper bound on the exponential growth for a large class of models.