Saturation in the hypercube

Alex Scott , Oxford University
Fine Hall 224

A subgraph of the d-dimensional cube Qd is (Qd,Qm)-saturated if it does not contain a copy of Qm, but adding any missing edge creates a copy of Qm. The subgraph is weakly (Qd,Qm)-saturated if we can add the missing edges one at a time, creating a new copy of Qm at each step. Answering a question of Johnson and Pinto, we show that for every fixed m, the minimum number of edges in a (Qd,Qm)-saturated graph is \Theta(2^d). We also determine exactly the minimum number of edges in a weakly (Qd,Qm)-saturated subgraph of Qd, and raise some further questions. Joint work with Natasha Morrison and Jonathan Noel.