Tuesday March 26, 2019 at 2:30 p.m.

Thesis Title: Variations on the Matching Problem

Student: David Judkovich

Abstract

We consider two extensions of the matching problem of classical combinatorial probability. We first consider the number of approximate matches in a randomly chosen permutation; an element is called an approximate match if it is within $c$ of its original position. We also consider the distribution of the number of $k$-cycles of a random permutation and, more generally, a permutation conditioned to only contain cycles of length not exceeding $r$. In both cases we prove that the distributions are approximately Poisson under suitable conditions and obtain bounds on the total variation distance between the distributions and their respective Poisson limiting distributions. The main technical tool used is Stein’s method of exchangeable pairs.