


Let and
be graphs. Say that a spanning subgraph
of
is
-saturated if
contains no copy of
but
contains a copy of
for every edge
. Let
denote the minimum number of edges in a
-saturated graph. Saturation was introduced by Erdős, Hajnal and Moon [EHM] who proved the following:


Let denote the
-dimensional hypercube. Saturation of
-cycles in the hypercube has been studied by Choi and Guan [CG] who proved that
. This was drastically improved by Johnson and Pinto [JP] to
. The saturation number for longer cycles in the hypercube is not known, though. The question above addresses this.
Another open problem is to determine the saturation number of sub-hypercubes in . This was first considered by Johnson and Pinto [JP] who proved that
for fixed
and
. This upper bound was improved to
by Morrison, Noel and Scott [MNS]. The best known lower bound on
for fixed
and large
, also due to [MNS], is
.



The results of [MNS] show that for fixed
. Howver, the precise asymptotic behaviour of this quantity is unknown.



Bibliography
[CG] S. Choi and P. Guan, Minimum critical squarefree subgraph of a hypercube, Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 189, 2008, pp. 57–64.
[EHM] P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107–1110.
[JP] J. R. Johnson and T. Pinto, Saturated subgraphs of the hypercube, arXiv:1406.1766v1, preprint, June 2014.
[MNS] N. Morrison, J. A. Noel and A. Scott, Saturation in the Hypercube and Bootstrap Percolation, arXiv:1408.5488v2, June 2015.
* indicates original appearance(s) of problem.