Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Question

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within the n-gon using each of the given lengths exactly once (and no vertex twice)?

Here the length of a directed diagonal within any kind of an n-gon is the number of sides of the n-gon between the starting and the end vertex counted in a fixed direction. A directed path is a sequence $(d_1,d_2,\ldots,d_t)$ of directed diagonals such that the end vertex of $d_i$ is the starting vertex of $d_{i+1}$ for $i=1,2,…,t-1$.

In number theory, it is equivalent to: For any subset $S=\{l_1,\ldots,l_t\}$ of $\{1,2,…,n-1\}$ with $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$ and $l_1+\cdots+l_t\neq 0 \pmod n$. Is there any a permutation of the elements of the subset $S$ such that no set of consecutive elements in this permutation has sum $=0 \pmod n$. Can anyone give me a counter-example or prove it?

In Graph theory, I can rephrase this question to: Let $\mathbb{Z}_n$ be a group of integers modulo $n$ and $S=\{l_1,\dots,l_t\}$ be a set of positive integers such that $1\le l_1<l_2< \dots < l_t \le n-1$, where $l_1+\dots + l_t \not\equiv 0 \pmod n$).

Let $P_t$ be a directed path of length $t$ ($t+1$ vertices). Can you label the vertices of the directed path $\overrightarrow{P_t}$ of length $t$ with distinct elements of $\mathbb{Z}_n$ such that the label differences on edges are exactly $S$? The difference is taking by subtract the head by the tail (then take mod $n$).

I have a proof for case $t\leq 6$. However, I wonder is it true or not in general. Many thanks.

Answer 1

I posed this problem at the 2007 CANADAM meeting in Banff after having discussed it privately with several mathematicians starting in about 2000. The problem arose for me because a positive answer would have considerably shortened the long proof of the main theorem in B. Alspach, H. Gavlas, M. Sajna and H. Verrall, Cycle Decompositions IV: complete directed graphs and fixed length directed cycles, JCT(A), 2003.

There has one paper published on the problem by H. Harborth in vol. 299 of Discrete Mathematics in 2005.

Doug Stinson, Jeff Dinitz and Dan Archdeacon recently started working onn the above problem and verified that holds for n up through something 26 (I don't recall precisely).

At the just concluded CANADAM 2015 in Saskatoon, Thomas Kalinowski and I posed the problem generalized to any Cayley digraph. That is, if one considers a connected Cayley digraph on a finite group G with connection set S, can one find either a directed path of length |S| or a directed cycle of length |S| such that each element of S generates an arc of the directed path or directed cycle.

Answer 2

For $t=n-1$ you are asking if the cyclic group of order $n$ is sequenceable, where a finite group $G$ is sequenceable if you can write down the non-identity elements $g_1,\ldots,g_{n-1}$ in such a way that the products $e,g_1,\,g_1g_2,\ldots,g_1g_2\cdots g_{n-1}$ are distinct. Gordon (Sequences in groups with distinct partial products, Pacific J. Math, 1961 ) proved that this is the case if and only if $n$ is even, which in your case follows from the assumption that the sum of the $l_i$ is nonzero.

For general $t$, your claim is that if $G$ is the circulant graph of order $n$ with connection set $S$ and the sum of the elements in $S$ is nonzero modulo $n$, then there is a simple path in $G$ using every element of $S$ exactly once. I think that this is an open problem.