A Symmetry Theorem on a Modified Jeu De Taquin

For their bijective proof of the hook-length formula for the number of standard tableaux of a fixed shape Novelli et al. define a modified jeu de taquin which transforms an arbitrary filling of the Ferrers diagram with 1, 2, , n(tabloid) into a standard tableau. Their definition relies on a total order of the cells in the Ferrers diagram induced by a special standard tableau, however, this definition also makes sense for the total order induced by any other standard tableau. Given two standard tableaux P, Q of the same shape we show that the number of tabloids which result in P if we perform the modified jeu de taquin with respect to the total order induced by Q is equal to the number of tabloids which result in Q if we perform the modified jeu de taquin with respect to P. This symmetry theorem extends to skew shapes and shifted skew shapes.     

Sliding Presentation of the Jeux de Taquin for Classical Lie Groups

The simple \(GL(n,\mathbb {C})\)-modules are described by using semistandard Young tableaux. Any semistandard skew tableau can be transformed into a well defined semistandard tableau by a combinatorial operation, the Schützenberger jeu de taquin. Associated to the classical Lie groups \(SP(2n,\mathbb {C})\), \(SO(2n+1,\mathbb {C})\), there are other notions of semistandard Young tableaux and jeux de taquin. In this paper, we study these various jeux de taquin, proving that each of them has a simple and explicit formulation as a step-by-step sliding. Any of these jeux de taquin is the restriction of the orthogonal one, associated to \(SO(2n+1,\mathbb {C})\).     

A symplectic jeu de taquin bijection between the tableaux of King and of De Concini

The definitions, methods, and results are entirely combinatorial. The symplectic jeu de taquin algorithm developed here is an extension of Schützenberger's original jeu de taquin and acts on a skew form of De Concini's symplectic standard tableaux. This algorithm is used to construct a weight preserving bijection between the two most widely known sets of symplectic tableaux. Anticipated applications to Knuth relations and to decomposing symplectic tensor products are indicated.

     

Increasing Tableaux,Narayana Numbers and an Instance of the Cyclic Sieving Phenomenon

We give a counting formula for the set of rectangular increasing tableaux in terms of generalized Narayana numbers. We define small m–Schröder paths and give a bijection between the set of increasing rectangular tableaux and small m–Schröder paths, generalizing a result of Pechenik [4]. Using K–jeu de taquin promotion, we give a cyclic sieving phenomenon for the set of increasing hook tableaux.     

Shifted tableaux,schur Q-functions,and a conjecture of R. Stanley

We present an analog of the Robinson-Schensted correspondence that applies to shifted Young tableaux and is considerably simpler than the one proposed in [B. E. Sagan, J. Combin. Theory Ser. A 27 (1979), 10–18]. In addition, this algorithm enjoys many of the important properties of the original Robinson-Schensted map including an interpretation of row lengths in terms of k-increasing sequences, a jeu de taquin, and a generalization to tableaux with repeated entries analogous to Knuth's construction (Pacific J. Math. 34 (1970), 709–727). The fact that the Knuth relations hold for our algorithm yields a simple proof of a conjecture of Stanley.     

Graphs of order two less than the Moore bound

The problem of determining the largest order n_d,k of a graph of maximum degree at most d and diameter at most k is well known as the degree/diameter problem. It is known that n_d,k?M_d,k where M_d,k is the Moore bound. For d=4, the current best upper bound for n_4,k is M_4,k-1. In this paper we study properties of graphs of order M_d,k-2 and we give a new upper bound for n_4,k for k?3.     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

Growth diagrams for the Schubert multiplication

