Restricted Symmetric Permutations

Pattern-avoiding involutions, which have received much enumerative attention, are pattern-avoiding permutations which are invariant under the natural action of a certain subgroup of D ₈, the symmetry group of a square. Three other nontrivial subgroups of D ₈ also have invariant permutations under this action. For each of these subgroups, we enumerate the set of permutations which are invariant under the action of the subgroup and which also avoid a given set of forbidden patterns. The sets of forbidden patterns we consider include all subsets of S ₃. For each subgroup we also give a bijection between the invariant permutations and certain symmetric signed permutations. Received September 14, 2006     

Serre's Condition Rℓ for Affine Semigroup Rings

In this note we characterize the affine semigroup rings K[S] over an arbitrary field K that satisfy condition R_? of Serre. Our characterization is in terms of the face lattice of the positive cone pos(S) of S. We start by reviewing some basic facts about the faces of pos(S) and consequences for the monomial primes of K[S]. After proving our characterization we turn our attention to the Rees algebras of a special class of monomial ideals in a polynomial ring over a field. In this special case, some of the characterizing criteria are always satisfied. We give examples of non-normal affine semigroup rings that satisfy R₂.     

3-Rewritable Nilpotent 2-Groups of Class 2#

ABSTRACT

Let n be an integer greater than 1. A group G is said to be n-rewritable (or a Q_n-group) if for every n elements x₁, x₂,…,x_n in G there exist distinct permutations σ and τ in S_n such that x_σ(1)x_{σ (2)} ??? x_σ(n) = x_τ(1)x_τ(2) ??? x_τ(n). In this paper, we characterize all 3-rewritable nilpotent 2-groups of class 2. Also we have found a bound for the nilpotency class of certain nilpotent 3-rewritable groups, and have shown that 3-rewritable groups satisfy a certain law.     

Refined Enumeration of Permutations Sorted with Two Stacks and a D 8-Symmetry

We study permutations that are sorted by operators of the form S ° α ° S, where S is the usual stack sorting operator introduced by Knuth and α is any D ₈-symmetry obtained by combining the classical reverse, complement, and inverse operations. Such permutations can be characterized by excluded (generalized) patterns. Some conjectures about the enumeration of these permutations, refined with numerous classical statistics, have been proposed by Claesson, Dukes, and Steingrímsson. We prove these conjectures, and enrich one of them with a few more statistics. The proofs mostly rely on generating trees techniques, and on a recent bijection of Giraudo between Baxter and twisted Baxter permutations.     

Random Walks with Stochastically Bounded Increments: Renewal Theory

Summary. This paper develops renewal theory for a rather general class of random walks S_N including linear submartingales with positive drift. The basic assumption on S_N is that their conditional increment distribution functions with respect to some filtration ?_? are bounded from above and below by integrable distribution functions. Under a further mean stability condition these random walks turn out to be natural candidates for satisfying Blackwell-type renewal theorems. In a companion paper [2], certain uniform lower and upper drift bounds for S_N, describing its average growth on finite remote time intervals, have been introduced and shown to be equal in case the afore-mentioned mean stability condition holds true. With the help of these bounds we give lower and upper estimates for H * U(B), where U denotes the renewal measure of S_N, H a suitable delay distribution and B a Borel subset of IR. This is then further utilized in combination with a coupling argument to prove the principal result, namely an extension of Blackwell's renewal theorem to random walks of the previous type whose conditional increment distribution additionally contain a subsequence with a common component in a certain sense. A number of examples are also presented.     

Linear operators preserving unitarily invariant norms of matrices

Let F _{m × n} be the set of all m × n matrices over the field F = C or R Denote by U_n (F) the group of all n × n unitary or orthogonal matrices according as F = C or F-R. A norm N() on F m ×n, is unitarily invariant if N(UAV) = N(A): for all A ∈ F _m×n U ∈ U _m (F). and V ∈ U_n (F). We characterize those linear operators T F _{m × n} → F _{m × n} which satisfy N (T(A)) = N(A)for all A ∈ F _{m × n}

