On Universal Cycles for new Classes of Combinatorial Structures
On Universal Cycles for new Classes of Combinatorial Structures
复制标题
新一类组合结构的通用循环
DOI：
--
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
A. Godbole
中科院分区：
文献类型：
--
作者：
Antonio Blanca;A. Godbole
通用周期（U-CYCLE）是组合对象集合的紧凑型清单，我们使用这些对象的自然编码来显示U-Cycles的存在，以集合子集，受限多层和晶格路径。对于子集，我们表明，如果我们让$ k $在非零长度间隔内变化，则存在$ n $ set的$ k $ -subsets的U周期。长度$（1+O（1））$$ n \选择$ [n] $的所有子集的$ k $，$ o（1）$ term $ k $。 - 在某些字母$ \ sigma上的所有$ n $ lengength单词都存在，其中包含$ r \ subset \ sigma中的所有字符。子集的链。
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.