Talk information

Date: Sunday, July 7, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Sahar Diskin (Tel Aviv University)
Title: Hitting time of perfect matchings in product graphs

Abstract:

Given a graph $G=(V,E)$, the random graph process starts with $G(0)$ being the empty graph on $V$, and at each step $1 \leq i \leq |E|$ the graph $G(i)$ is obtained from $G(i-1)$ by adding uniformly at random a new edge from $E$. The hitting time of a monotone increasing (non-empty) graph property $P$ is then a random variable equal to the index $t$ for which $G(t)\in P$, but $G(t-1)\notin P$.

A classical result of Bollobás and Thomason shows that when $G$ is the complete graph, with high probability the hitting time of minimum degree one and the hitting time of perfect matching (a matching covering all but at most one vertex) are the same. Note that deterministically the hitting time for a perfect matching is at least the hitting time of minimum degree one. In 1990, Bollobás showed that the same holds when $G$ is the $d$-dimensional binary hypercube. In this talk, we extend this result to a wider family of Cartesian product graphs and develop several tools which may be of independent interest in a more general setting of the typical existence of perfect matchings in random (sub)graphs.

Joint work with Anna Geisler from TU Graz.