Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.     

Avoiding Monotone Chains in Fillings of Layer Polyominoes

In this paper we give simple bijective proofs that the number of fillings of layer polyominoes with no northeast chains is the same as the number with no southeast chains. We consider 01-fillings and \({{\mathbb{N}}}\)-fillings and prove the results for both strong chains where the smallest rectangle containing the chain is also in the polyomino, and for regular chains where only the corners of the smallest rectangle containing the chain are required to be in the polyomino.     

The topology of ultrafilters as subspaces of 2

Using the property of being completely Baire, countable dense homogeneity and the perfect set property we will be able, under Martin?s Axiom for countable posets, to distinguish non-principal ultrafilters on ω up to homeomorphism. Here, we identify ultrafilters with subpaces of 2^ω in the obvious way. Using the same methods, still under Martin?s Axiom for countable posets, we will construct a non-principal ultrafilter such that is countable dense homogeneous. This consistently answers a question of Hrušák and Zamora Avilés. Finally, we will give some partial results about the relation of such topological properties with the combinatorial property of being a P-point.     

Asymptotics of q-plancherel measures

In this paper, we are interested in the asymptotic size of the rows and columns of a random Young diagram under a natural deformation of the Plancherel measure coming from Hecke algebras. The first lines of such diagrams are typically of order n, so it does not fit in the context of the work of Biane (Int Math Res Notices 4:179–192, 2001) and ?niady (Probab. Theory Relat Fields 136:263–297, 2006). Using the theory of polynomial functions on Young diagrams of Kerov and Olshanski, we are able to compute explicitly the first- and second-order asymptotics of the length of the first rows. Our method also works for other measures, for example those coming from Schur–Weyl representations.     

Young measures generated by a class of integrands: a narrow epicontinuity and applications to Homogenization

Given a subset E of convex functions from into which satisfy growth conditions of order p>1 and an open bounded subset of , we establish the continuity of a map μΦ_μ from the set of all Young measures on equipped with the narrow topology into a set of suitable functionals defined in and equipped with the topology of Γ-convergence. Some applications are given in the setting of periodic and stochastic homogenization.     

The number of convex polyominoes and the generating function of Jacobi polynomials

Lin and Chang gave a generating function of convex polyominoes with an m+1 by n+1 minimal bounding rectangle. Gessel showed that their result implies that the number of such polyominoes is

     

k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams

We study the distribution of k-crossings and k-nestings and other patterns in ordered graphs by using fillings of Ferrers diagrams. The main result states that there are as many graphs without k-crossings as without k-nestings. We also show that studying equirrestrictive patterns in ordered graphs is equivalent to studying equirrestrictive matrices in fillings of Ferrers diagrams.     

Patterns in Shi Tableaux and Dyck Paths

Order - Shi tableaux are special binary fillings of certain Young diagrams which arise in the study of Shi hyperplane arrangements related to classical root systems. For type A, the set $\mathcal...     

Row-Strict Quasisymmetric Schur Functions

Haglund, Luoto, Mason, and van Willigenburg introduced a basis for quasisymmetric functions, called the quasisymmetric Schur function basis, generated combinatorially through fillings of composition diagrams in much the same way as Schur functions are generated through reverse column-strict tableaux. We introduce a new basis for quasisymmetric functions, called the row-strict quasisymmetric Schur function basis, generated combinatorially through fillings of composition diagrams in much the same way as quasisymmetic Schur functions are generated through fillings of composition diagrams. We describe the relationship between this new basis and other known bases for quasisymmetric functions, as well as its relationship to Schur polynomials. We obtain a refinement of the omega transform operator as a result of these relationships.     

APPLICATION OF TWO OPERATORS TRANSFORM FROM CLASS A OPERATOR TO THE CLASS OF HYPONORMAL OPERATOR

In this article, we give an operator transform T (*) from class A operator to the class of hyponormal operators. It is different from the operator transform T defined by M. Ch and T. Yamazaki. Then, we show that σ(T ) = σ( T (*)) and σa(T )\{0} = σa( T (*))\{0}, in case T belongs to class A. Next, we obtain some relations between T and T (9).     

