A self paired Hopf algebra on double posets and a Littlewood-Richardson rule

Let D be the set of isomorphism types of finite double partially ordered sets, that is sets endowed with two partial orders. On ZD we define a product and a coproduct, together with an internal product, that is, degree-preserving. With these operations ZD is a Hopf algebra. We define a symmetric bilinear form on this Hopf algebra: it counts the number of pictures (in the sense of Zelevinsky) between two double posets. This form is a Hopf pairing, which means that product and coproduct are adjoint each to another. The product and coproduct correspond respectively to disjoint union of posets and to a natural decomposition of a poset into order ideals. Restricting to special double posets (meaning that the second order is total), we obtain a notion equivalent to Stanley's labelled posets, and a Hopf subalgebra already considered by Blessenohl and Schocker. The mapping which maps each double poset onto the sum of the linear extensions of its first order, identified via its second (total) order with permutations, is a Hopf algebra homomorphism, which is isometric and preserves the internal product, onto the Hopf algebra of permutations, previously considered by the two authors. Finally, the scalar product between any special double poset and double posets naturally associated to integer partitions is described by an extension of the Littlewood-Richardson rule.     

有限交换环上的多项式置换群

1999年, Frisch描述了 Z/p2Z上多项式置换群的结构.2005年,张找到 Z/p2Z 上多项式函数与 Z/pZ 上多项式函数的3维向量之间的对应关系.本文首先证明在任意有限交换环 R 上, 多项式置换群同构于R［x］（作为 R 上多项式函数全体构成的 R 代数）的自同构群,然后用张所提出的对应对Frisch的描述给出一个新证明.     

Computational analysis of counter-based schemes for VLSI test pattern generation

The use of a binary counter as a mechanism for VLSI built-in test pattern generation is examined. Four different schemes are studied which are defined as partitioning problems on the rows of a binary matrix T. The goal in all problems is to minimize the maximum distance between the values of the binary patterns of any two rows of T, so that they can be generated by a counter in the minimum number of cycles. Although all schemes are NP-hard, an approximation algorithm is presented for the first scheme which guarantees solutions within 2·p from the optimal, where p is the prescribed number of partitions. The remaining problems are shown to be NP-complete even to be approximated within twice the optimal.     

Enumerating split-pair arrangements

An arrangement of the multi-set {1,1,2,2,…,n,n} is said to be “split-pair” if for all i<n, between the two occurrences of i there is exactly one i+1. We enumerate the number of split-pair arrangements and in particular show that the number of such arrangements is (−1)ⁿ⁺¹n²(²2n−1)B2n where Bi is the ith Bernoulli number.     

Forbidden patterns and shift systems

The scope of this paper is two-fold. First, to present to the researchers in combinatorics an interesting implementation of permutations avoiding generalized patterns in the framework of discrete-time dynamical systems. Indeed, the orbits generated by piecewise monotone maps on one-dimensional intervals have forbidden order patterns, i.e., order patterns that do not occur in any orbit. The allowed patterns are then those patterns avoiding the so-called forbidden root patterns and their shifted patterns. The second scope is to study forbidden patterns in shift systems, which are universal models in information theory, dynamical systems and stochastic processes. Due to its simple structure, shift systems are accessible to a more detailed analysis and, at the same time, exhibit all important properties of low-dimensional chaotic dynamical systems (e.g., sensitivity to initial conditions, strong mixing and a dense set of periodic points), allowing to export the results to other dynamical systems via order-isomorphisms.     

Universal cycles of -partitions of an -set

In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles. Universal cycles have been investigated for permutations, partitions, k-partitions and k-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n−1-partitions of an n-set when n is odd and conjectured that when n is even, they do not exist. Herein we prove Hurlbert’s conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for n≤13 and give a lower bound on the total number for all n. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.     

Minimal factorizations of permutations into star transpositions

We give a compact expression for the number of factorizations of any permutation into a minimal number of transpositions of the form . This generalizes earlier work of Pak in which substantial restrictions were placed on the permutation being factored. Our result exhibits an unexpected and simple symmetry of star factorizations that has yet to be explained in a satisfactory manner.     

On the number of factorizations of a full cycle

We give a new expression for the number of factorizations of a full cycle into an ordered product of permutations of specified cycle types. This is done through purely algebraic means, extending recent work of Biane. We deduce from our result a remarkable formula of Poulalhon and Schaeffer that was previously derived through an intricate combinatorial argument.