Overlap Cycles for Permutations: Necessary and Sufficient Conditions

Abstract

Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1992. They have been devel- oped by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is s-overlap cycles, which relax such a constraint. In this paper we study permutations and some closely related class of strings, namely juggling sequences and functions. We prove the existence of s-overlap cycles for these objects, as they do not always lend themselves to the universal cycle structure.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 19, 2013
Accession Number
ADA623587

Entities

People

  • Victoria Horan

Organizations

  • Air Force Research Laboratory

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Genetic Algorithms
  • Information Operations
  • Military Research
  • Permutations
  • Rotation
  • Sequences
  • Standards
  • Transitions

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space
  • Space - Space Objects