for a given unitarily invariant norm N(). It is shown that the problem is equivalent to characterizing those operators which preserve certain subsets in F _{m × n} To develop the theory we prove some results concerning unitary operators on F _{m × n} which are of independent interest.     

Hecke Algebras of Group Extensions

Abstract

We describe the Hecke algebra ?(Γ,Γ₀) of a Hecke pair (Γ,Γ₀) in terms of the Hecke pair (N,Γ₀) where N is a normal subgroup of Γ containing Γ₀. To do this, we introduce twisted crossed products of unital *-algebras by semigroups. Then, provided a certain semigroup S ? Γ/N satisfies S ^?1 S = Γ/N, we show that ? (Γ,Γ₀) is the twisted crossed product of ? (N,Γ₀) by S. This generalizes a recent theorem of Laca and Larsen about Hecke algebras of semidirect products.     

Regular subsets of valued fields and Bhargava’s v-orderings

We generalize notions and results obtained by Amice for regular compact subsets S of a local field K and extended by Bhargava to general compact subsets of K. Considering any ultrametric valued field K and subsets S that are regular in a generalized sense (but not necessarily compact), we show that they still have strong properties such as having v-orderings ${\{a_n\}_{n\geq0}}$ which satisfy a generalized Legendre formula, which are very well ordered and well distributed sequences in the sense of Helsmoortel and which remain v-orderings when a finite number of the initial terms of the sequence are deleted.     

Garside Structures on Monoids with Quadratic Square-Free Relations

We show the intimate connection between various mathematical notions that are currently under active investigation: a class of Garside monoids, with a “nice” Garside element, certain monoids S with quadratic relations, whose monoidal algebra A = kSA= \textbf{k}S has a Frobenius Koszul dual A ^! with regular socle, the monoids of skew-polynomial type (or equivalently, binomial skew-polynomial rings) which were introduced and studied by the author and in 1995 provided a new class of Noetherian Artin-Schelter regular domains, and the square-free set-theoretic solutions of the Yang-Baxter equation. There is a beautiful symmetry in these objects due to their nice combinatorial and algebraic properties.     

Fibonacci Numbers, Reduced Decompositions, and 321/3412 Pattern Classes

We provide a bijection between the permutations in S _n that avoid 3412 and contain exactly one 321 pattern with the permutations in S _n+1 that avoid 321 and contain exactly one 3412 pattern. The enumeration of these classes is obtained from their classification via reduced decompositions. The results are extended to involutions in the above pattern classes using reduced decompositions reproducing a result of Egge.     

On Some Finite Dimensional Representations of Symplectic Reflection Algebras Associated to Wreath Products

Let Γ _N : = S _N  ? Γ ^N be the wreath product of Γ, a finite subgroup of SL(2,C), by the symmetric group of degree N. In this article we classify all the irreducible representations of S _N  ? Γ ^N that can be extended to a representation of the associated symplectic reflection algebra H _1,k,c (Γ _N ) (where k is a complex number and c a class function on the nontrivial elements of Γ) for nonzero values of k.     

Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating functionH(x) of all 1342-avoiding permutations of lengthnas well as anexactformula for their numberS_n(1342). While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of lengthnequals that of labeled plane trees of a certain type onnvertices recently enumerated by Cori, Jacquard, and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte (Can. J. Math.33(1963), 249–271). Moreover,H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Noonan and Zeilberger (Adv. Appl. Math.17(1996), 381–407). We also prove thatconverges to 8, so in particular, lim_n→∞(S_n(1342)/S_n(1234))=0.     

Conjugacy in Permutation Representations of the Symmetric Group

Although the conjugacy classes of the general linear group are known, it is not obvious (from the canonic form of matrices) that two permutation matrices are similar if and only if they are conjugate as permutations in the symmetric group, i.e., that conjugacy classes of S _n do not unite under the natural representation. We prove this fact, and give its application to the enumeration of fixed points under a natural action of S _n  × S _n . We also consider the permutation representations of S _n which arise from the action of S _n on ordered tuples and on unordered subsets, and classify which of them unite conjugacy classes and which do not.     

