22 problems

Shen–Williams' conjecture. For every $\alpha\geq 1$ and $k\geq 2$, all $\alpha^k$-multiset permutations can be generated by star transpositions; equivalently, $G(\alpha^k)$ has a H…

Binary STGC conjecture. Binary STGCs of length $p$ and period $2^p-2$ can be obtained by using the paper's theorem on single necklaces and its theorem on self-dual STGCs.

Slater's conjecture. No $P_n$-compatible complete binary Gray code exists for $n\geqslant 7$.

Slater's conjecture. No complete skew-tolerant ($\overline{P_n}$-compatible) Gray code exists for $n\geqslant 7$.

Let $m$ and $k$ be positive integers. An $(m,k)$-Ucycle is an $m$-distinguishable sequence in which no $m$-window repeats an element and every $m$-subset of $[k]$ occurs exactly on…

Let $m$ and $k$ be positive integers. An $(m,k)$-Mcycle is a cyclic $m$-distinguishable sequence on $[k]$ in which every $m$-multiset of $[k]$ appears exactly once; it therefore ha…

Let $I_n^D$ denote the involutions in the type-D signed permutation group, and let $G({\mathcal S}_n^B,X_1^D\cup X_2^D)$ be the Cayley graph with generating sets … … Consider the r…

Let $\mathcal{W}_{q,n}$ denote the set of restricted binary words of length $n$ associated with the positive rational parameter $q$. A 1-Gray code is an arrangement of all words in…

Hamilton-connectedness conjecture. For every $\alpha\geq 2$, the graph $G(\alpha,\alpha,1)$ is Hamilton-connected.

Hamilton-1-laceability conjecture. For every integer partition $\ba=(a_1,\ldots,a_k)$ with $\Delta(\ba)=0$, the graph $G(\ba)$ is Hamilton-1-laceable, unless $\ba=(2,2)$.

Let $n\geq 0$ and $q\geq 1$, and let $\mathcal{W}^q_n$ denote the set of Fibonacci $q$-decreasing words of length $n$. A 1-Gray code for $\mathcal{W}^q_n$ is an ordering of its wor…

Let $n\geq 1$, let $N=\binom{2(n+1)}{n+1}$, and consider a cyclic star-transposition ordering of all $(n+1,n+1)$-combinations, with flip sequence $\alpha$ recording the position sw…

Let $n\geq 1$. Consider all binary strings of length $2(n+1)$ containing exactly $n+1$ zeros and $n+1$ ones. Middle levels conjecture. These strings can be ordered cyclically so th…

Middle levels conjecture. All $(2k,k)$-combinations can be generated with only exchanges of the form $1\leftrightarrow i$.

Hierarchical-counter lower-bound conjecture. There is no space-optimal hierarchical counter over $\mathbb{Z}_{m_1}\times \mathbb{Z}_{m_2}\times \mathbb{Z}_{m_3}$ unless $m_2$ and…

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 $S_{2m+2}$ be the symmetric group on $2m+2$ elements, and let a Kendall snake be a single-error-detecting rank-modulation Gray code under the Kendall $tau$-metric. Holroyd's co…

An $(1,2,n;2)$-LRMGC is a constant-weight $(1,2,n)$-LRM Gray code whose codewords all have weight $2$. The $(1,2,n;2)$-LRMGC upper-bound conjecture. Every such code has at most…

Middle levels conjecture. The middle layer graph has a Hamilton cycle for every $n\geq 1$.

4-adjacent Gray code conjecture. The resulting list is a $4$-adjacent Gray code.

Minimal-weight Hamiltonian path conjecture. The Hamiltonian path $\mathbf{w}_n$ in $G_n$ has minimal total weight.