Saturation in the hypercube
Saturation in the hypercube

Alex Scott , Oxford University
Fine Hall 224
A subgraph of the ddimensional 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.