Adjacency of Young tableaux and the Springer fibers

We connect different results about irreducible components of the Springer fibers of type A. Firstly, we show a relation between the Spaltenstein partition of the fibers and a total order on the set of standard Young tableaux. Next, using a result of Steinberg, we connect a work of the first author to the Robinson–Schensted map. We also perform the Spaltenstein study of the relative position of the Springer fibers and -fibrations of the flag manifold. This leads us to consider the adjacency relation on the set of standard Young tableaux and to define oriented and labeled graphs with the standard Young tableaux as vertices. Using this adjacency relation, we describe some smooth irreducible components of the Springer fibers. Finally, we show that these graphs can be identified with some full subgraphs of the Bruhat graph.     

An n log n Algorithm for Online BDD Refinement

Binary decision diagrams are in widespread use in verification systems for the canonical representation of finite functions. Here we consider multivalued BDDs, which represent functions of the form : ^ν →  , where is a finite set of leaves. We study a rather natural online BDD refinement problem: a partition of the leaves of several shared BDDs is gradually refined, and the equivalence of the BDDs under the current partition must be maintained in a discriminator table. We show that it can be solved in O(n log n) time if n bounds both the size of the BDDs and the total size of update operations. Our algorithm is based on an understanding of BDDs as the fixed points of an operator that in each step splits and gathers nodes. We apply our algorithm to show that automata BDD-represented transition functions can be minimized in time O(n · log n), where n is the total number of BDD nodes representing the automaton. This result is not an instance of Hopcroft's classical minimization algorithm, which breaks down for BDD-represented automata because of the BDD path compression property.     

Evolutionary Pareto distributions

We consider here i.i.d. variables which are distributed according to a Pareto up to some point x₁ and a Pareto (with a different parameter) after this point. This model constitutes an approximation for estimating extreme tail probabilities, especially for financial or insurance data. We estimate the parameters by maximizing the likelihood of the sample, and investigate the rates of convergence and the asymptotic laws. We find here a problem which is very close to the change point question from the point of view of limits of experiments. Especially, the rates of convergence and the limiting law obtained here are the same as in a change point framework. Simulations are giving an illustration of the quality of the procedure.     

Additive spectrum compressors

Additive bijections , which compress the spectrum between two unital, standard operator algebras, are characterized. Applications to local approximate (anti)multiplications are also given.     

The index of nonmonic polynomials

We show that the index of nonmonic polynomials gives the same information on the ring of integers in a number field as monic polynomials. In particular, we generalize a result of M.-N. Gras by proving that almost all cyclic extensions of of prime degree cannot be generated by a (nonmonic) polynomial with index 1. More precisely, we prove that this index goes to infinity with the conductor.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

The completeness of the isomorphism relation for countable Boolean algebras

We show that the isomorphism relation for countable Boolean algebras is Borel complete, i.e., the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Boolean algebras. This implies that Ketonen's classification of countable Boolean algebras is optimal in the sense that the kind of objects used for the complete invariants cannot be improved in an essential way. We also give a stronger form of the Vaught conjecture for Boolean algebras which states that, for any complete first-order theory of Boolean algebras that has more than one countable model up to isomorphism, the class of countable models for the theory is Borel complete. The results are applied to settle many other classification problems related to countable Boolean algebras and separable Boolean spaces. In particular, we will show that the following equivalence relations are Borel complete: the translation equivalence between closed subsets of the Cantor space, the isomorphism relation between ideals of the countable atomless Boolean algebra, the conjugacy equivalence of the autohomeomorphisms of the Cantor space, etc. Another corollary of our results is the Borel completeness of the commutative AF -algebras, which in turn gives rise to similar results for Bratteli diagrams and dimension groups.

     

More on Weak α-Openness

In [6] the authors, introduced the notion of weak -openness and investigated its fundamental properties. In this paper we investigate some more properties of this type of openness. In this connection, we obtain a new decomposition of -openness and it is also shown that weakly -open bijections preserve clopen sets.