Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

Model theoretic connected components of groups

We give a general exposition of model theoretic connected components of groups. We show that if a group G has NIP, then there exists the smallest invariant (over some small set) subgroup of G with bounded index (Theorem 5.3). This result extends a theorem of Shelah from [21]. We consider also in this context the multiplicative and the additive groups of some rings (including infinite fields).     

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     

Pattern avoidance and Boolean elements in the Bruhat order on involutions

We show that the principal order ideal of an element w in the Bruhat order on involutions in a symmetric group is a Boolean lattice if and only if w avoids the patterns 4321, 45312 and 456123. Similar criteria for signed permutations are also stated. Involutions with this property are enumerated with respect to natural statistics. In this context, a bijective correspondence with certain Motzkin paths is demonstrated. This article is largely based on results from the second author’s M.Sc. thesis [15].     

On covers of cyclic acts over monoids

In (Bull. Lond. Math. Soc. 33:385–390, 2001) Bican, Bashir and Enochs finally solved a long standing conjecture in module theory that all modules over a unitary ring have a flat cover. The only substantial work on covers of acts over monoids seems to be that of Isbell (Semigroup Forum 2:95–118, 1971), Fountain (Proc. Edinb. Math. Soc. (2) 20:87–93, 1976) and Kilp (Semigroup Forum 53:225–229, 1996) who only consider projective covers. To our knowledge the situation for flat covers of acts has not been addressed and this paper is an attempt to initiate such a study. We consider almost exclusively covers of cyclic acts and restrict our attention to strongly flat and condition (P) covers. We give a necessary and sufficient condition for the existence of such covers and for a monoid to have the property that all its cyclic right acts have a strongly flat cover (resp. (P)-cover). We give numerous classes of monoids that satisfy these conditions and we also show that there are monoids that do not satisfy this condition in the strongly flat case. We give a new necessary and sufficient condition for a cyclic act to have a projective cover and provide a new proof of one of Isbell’s classic results concerning projective covers. We show also that condition (P) covers are not unique, unlike the situation for projective covers.     

APN permutations on and Costas arrays

We study PN and APN functions over the integers modulo n. We give some construction techniques based on Costas arrays, which allow us to construct APN permutations on where p is a prime. Although PN permutations do not exist, one set of our functions is very close to being a set of PN permutations.     

A Kuran Type Regularity Criterion for Sub-Laplacians

The aim of this paper is to show the strong connection between regularity of bounded open set boundary points and quasi-boundedness, on the same set, of the fundamental solution of stratified Lie group sub-Laplacians. In the euclidean case the theorem was proved by Kuran (J Lond Math Soc 2(19):301–311, 1979). We later give two examples using some direct consequences of main theorem.     

Labeled partitions with colored permutations

In this paper, we extend the notion of labeled partitions with ordinary permutations to colored permutations. We use this structure to derive the generating function of the indices of colored permutations. We further give a combinatorial treatment of a relation on the q-derangement numbers with respect to colored permutations. Based on labeled partitions, we provide an involution that implies the generating function formula due to Gessel and Simon for signed q-counting of the major indices. This involution can be extended to signed permutations. This gives a combinatorial interpretation of a formula of Adin, Gessel and Roichman.     

Rough Sets Determined by Quasiorders

In this paper, the ordered set of rough sets determined by a quasiorder relation R is investigated. We prove that this ordered set is a complete, completely distributive lattice. We show that on this lattice can be defined three different kinds of complementation operations, and we describe its completely join-irreducible and its completely meet-irreducible elements. We also characterize the case in which this lattice is a Stone lattice. Our results generalize some results of J. Pomykała and J. A. Pomykała (Bull Pol Acad Sci, Math, 36:495–512, 1988) and M. Gehrke and E. Walker (Bull Pol Acad Sci, Math, 40:235–245, 1992) in case R is an equivalence.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

The structure of popular difference sets

We show that the set of popular differences of a large subset of ℤ _N does not always contain the complete difference set of another large set. For this purpose we construct a so-called niveau set, which was first introduced by Ruzsa in [Ruz87] and later used in [Ruz91] to show that there exists a large subset of ℤ _N whose sumset does not contain any long arithmetic progressions. In this paper we make substantial use of measure concentration results on the multi-dimensional torus and Esseen’s Inequality.     

Detection of slightly expressed changes in random environment

