Saturation in the Hypercube

Recomm. for undergrads: no
Posted by: Jon Noel
on: September 20th, 2015

\begin{question} What is the saturation number of cycles of length $2\ell$ in the $d$-dimensional hypercube? \end{question}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

Let $G$ and $H$ be graphs. Say that a spanning subgraph $F$ of $G$ is \emph{$(G,H)$-saturated} if $F$ contains no copy of $H$ but $F+e$ contains a copy of $H$ for every edge $e\in E(G)\setminus E(F)$. Let $\text{sat}(G,H)$ denote the minimum number of edges in a $(G,H)$-saturated graph. Saturation was introduced by Erdős, Hajnal and Moon [EHM] who proved the following:

\begin{theorem}[Erdős, Hajnal and Moon] For $n\geq k\geq2$ we have $\text{sat}(K_n,K_k) = \binom{n}{2} = \binom{n-k+2}{2}$. \end{theorem}

Let $Q_d$ denote the $d$-dimensional hypercube. Saturation of $4$-cycles in the hypercube has been studied by Choi and Guan [CG] who proved that $\text{sat}(Q_d,C_4)\leq \left(\frac{1}{4} + o(1)\right)|E(Q_d)|$. This was drastically improved by Johnson and Pinto [JP] to $\text{sat}(Q_d,C_4) < 10\cdot 2^d$. 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 $Q_d$. This was first considered by Johnson and Pinto [JP] who proved that $\text{sat}(Q_d,Q_m) = o\left(|E(Q_d)|\right)$ for fixed $m$ and $d\to \infty$. This upper bound was improved to $(1+o(1))72m^2 2^d$ by Morrison, Noel and Scott [MNS]. The best known lower bound on $\text{sat}(Q_d,Q_m)$ for fixed $m$ and large $d$, also due to [MNS], is $(m-1-o(1))2^d$.

\begin{problem} Improve the upper and lower bounds on $\text{sat}(Q_d,Q_m)$ for fixed $m$ and large $d$. \end{problem}

The results of [MNS] show that $\text{sat}(Q_d,Q_m) = \Theta(2^d)$ for fixed $m$. Howver, the precise asymptotic behaviour of this quantity is unknown.

\begin{question}[Morrison, Noel and Scott] For fixed $m\geq 2$, is it true that $\frac{\text{sat}(Q_d,Q_m)}{2^d}$ converges as $d\to \infty$? \end{question}


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[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.