hypercube


Weak saturation of the cube in the clique

Author(s): Morrison; Noel

\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}

Keywords: bootstrap percolation; hypercube; Weak saturation

Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

\begin{problem} Bound the extremal number of $C_{10}$ in the hypercube. \end{problem}

Keywords: cycles; extremal combinatorics; hypercube

Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

Author(s): Morrison; Noel

\begin{problem} Determine the smallest percolating set for the $4$-neighbour bootstrap process in the hypercube. \end{problem}

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

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

Keywords: cycles; hypercube; minimum saturation; saturation

Coloring squares of hypercubes ★★

Author(s): Wan

If $G$ is a simple graph, we let $G^{(2)}$ denote the simple graph with vertex set $V(G)$ and two vertices adjacent if they are distance $\le 2$ in $G$.

\begin{conjecture} $\chi(Q_d^{(2)}) = 2^{ \lfloor \log_2 d \rfloor + 1}$. \end{conjecture}

Keywords: coloring; hypercube

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

\begin{question} Does every \Def[matching]{matching} of \Def[hypercube]{hypercube} extend to a \Def[Hamiltonian cycle]{Hamiltonian path}? \end{question}

Keywords: Hamiltonian cycle; hypercube; matching

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane.

The $d$-dimensional (hyper)cube $Q_d$ is the graph whose vertices are all binary sequences of length $d$, and two of the sequences are adjacent in $Q_d$ if they differ in precisely one coordinate.

\begin{conjecture} $\displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32}$ \end{conjecture}

Keywords: crossing number; hypercube

Syndicate content