Name
Abstract | ||
|---|---|---|
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 $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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1137/100805674 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
combinatorial structures,length word,specific formula,restricted multisets,proper chain,zero length interval,new classes,compact listing,combinatorial object,universal cycles,lattice path,natural encodings,sperner family,subset | Discrete mathematics,Combinatorics,Lattice (order),Multiset,Lattice path,Sigma,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
25 | 4 | 0895-4801 |
Citations | PageRank | References |
5 | 0.56 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antonio Blanca | 1 | 14 | 9.74 |
| Anant P. Godbole | 2 | 95 | 16.08 |