![](/files/happy5.png)
Saturation in the Hypercube
![$ 2\ell $](/files/tex/e6160c4357fdf2ec5854a3cc78837f8a67caa5c5.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
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:
![$ n\geq k\geq2 $](/files/tex/2c98217cff01e698152b010e543f1d6205061e34.png)
![$ \text{sat}(K_n,K_k) = \binom{n}{2} = \binom{n-k+2}{2} $](/files/tex/3969c93f396939121c20aecaab8f75fbcf3cdc46.png)
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
.
![$ \text{sat}(Q_d,Q_m) $](/files/tex/05c26151af3d29137e9b9533a2bc048784e23d03.png)
![$ m $](/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
The results of [MNS] show that for fixed
. Howver, the precise asymptotic behaviour of this quantity is unknown.
![$ m\geq 2 $](/files/tex/d74668d49fba7f84e59b3a357f56ee670c53e20d.png)
![$ \frac{\text{sat}(Q_d,Q_m)}{2^d} $](/files/tex/eb53275c9c76f8458388d0181627ec2921f45ea8.png)
![$ d\to \infty $](/files/tex/cf0c41dbf68b8be1494ee1f27412b835d1086de8.png)
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.