27 problems

The $n$-dimensional hypercube $Q_n$ has as vertices all subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise v…

Let $Q_n$ be the graph whose vertices are the subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise vertex-disj…

Strong non-automorphism conjecture. There are minimum zero forcing sets of $Q_d$ that are non-automorphic in a particularly strong sense.

Propagation-time interval conjecture. For every $d\geq 2$,

Hypercube $L^1$-congestion conjecture.

The $H_7$ minimum-congestion conjecture.

Hruska's hypercube congestion conjecture.

Erdős's conjecture. All even cycles $C_{2t}$ with $t\geq 3$ are $g$-degenerate.

Let $Q_n$ be a hypercube and let a 2-factor mean a spanning 2-regular subgraph of $Q_n$. A matching is a set of pairwise vertex-disjoint edges. Vandenbussche–West conjecture. Every…

Let $Q_n$ be the $n$-dimensional hypercube. A matching is a set of pairwise vertex-disjoint edges. Let $u,v\in Q_n$ be vertices of opposite parity, and let the C-conditions be the…

Let $Q_n$ be the $n$-dimensional hypercube. A maximal matching is a matching that cannot be enlarged by adding an edge. For a matching $M$ and a vertex $u$ covered by $M$, let…

Let $Q_n$ be the $n$-dimensional hypercube. A half-layer is the set of edges in one direction having a fixed parity, and an almost half-layer is a set of edges missing one edge fro…

Let $Q_n$ be the hypercube graph of dimension $n$, and let $\chi_2(Q_n)$ denote its distance-$2$ chromatic number. Wan's conjecture. For every positive integer $n$, … Wan's conject…

Shukla's conjecture. For $n\geq r+2$,

De Bruyn's gonality conjecture.

Let $\mathbb{I}_n$ denote the $n$-dimensional hypercube graph, and let $\mathcal{VR}(\mathbb{I}_n;r)$ be its Vietoris–Rips complex at scale $r$. Let the collapsibility number of a…

A symmetric chain decomposition (SCD) of the hypercube $Q_n$ is a partition of its vertices into symmetric chains, where a symmetric chain is a path $(x_k,x_{k+1},\ldots,x_{n-k})$…

Let $G_{k,2}$ be the bipartite graph with vertex classes $\binom{[n]}{k}$ and $\binom{[n]}{2}$, where a $k$-element set $S$ is adjacent to a 2-element set $T$ exactly when…

Consider a 2-colouring of the edges of an $n$-dimensional hypercube graph in which directly opposite edges have opposite colours. Norine's conjecture. There are two directly opposi…

Let $Q_n$ be the hypercube graph, let $C_{2l}$ be the cycle of length $2l$, and let $e(Q_n)$ denote the number of edges of $Q_n$. For a graph $G$, write ${\rm ex}(G,H)$ for the max…

Let $Q_n$ be the $n$-dimensional hypercube, let $\mathcal{S}=(a_1,\dots,a_n)$ be a signature of $Q_n$, and let ${\mathcal{E}(\mathcal{S})}$ be the edge slide graph induced by the s…

Let $Q_n$ be the $n$-dimensional hypercube, let $||Q_n||$ denote its number of edges, and let $\operatorname{ex}(Q_n,Q_2)$ be the maximum number of edges in a subgraph of $Q_n$ con…

Middle levels conjecture. There exists a Hamiltonian cycle in the graph induced by the vertices on levels $n$ and $n+1$ of the hypercube graph in $2n+1$ dimensions.

Let $Q_n$ be the $n$-dimensional hypercube, and let $Q_{n,[a,b]}$ denote the subgraph induced by the vertices whose levels lie in $[a,b]$. For integers $k\geq 1$ and…

Let $Q_n$ be the $n$-dimensional hypercube, and let $G$ be a quadrilateral-free subgraph of $Q_n$. Erdős's conjecture. As $n$ tends to infinity, $G$ has asymptotically at most half…