Consider a regular parametric family of distributions F(·, θ). The classical change point problem deals with observations corresponding to θ = 0 before a point of change, and θ = μ after that. We substitute the latter constant μ by a set of random variables θ _i,n called a random environment assuming that E[θ _i,n ] = μ _n → 0. The random environment can be independent or obtained by random permutations of a given set. We define the rates of convergence and give the conditions under which the classical parametric change point algorithms apply.     

On Extremal Permutations AvoidingωN = NN − 1 . . . 1

Dedicated to the memory of Marcel–Paul Schützenberger Cet article présente une étude des permutations qui évitent le motif de la permutation maximaleω_N = NN − 1 . . . 1. Après avoir donné les définitions classiques, nous montrons que l’ensemble de ces permutations est un idéal pour l’ordre de Bruhat faible et faisons l’étude de ses éléments maximaux. Nous exhibons alors un algorithme pour calculer ces éléments et nous montrons que ceux-ci peuvent être obtenus à partir d’un automate. Nous terminons en donnant des estimations asymptotiques de leur nombre. This paper presents a study of permutations avoiding the patternω_N = NN − 1 . . . 1. After recalling the basic definitions, we prove that this set of permutations is an ideal for the weak Bruhat order and begin the study of its maximal elements. We then present an algorithm that generates these elements and find out that they can be obtained from an automaton. Finally, we give some asymptotics about their number.     

A Little More on Coz-Unique Frames

Coz-unique frames were defined and characterized by Banaschewski and Gilmour (J Pure Appl Algebra 157:1–22, 2001). In this note we give further characterizations of these frames along the lines of characterizations of absolutely z-embedded spaces obtained by Blair and Hager (Math Z 136:41–52, 1974) on the one hand, and by Hager and Johnson (Canad J Math 20:389–393, 1968) on the other. We also extend to frames certain characterizations of z-embedded spaces; namely, we give a characterization of coz-onto frame homomorphisms in terms of normal covers.      

Comparing Algorithms for Sorting with <Emphasis Type="Italic">t</Emphasis> Stacks in Series

We show that the left-greedy algorithm is a better algorithm than the right-greedy algorithm for sorting permutations using t stacks in series when t > 1. We also supply a method for constructing some permutations that can be sorted by t stacks in series and from this get a lower bound on the number of permutations of length n that are sortable by t stacks in series. Finally we show that the left-greedy algorithm is neither optimal nor defines a closed class of permutations for t > 2.AMS Subject Classification: 05A05, 68R05, 68W01.     

Coherent random permutations with biased record statistics

We consider random permutations that are defined coherently for all values of n, and for each n have a probability distribution which is conditionally uniform given the set of upper and lower record values. Our central example is a two-parameter family of random permutations that are conditionally uniform given the counts of upper and lower records. This family may be seen as an interpolation between two versions of Ewens’ distribution. We discuss characterisations of the conditionally uniform permutations, their asymptotic properties, constructions and relations to random compositions.     

Adaptive learning and <Emphasis Type="Italic">p</Emphasis>-best response sets

A product set of strategies is a p-best response set if for each agent it contains all best responses to any distribution placing at least probability p on his opponents’ profiles belonging to the product set. A p-best response set is minimal if it does not properly contain another p-best response set. We study a perturbed joint fictitious play process with bounded memory and sample and a perturbed independent fictitious play process as in Young (Econometrica 61:57–84, 1993). We show that in n-person games only strategies contained in the unique minimal p-best response set can be selected in the long run by both types of processes provided that the rate of perturbations and p are sufficiently low. For each process, an explicit bound of p is given and we analyze how this critical value evolves when n increases. Our results are robust to the degree of incompleteness of sampling relative to memory.     

Uniform Convergence of Schr?dinger Cocycles over Simple Toeplitz Subshift

For locally constant cocycles defined on an aperiodic subshift, Damanik and Lenz (Duke Math J 133(1): 95–123, 2006) proved that if the subshift satisfies a certain condition (B), then the cocycle is uniform. In this paper, we study simple Toeplitz subshifts. We give a criterion that simple Toeplitz subshifts satisfy condition (B), and also give some sufficient conditions that they do not satisfy condition (B). However, we can still prove the uniformity of Schr?dinger cocycles over any simple Toeplitz subshift. As a consequence, the related Schr?dinger operators have Cantor spectrum of Lebesgue measure 0. We also exhibit a fine structure for the spectrum, and this helps us to prove purely singular continuous spectrum for a large class of simple Toeplitz potentials.