Atlantic Graph Theory Seminar: Calum MacRury, University of Toronto

The semi-random graph process is an example of an adaptive process for constructing a graph in which random edges are added step by step.  It is adaptive in that there is an online algorithm which has partial control over which random edges are added. Through intelligent decision-making, the objective of the algorithm is to force the graph to satisfy a fixed graph property with high probability in as few rounds as possible. We first provide upper and lower bounds on the performance of an optimal algorithm when the property corresponds to being Hamiltonian or to containing a perfect matching. This part of the talk is based on joint works with Pawel Pralat and Jane Gao.

Afterwards, we introduce a formal definition of an adaptive random graph process which generalizes both the semi-random graph process, as well as the Achlioptas process. In this model, we define a condition called edge-replaceability  which we prove is sufficient for a property to have a sharp threshold. Intuitively, a property has a sharp threshold if the optimal algorithm’s “success probability” transitions from almost $0$ to almost $1$ in a negligible number of steps.  We apply our result to the semi-random graph process to show that the properties of being Hamiltonian  and of containing a perfect matching each have a sharp threshold. This part of the talk is based on a joint work with Erlang Surya.