We present a partial generalization of the classical Littlewood-Richardson rule (in its version based on Schützenberger's jeu de taquin) to Schubert calculus on flag varieties. More precisely, we describe certain structure constants expressing the product of a Schubert and a Schur polynomial. We use a generalization of Fomin's growth diagrams (for chains in Young's lattice of partitions) to chains of permutations in the so-called k-Bruhat order. Our work is based on the recent thesis of Beligan, in which he generalizes the classical plactic structure on words to chains in certain intervals in k-Bruhat order. Potential applications of our work include the generalization of the S₃-symmetric Littlewood-Richardson rule due to Thomas and Yong, which is based on Fomin's growth diagrams.     

Irreducibility of Hurwitz spaces of coverings with one special fiber

Let Y be a smooth, projective complex curve of genus g ? 1. Let d be an integer ? 3, let e = {e₁, e₂,..., e_r} be a partition of d and let |e| = Σ_i=1^r(e_i − 1). In this paper we study the Hurwitz spaces which parametrize coverings of degree d of Y branched in n points of which n − 1 are points of simple ramification and one is a special point whose local monodromy has cyclic type e and furthermore the coverings have full monodromy group S_d. We prove the irreducibility of these Hurwitz spaces when n − 1 + |e| ? 2d, thus generalizing a result of Graber, Harris and Starr [A note on Hurwitz schemes of covers of a positive genus curve, Preprint, math. AG/0205056].     

An explicit bijection between semistandard tableaux and non-elliptic sl 3 webs

The sl ₃ spider is a diagrammatic category used to study the representation theory of the quantum group U _q (sl ₃). The morphisms in this category are generated by a basis of non-elliptic webs. Khovanov–Kuperberg observe that non-elliptic webs are indexed by semistandard Young tableaux. They establish this bijection via a recursive growth algorithm. Recently, Tymoczko gave a simple version of this bijection in the case that the tableaux are standard and used it to study rotation and join of webs. This article builds on Tymoczko’s bijection to give a simple and explicit algorithm for constructing all non-elliptic sl ₃ webs. As an application, we generalize results of Petersen–Pylyavskyy–Rhoades and Tymoczko proving that, for all non-elliptic sl ₃ webs, rotation corresponds to jeu de taquin promotion and join corresponds to shuffling.     

Lusztig Data of Kashiwara-Nakashima Tableaux in Type D

We describe the embedding from the crystal of Kashiwara-Nakashima tableaux in type D of an arbitrary shape into that of i-Lusztig data associated to a family of reduced expressions i which are compatible with the maximal Levi subalgebra of type A. The embedding is described explicitly in terms of well-known combinatorics of type A including the Schützenberger’s jeu de taquin and an analog of RSK algorithm.

     

Tableau stabilization and rectangular tableaux fixed by promotion powers

Journal of Algebraic Combinatorics - We introduce tableau stabilization, a new phenomenon and statistic on Young tableaux based on jeu de taquin. We investigate bounds for tableau stabilization,...     

Puzzles,tableaux, and mosaics

We define mosaics, which are naturally in bijection with Knutson-Tao puzzles. We define an operation on mosaics, which shows they are also in bijection with Littlewood-Richardson skew-tableaux. Another consequence of this construction is that we obtain bijective proofs of commutativity and associativity for the ring structures defined either of these objects. In particular, we obtain a new, easy proof of the Littlewood-Richardson rule. Finally we discuss how our operation is related to other known constructions, particularly jeu de taquin.     

Linear spaces with small generated subspaces

The dimension of a linear space is the maximum positive integer d such that any d of its points generate a proper subspace. Given n, d, s, we consider linear spaces on n points such that any d points generate subspaces of size at most s. Certain design-theoretic constructions and applications are investigated. In particular, one consequence is the existence of proper n-edge-colourings of both Kn+1 (for n odd) and Kn,n with a constant bound on the length of two-colored cycles.     

Gibbs rapidly samples colorings of G(n, d/n)

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s–Rényi random graph G(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n, d/n) is d(1?o(1)), it contains many nodes of degree of order (log n) / (log log n). The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n, d/n) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n ^{1+Ω(1 / log log} n) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work we consider sampling q-colorings and show that for every d < ∞ there exists q(d) < ∞ such that for all q ≥ q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the “Weitz tree”, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erd?s–Rényi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which there exists an α > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Γ of length O(log n) satisfies ${\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}$ . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.     

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.     

On the Wronskian combinants of binary forms

Given a sequence A=(A₁,…,A_r) of binary d-ics, we construct a set of combinants C={C_q:0≤q≤r,q≠1}, to be called the Wronskian combinants of A. We show that the span of A can be recovered from C as the solution space of an SL(2)-invariant differential equation. The Wronskian combinants define a projective imbedding of the Grassmannian G(r,S_d), and, as a corollary, any other combinant of A is expressible as a compound transvectant in C.Our main result characterises those sequences of binary forms that can arise as Wronskian combinants; namely, they are the ones such that the associated differential equation has the maximal number of linearly independent polynomial solutions. Along the way we deduce some identities which relate Wronskians to transvectants. We also calculate compound transvectant formulae for C in the case r=3.     

On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d²−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F_i,d(x)=f_i(x²+x+1−d), where f_i(x) denotes the minimal polynomial of the Gauss period , being ζ_i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F_i,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.