Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

Reverse mathematics and well-ordering principles: A pilot study

The larger project broached here is to look at the generally sentence “if X is well-ordered then f(X) is well-ordered”, where f is a standard proof-theoretic function from ordinals to ordinals. It has turned out that a statement of this form is often equivalent to the existence of countable coded ω-models for a particular theory T_f whose consistency can be proved by means of a cut elimination theorem in infinitary logic which crucially involves the function f. To illustrate this theme, we prove in this paper that the statement “if X is well-ordered then ε_X is well-ordered” is equivalent to . This was first proved by Marcone and Montalban [Alberto Marcone, Antonio Montalbán, The epsilon function for computability theorists, draft, 2007] using recursion-theoretic and combinatorial methods. The proof given here is principally proof-theoretic, the main techniques being Schütte’s method of proof search (deduction chains) [Kurt Schütte, Proof Theory, Springer-Verlag, Berlin, Heidelberg, 1977] and cut elimination for a (small) fragment of .     

The Reception of Frege''sBegriffsschrift

The topic of the paper is the public reception of Gottlob Frege's (1848–1925)Begriffsschriftright after its publication in 1879. According to a widespread conception, the reception of the book was “unfavorable” and even “tragic.” The aim of the paper is to correct this exaggerated and even false view. The arguments are based, above all, on the six journal reviews of Frege's book in 1879 and 1880, and on Leonhard Rabus's critical comment on it in his bookDie neuesten Bestrebungen auf dem Gebiete der Logik bei den Deutschen und die logische Frage(1880). The conclusion is that it is misleading to regard the reception of Frege's first work as unfair and hostile even though it is apparent thatsomereviewers of the book were rather poorly motivated to comment on theBegriffsschrift.Copyright 1998 Academic Press.Der Gegenstand dieses Beitrags ist die öffentliche Rezeption von Gottlob Freges (1848–1925)Begriffsschriftnach ihrer Publikation 1879. Nach einer weitverbreiteten Auffassung war die Rezeption “ungünstig,” sogar “tragisch.” Ziel des Beitrags ist es zu zeigen, dass solche Interpretationen überspannt, teilweise sogar falsch sind. Der Verfasser gründet seine Behauptung vor allem auf die Rezensionen, die in verschiedenen Zeitschriften in den Jahren 1879 und 1880 erschienen sind. Er benutzt auch den Kommentar von Leonhard RabusDie neuesten Bestrebungen auf dem Gebiete der Logik bei den Deutschen und Die logische Frage(1880). Die Untersuchung kommt zu dem Schluss, dass, obwohl offensichtlicheinigeRezensenten dem Buch eher ablehnend gegenüberstanden, es irreführend ist, von einer ungerechtfertigten oder abweisenden Rezeption der Fregeschen Begriffsschrift zu sprechenCopyright 1998 Academic Press.AMS subject classification: 00A30, 01A55, 03A05     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

A bijection proving orthogonality of the characters of Sn

Suppose ? and β are partitions of n. If ? ? β, a bijection is given between positive pairs of rim hook tableaux of the same shape λ and content β and ?, respectively, and negative pairs of rim hook tableaux of some other shape μ and content β and ?, respectively. If ? = β, the bijection is between positive pairs and either negative pairs or permutations of hooks. The bijection, in the latter case, is a generalization of the Schensted correspondence between pairs of standard tableaux and permutations. If the irreducible characters of S_n are interpreted combinatorially using the Murnaghan-Nakayama formula, these bijections prove

$\text{∑}\text{λ}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\rho }}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\beta }}\text{=δ}{}_{\mathrm{\rho \beta }}\text{1}{}^{\mathrm{j1}}\text{J1!2}{}^{\mathrm{j2}}\text{J2!…}$

where ? = 1^j12^j2….     

Noncommutative algebras related with Schubert calculus on Coxeter groups

