Saturation in the Hypercube

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

The hypercube $Q_d$ has vertex set $\{0,1\}^d$ and an edge between binary strings differing in exactly one coordinate; $|E(Q_d)|=d2^{d-1}$. For finite simple graphs $G,H$, a spanning subgraph $F\subseteq G$ is $(G,H)$-saturated if it contains no subgraph isomorphic to $H$, while $F+e$ contains such a subgraph for every $e\in E(G)\setminus E(F)$. Define $\operatorname{sat}(G,H)=\min |E(F)|$ over these subgraphs. Copies need not be induced. Write $C_{2\ell}$ for the cycle of length $2\ell$.

Statement recorded in the supplied source.

Determine $\operatorname{sat}(Q_d,C_{2\ell})$ for integers $d\geq1$, $\ell\geq2$. Also improve the upper and lower asymptotic bounds on $\operatorname{sat}(Q_d,Q_m)$ for each fixed $m\geq2$ as $d\to\infty$ through $d\geq m$, and decide whether the limit \[\lim_{d\to\infty}\frac{\operatorname{sat}(Q_d,Q_m)}{2^d}\] exists for every such $m$. [S2]

Short English statement

Find the minimum number of hypercube edges needed for cycle saturation; also sharpen fixed-subcube saturation bounds and determine whether their normalization by the number of vertices converges.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3054 (OPG-60002). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Morrison, Natasha; Noel, Jonathan A.; Scott, Alex, Saturation in the Hypercube, Open Problem Garden, node 60002. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/saturation_in_the_hypercube.