On generation of permutations through decomposition of symmetric groups into cosets

A hardware-oriented algorithm for generating permutations is presented that takes as a theoretic base an iterative decomposition of the symmetric groupS _n into cosets. It generates permutations in a new order. Simple ranking and unranking algorithms are given. The construction of a permutation generator is proposed which contains a cellular permutation network as a main component. The application of the permutation generator for solving a class of combinatorial problems on parallel computers is suggested.     

Level Structures on the Weierstrass Family of Cubics

Let W → 𝔸 ² be the universal Weierstrass family of cubic curves over ?. For each N ≥ 2, we construct surfaces parameterizing the three standard kinds of level N structures on the smooth fibers of W. We then complete these surfaces to finite covers of 𝔸 ². Since W → 𝔸 ² is the versal deformation space of a cusp singularity, these surfaces convey information about the level structure on any family of curves of genus g degenerating to a cuspidal curve. Our goal in this note is to determine for which values of N these surfaces are smooth over (0, 0). From a topological perspective, the results determine the homeomorphism type of certain branched covers of S ³ with monodromy in SL₂ (?/N).     

The Maximal Chains of the Extended Bruhat Orders on the  × -Orbits of an Infinite Renner Monoid

Let (, S) be a Coxeter system. For ?, δ ? {+, ?} we introduce and investigate combinatorially certain partial orders ≤ _?δ, called extended Bruhat orders, on a  × -set (N, C), which depends on , a subset N ? S, and a component C ? N. We determine the length of the maximal chains between two elements x, y ? (N, C), x ≤ _?δ y.

These posets generalize  equipped with its Bruhat order. They include the  × -orbits of the Renner monoids of reductive algebraic monoids and of some infinite-dimensional generalizations which are equipped with the partial orders obtained by the closure relations of the Bruhat and Birkhoff cells. They also include the  × -orbits of certain posets obtained by generalizing the closure relation of the Bruhat cells of the wonderful compactification.     

Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

PS_N is a fast forward permutation if for each m the computational complexity of evaluating P^m(x) is small independently of m and x. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in S_N is Θ(N) if one does not use queries of the form P^m(x), but is only Θ(1) if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form P^m(x) are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.     

Almost disjoint large subsets of semigroups

There are several notions of largeness in a semigroup S that originated in topological dynamics. Among these are thick, central, syndetic and piecewise syndetic. Of these, central sets are especially interesting because they are partition regular and are guaranteed to contain substantial combinatorial structure. It is known that in (N,+) any central set may be partitioned into infinitely many pairwise disjoint central sets. We extend this result to a large class of semigroups (including (N,+)) by showing that if S is a semigroup in this class which has cardinality κ then any central set can be partitioned into κ many pairwise disjoint central sets. We also show that for this same class of semigroups, if there exists a collection of μ almost disjoint subsets of any member S, then any central subset of S contains a collection of μ almost disjoint central sets. The same statement applies if “central” is replaced by “thick”; and in the case that the semigroup is left cancellative, “central” may be replaced by “piecewise syndetic”. The situation with respect to syndetic sets is much more restrictive. For example, there does not exist an uncountable collection of almost disjoint syndetic subsets of N. We investigate the extent to which syndetic sets can be split into disjoint syndetic sets.     

A FORMALISM FOR SOME CLASS OF FORCING NOTIONS

We introduce a class of forcing notions, called forcing notions of type S, which contains among other Sacks forcing, Prikry-Silver forcing and their iterations and products with countable supports. We construct and investigate some formalism suitable for this forcing notions, which allows all standard tricks for iterations or products with countable supports of Sacks forcing. On the other hand it does not involve internal combinatorial structure of conditions of iterations or products. We prove that the class of forcing notions of type S is closed under products and certain iterations with countable supports.