For any finite Coxeter system (W,S) we construct a certain noncommutative algebra, the so-called bracket algebra, together with a family of commuting elements, the so-called Dunkl elements. The Dunkl elements conjecturally generate an algebra which is canonically isomorphic to the coinvariant algebra of the Coxeter group W. We prove this conjecture for classical Coxeter groups and I₂(m). We define a “quantization” and a multiparameter deformation of our construction and show that for Lie groups of classical type and G₂, the algebra generated by Dunkl’s elements in the quantized bracket algebra is canonically isomorphic to the small quantum cohomology ring of the corresponding flag variety, as described by B. Kim. For crystallographic Coxeter systems we define the so-called quantum Bruhat representation of the corresponding bracket algebra. We study in more detail the structure of the relations in B_n-, D_n- and G₂-bracket algebras, and as an application, discover a Pieri-type formula in the B_n-bracket algebra. As a corollary, we obtain a Pieri-type formula for multiplication of an arbitrary B_n-Schubert class by some special ones. Our Pieri-type formula is a generalization of Pieri’s formulas obtained by A. Lascoux and M.-P. Schützenberger for flag varieties of type A. We also introduce a super-version of the bracket algebra together with a family of pairwise anticommutative elements, the so-called flat connections with constant coefficients, which describes “a noncommutative differential geometry on a finite Coxeter group” in the sense of S. Majid.     

Skew domino Schensted correspondence and sign-imbalance

Using growth diagrams, we define a skew domino Schensted correspondence which is a domino analogue of the skew Robinson–Schensted correspondence due to Sagan and Stanley. The color-to-spin property of Shimozono and White is extended. As an application, we give a simple generating function for the weighted sum of skew domino tableaux, which is a generalization of Stanley’s sign-imbalance formula. The generating function gives a method to calculate the generalized sign-imbalance formula. We also extend Sjöstrand’s theorems on sign-imbalance of skew shapes.     

Schensted Algorithms for Dual Graded Graphs

This paper is a sequel to [3]. We keep the notation and terminology and extend the numbering of sections, propositions, and formulae of [3].The main result of this paper is a generalization of the Robinson-Schensted correspondence to the class of dual graded graphs introduced in [3], This class extends the class of Y-graphs, or differential posets [22], for which a generalized Schensted correspondence was constructed earlier in [2].The main construction leads to unified bijective proofs of various identities related to path counting, including those obtained in [3]. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.As particular cases of the general construction, we re-derive the classical algorithm of Robinson, Schensted, and Knuth [19, 12], the Sagan-Stanley [18], Sagan-Worley [16, 29] and Haiman's [11] algorithms and the author's algorithm for the Young-Fibonacci graph [2]. Some new applications are suggested.The rim hook correspondence of Stanton and White [23] and Viennot's bijection [28] are also special cases of the general construction of this paper.In [5], the results of this paper and the previous paper [3] were presented in a form of extended abstract.     

On the number of rim hook tableaux

A hooklength formula for the number of rim hook tableaux is used to obtain an inequality relating the number of rim hook tableaux of a given shape to the number of standard Young tableaux of the same shape. This provides an upper bound for a certain family of characters of the symmetric group. The analogues for shifted shapes and rooted trees are also given. Bibliography: 13 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 219–226. Partially supported by the NSF (DMS-9400914).     

Schubert functors and Schubert polynomials

We construct a family of functors assigning an R-module to a flag of R-modules, where R is a commutative ring. As particular instances, we get flagged Schur functors and Schubert functors, the latter family being indexed by permutations. We identify Schubert functors for vexillary permutations with some flagged Schur functors, thus establishing a functorial analogue of a theorem of Lascoux and Schützenberger from C. R. Acad. Sci. Paris Sér. I Math. 294 (1982) 447 and of Wachs from J. Combin. Theory Ser. A 40 (1985) 276. Over an infinite field, we study the trace of a Schubert module, which is a cyclic module over a Borel subgroup B, restricted to the maximal torus. The main result of the paper says that this trace is equal to the corresponding Schubert polynomial of Lascoux and Schützenberger (C. R. Acad. Sci. Paris Sér. I Math. 294 (1982) 447). We also investigate filtrations of B-modules associated with the Monk formula (Proc. London Math. Soc. 9 (1959) 253) and transition formula from Lett. Math. Phys. 10 (1985) 111.     

Probabilities in the (<Emphasis Type="Italic">k</Emphasis>, ℓ) hook

We consider particular (k, ℓ)-hook probability measures on the space of the infinite standard Young tableaux, and calculate the probability that the entry at the (1, 2) cell is odd. As n goes to infinity, this, approximately, is the corresponding probability on tableaux of size n in the (k, ℓ) hook. In few cases of small k and ℓ we find exact formulas for the corresponding numbers of such standard tableaux.     

