On Universal Cycles for new Classes of Combinatorial Structures

Details On Universal Cycles for new Classes of Combinatorial Structures On Universal Cycles for new Classes of Combinatorial Structures

2010-08-13

arxiv.org/abs/1008.2251v1

Mathematics

Combinatorics

Scientific paper

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, matroids, restricted multisets, chains of subsets, multichains, and lattice paths. For subsets, we show that a u-cycle exists for the $k$-subsets of an $n$-set if we let $k$ vary in a non zero length interval. We use this result to construct a "covering" of length $(1+o(1))$$n \choose k$ for all subsets of $[n]$ of size exactly $k$ with a specific formula for the $o(1)$ term. We also show that u-cycles exist for all $n$-length words over some alphabet $\Sigma,$ which contain all characters from $R \subset \Sigma.$ Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.

Affiliated with

Also associated with

No associations

Rating

On Universal Cycles for new Classes of Combinatorial Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Universal Cycles for new Classes of Combinatorial Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Universal Cycles for new Classes of Combinatorial Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502948