Thursday, April 6th, 2015 | 4pm-5pm | Burnside 1205 |

University of Oxford

Saturation in the Hypercube

Let $Q_d$ denote the hypercube of dimension $d$. Given $d\geq m$, a spanning subgraph $G$ of $Q_d$ is said to be \emph{$(Q_d,Q_m)$-saturated} if it does not contain $Q_m$ as a subgraph but adding any edge of $E(Q_d)\setminus E(G)$ creates a copy of $Q_m$ in $G$. We say $G$ is \emph{weakly $(Q_d,Q_m)$-saturated} if the edges of $E(Q_d)\setminus E(G)$ can be added to $G$ one at a time so that each additional edge creates a new copy of $Q_m$. In this talk we answer two questions of Johnson and Pinto. First we show that for fixed $m\geq2$ the minimum number of edges in a $(Q_d,Q_m)$-saturated graph is $\Theta(2^d)$. We also determine the minimum number of edges in a weakly $(Q_d,Q_m)$-saturated graph for all $d\geq m\geq1$. Joint work with Alex Scott and Jonathan Noel.