k-Best Solutions under Distance Constraints in Valuated -Matroids

In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like “alignments,” “automatic speech recognition,” and “computer chess” people are interested to find thekbest solutions for somek ≥ 2. We demand that theksolutions obey certain distance constraints to avoid that thekalternatives are too similar. Several results for valuated -matroids are presented, some of them concerning time complexity of algorithms.     

The Potts model representation and a Robinson–Schensted correspondence for the partition algebra

We construct a correspondence between the set of partitions of a finite set M and the set of pairs of walks to the same vertex on a graph giving the Bratteli diagram of the partition algebra on M. This is the precise analogue of the correspondence between the set of permutations of a finite set and the set of pairs of Young tableaux of the same shape, called the Robinson–Schensted correspondence.     

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.     

Primitive elements of the Hopf algebras of tableaux

The character theory of symmetric groups, and the theory of symmetric functions, both make use of the combinatorics of Young tableaux, such as the Robinson–Schensted algorithm, Schützenberger’s “jeu de taquin”, and evacuation. In 1995 Poirier and the second author introduced some algebraic structures, different from the plactic monoid, which induce some products and coproducts of tableaux, with homomorphisms. Their starting point are the two dual Hopf algebras of permutations, introduced by the authors in 1995. In 2006 Aguiar and Sottile studied in more detail the Hopf algebra of permutations: among other things, they introduce a new basis, by Möbius inversion in the poset of weak order, that allows them to describe the primitive elements of the Hopf algebra of permutations. In the present Note, by a similar method, we determine the primitive elements of the Poirier–Reutenauer algebra of tableaux, using a partial order on tableaux defined by Taskin.     

An analogue of the Robinson–Schensted–Knuth correspondence and non-symmetric Cauchy kernels for truncated staircases

We prove a restriction of an analogue of the Robinson–Schensted–Knuth correspondence for semi-skyline augmented fillings, due to Mason, to multisets of cells of a staircase possibly truncated by a smaller staircase at the upper left end corner, or at the bottom right end corner. The restriction to be imposed on the pairs of semi-skyline augmented fillings is that the pair of shapes, rearrangements of each other, satisfies an inequality in the Bruhat order, w.r.t. the symmetric group, where one shape is bounded by the reverse of the other. For semi-standard Young tableaux the inequality means that the pair of their right keys is such that one key is bounded by the Schützenberger evacuation of the other. This bijection is then used to obtain an expansion formula of the non-symmetric Cauchy kernel, over staircases or truncated staircases, in the basis of Demazure characters of type $A$, and the basis of Demazure atoms. The expansion implies Lascoux expansion formula, when specialized to staircases or truncated staircases, and make explicit, in the latter, the Young tableaux in the Demazure crystal by interpreting Demazure operators via elementary bubble sorting operators acting on weak compositions.     

Twisted loop groups and their affine flag varieties

We develop a theory of affine flag varieties and of their Schubert varieties for reductive groups over a Laurent power series local field k((t)) with k a perfect field. This can be viewed as a generalization of the theory of affine flag varieties for loop groups to a “twisted case”; a consequence of our results is that our construction also includes the flag varieties for Kac–Moody Lie algebras of affine type. We also give a coherence conjecture on the dimensions of the spaces of global sections of the natural ample line bundles on the partial flag varieties attached to a fixed group over k((t)) and some applications to local models of Shimura varieties.     

Equidistribution of negative statistics and quotients of Coxeter groups of type B and D

We generalize some identities and q-identities previously known for the symmetric group to Coxeter groups of type B and D. The extended results include theorems of Foata and Schützenberger, Gessel, and Roselle on various distributions of statistics, like inversion number, major index, and descent number. In order to show our results we provide explicit characterizations of the systems of minimal coset representatives of Coxeter groups of type B and D.     

Moment methods in two point Padé approximation

In the separable Hilbert space (H, ·, ·) the following “operator moment problem” is solved: given a complex sequence (c_k)_{k ε Z} generated by a meromorphic function f, find T ε B(H) and u₀ ε H such that T^ku₀, u₀ = c_k (k ε Z). If the sequence (c_k)_{k ε Z} is “normal,” an adapted form of Vorobyev's method of moments yields a sequence of two point Padé approximants to f. A sufficient condition for convergence of this sequence of approximants is given.