Abstract of Colloquium talk at Math Department of WVU, November 14, 1996

Professor Jerzy Wojciechowski

West Virginia University

Long Snakes in Powers of Complete Graphs

Let K_n^d be the cartesian product of d copies of the complete graph K_n, n>=2, d>=1. It will be convenient to think of the vertices of K_n^d to be the d-tuples of n-ary digits, i.e. the elements of the set {0,1,...,n-1}, with edges between any two d-tuples differing at exactly one coordinate. Let S(K_m^d) be the length of the longest snake (cycle without chords) in K_m^d.

The main result we present (conjectured by Abbott and Katchalski) states that for every m>=2 there is a positive constant L_m such that S(K_{mn}^d)>=L_m n^{d-1}S(K_m^{d-1}). As a corollary, we conclude that for any finite set P of primes there is a constant c=c(P)>0 such that S(K_n^d)>=cn^{d-1} for any n divisible by an element of P and any d>=1.