4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the point of the condition that the lengths don't add up to zero, when you have specified that they are all at least 1? $\endgroup$ – Gerry Myerson Jun 16 '15 at 2:51
  • $\begingroup$ If $t>n$, how will you avoid using vertices twice? $\endgroup$ – Gerry Myerson Jun 16 '15 at 2:53
  • 1
    $\begingroup$ The condition $1\leq l_1<l_2<\cdots<l_t\leq n-1$ implies t<n already. $\endgroup$ – Thomas Edison Jun 16 '15 at 2:58
  • 2
    $\begingroup$ Yes, after one reads that these "lengths" are defined as "the number of sides...". It's unfortunate that the 1st paragraph makes no sense until one has read the 2nd paragraph. $\endgroup$ – Gerry Myerson Jun 16 '15 at 2:59
  • 1
    $\begingroup$ lengths don't add up to zero (mod n). If sum = 0 (mod n), I have some counter-examples. $\endgroup$ – Thomas Edison Jun 16 '15 at 3:00
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Yes, there is a proof for $t=n-1$ and $t=n-2$. $\endgroup$ – Thomas Edison Jun 16 '15 at 9:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.