Weak saturation of the cube in the clique

 Importance: Low ✭
 Author(s): Morrison, Natasha Noel, Jonathan A.
 Subject: Graph Theory » Extremal Graph Theory
 Keywords: bootstrap percolation hypercube Weak saturation
 Posted by: Jon Noel on: April 6th, 2016

\begin{problem} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Determine $\text{wsat}(K_n,Q_3)$. \end{problem}

% 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]{http://www.research.att.com/~njas/sequences/}

Given graphs $G$ and $H$, let $\text{wsat}(G,H)$ denote the minimum number of edges in a subgraph $F$ of $G$ such that the edges of $E(G)\setminus E(F)$ can be added to $F$, one edge at a time, so that each edge completes a copy of $H$ when it is added.

Of course, if one can solve the problem above, then a natural next step is to determine $\text{wsat}(K_n,Q_m)$ for all $n$ and $m$.

Morrison, Noel and Scott [MNS] solved the related problem of determining $\text{wsat}(Q_d,Q_m)$ for all $d$ and $m$.

Bibliography

% 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)

[MNS] N. Morrison, J. A. Noel, A. Scott. Saturation in the hypercube and bootstrap percolation. To appear in Combin. Probab. Comput.

* indicates original appearance(s) of problem.