Seminario Interdipartimentale di Algoritmica  

Monday, June 19, 2006, 12:00 noon Abstract
Hunting for Snakes in Hypercubes
Anil M. Shende, Roanoke College, USA

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

The problem of finding the length, denoted by s(d), of a longest  d-dimensional snake, that is, an induced path in a d-dimensional hypercubical, undirected graph was posed in 1958 in the context of coding theory and is still an open problem.  The length of a snake is by definition the number of edges in a snake.  The 2^d vertices of a d-dimensional hypercube can be uniquely labeled using d bits.  A snake of length k in this hypercube is a sequence of distinct labels (vertices) v_0, v_1, ..., v_k such that:

* for each i, 0 <= i < k, v_i and v_{i+1} differ in exactly one bit position, and

* for each i, j, 0 <= i, j <= k, if |i - j| > 1 then v_i and v_j differ in at least two bit positions.

Besides coding theory, the study of snakes has several applications including electronic combination locking schemes, cryptography etc.

s(d) is known only for d <= 7, and these results were obtained by exhaustive search -- clearly an intractable methodology for finding s(d) for higher values of d.  The difference in the best known estimates for upper and lower bounds on s(d) is exponential in d.  Thus, there is a need to find better approximations on s(d).

A study of known longest d-dimensional snakes for d<=7 suggests that every d-dimensional snake contains a (d-1)-dimensional maximal snake as its prefix.  Hence, it is useful to study maximal snakes.

In this talk, we will discuss the best known results on s(d) and the techniques used to obtain these results.  In particular, we will discuss some existence/non-existence results related to maximal snakes, and how the proofs for these results may be useful in improving the lower bound on s(d).