Families of locally separated Hamilton paths.

Abstract: We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of <italic>n</italic> vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor. [ABSTRACT FROM AUTHOR]