• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

On Universal Cycles for New Classes of Combinatorial Structures

Blanca, Antonio, Godbole, Anant P. 01 December 2011 (has links)
A universal cycle (u-cycle) is a compact listing of a collection of combinatorial objects. In this paper, we use natural encodings of these objects to show the existence of u-cycles for collections of subsets, restricted multisets, and lattice paths. For subsets, we show that a u-cycle exists for the κ-subsets of an n-set if we let κ vary in a non zero length interval. We use this result to construct a "covering" of length (1+o(1))(n/κ) for all subsets of [n] of size exactly κ with a specific formula for the o(1) term. We also show that u-cycles exist for all n-length words over some alphabet ∑, which contain all characters from R ⊂ ∑. Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.

Page generated in 0.0171 seconds