On the combinatorics of crystal graphs, II. The crystal commutor

We present an explicit combinatorial realization of the commutor in the category of crystals which was first studied by Henriques and Kamnitzer. Our realization is based on certain local moves defined by van Leeuwen.

     

Explicit formulae for one-part double Hurwitz numbers with completed 3-cycles

We prove two explicit formulae for one-part double Hurwitz numbers with completed 3-cycles. We define “combinatorial Hodge integrals” from these numbers in the spirit of the celebrated ELSV formula. The obtained results imply some explicit formulae and properties of the combinatorial Hodge integrals.     

The Algebra of Conjugacy Classes in Symmetric Groups and Partial Permutations

We prove the convolution formula for the conjugacy classes in symmetric groups conjectured by the second author. A combinatorial interpretation of coefficients is provided. As a main tool, we introduce a new semigroup of partial permutations. We describe its structure, representations, and characters. We also discuss filtrations on the subalgebra of invariants in the semigroup algebra. Bibliography: 10 titles.     

Bilabelled increasing trees and hook-length formulae

We introduce two different kinds of increasing bilabellings of trees, for which we provide enumeration formulae. One of the bilabelled tree families considered is enumerated by the reduced tangent numbers and is in bijection with a tree family introduced by Poupard [11]. Both increasing bilabellings naturally lead to hook-length formulae for trees and forests; in particular, one construction gives a combinatorial interpretation of a formula for labelled unordered forests obtained recently by Chen et al. [1].     

Four positive formulae for type A quiver polynomials

We give four positive formulae for the (equioriented type A) quiver polynomials of Buch and Fulton [BF99 ]. All four formulae are combinatorial, in the sense that they are expressed in terms of combinatorial objects of certain types: Zelevinsky permutations, lacing diagrams, Young tableaux, and pipe dreams (also known as rc-graphs). Three of our formulae are multiplicity-free and geometric, meaning that their summands have coefficient 1 and correspond bijectively to components of a torus-invariant scheme. The remaining (presently non-geometric) formula is a variant of the conjecture of Buch and Fulton in terms of factor sequences of Young tableaux [BF99 ]; our proof of it proceeds by way of a new characterization of the tableaux counted by quiver constants. All four formulae come naturally in “doubled” versions, two for double quiver polynomials, and the other two for their stable limits, the double quiver functions, where setting half the variables equal to the other half specializes to the ordinary case. Our method begins by identifying quiver polynomials as multidegrees [BB82 , Jos84 , BB85 , Ros89 ] via equivariant Chow groups [EG98 ]. Then we make use of Zelevinsky’s map from quiver loci to open subvarieties of Schubert varieties in partial flag manifolds [Zel85 ]. Interpreted in equivariant cohomology, this lets us write double quiver polynomials as ratios of double Schubert polynomials [LS82 ] associated to Zelevinsky permutations; this is our first formula. In the process, we provide a simple argument that Zelevinsky maps are scheme-theoretic isomorphisms (originally proved in [LM98 ]). Writing double Schubert polynomials in terms of pipe dreams [FK96 ] then provides another geometric formula for double quiver polynomials, via [KM05 ]. The combinatorics of pipe dreams for Zelevinsky permutations implies an expression for limits of double quiver polynomials in terms of products of Stanley symmetric functions [Sta84 ]. A degeneration of quiver loci (orbit closures of GL on quiver representations) to unions of products of matrix Schubert varieties [Ful92 , KM05 ] identifies the summands in our Stanley function formula combinatorially, as lacing diagrams that we construct based on the strands of Abeasis and Del Fra in the representation theory of quivers [AD80 ]. Finally, we apply the combinatorial theory of key polynomials to pass from our lacing diagram formula to a double Schur function formula in terms of peelable tableaux [RS95a , RS98 ], and from there to our formula of Buch–Fulton type.     

Uniqueness of Walkup's 9-vertex 3-dimensional Klein bottle

Via a computer search, Altshuler and Steinberg found that there are 1296+1 combinatorial 3-manifolds on nine vertices, of which only one is non-sphere. This exceptional 3-manifold triangulates the twisted S²-bundle over S¹. It was first constructed by Walkup. In this paper, we present a computer-free proof of the uniqueness of this non-sphere combinatorial 3-manifold. As opposed to the computer-generated proof, ours does not require wading through all the 9-vertex 3-spheres. As a preliminary result, we also show that any 9-vertex combinatorial 3-manifold is equivalent by proper bistellar moves to a 9-vertex neighbourly 3-manifold.     

New Bases for Band Varieties

We give a new set of bases for band varieties which is simpler than those mentioned. It is again based on three families of words but they are defined by a single inductive formula. The proof consists in comparing the new system with the second one mentioned above. The formulae for meets and joins are also simpler in the new system of bases.     

Jumping coefficients and spectrum of a hyperplane arrangement

In an earlier version of this paper written by the second named author, we showed that the jumping coefficients of a hyperplane arrangement depend only on the combinatorial data of the arrangement as conjectured by Mustaţǎ. For this we proved a similar assertion on the spectrum. After this first proof was written, the first named author found a more conceptual proof using the Hirzebruch–Riemann–Roch theorem where the assertion on the jumping numbers was proved without reducing to that for the spectrum. In this paper we improve these methods and show that the jumping numbers and the spectrum are calculable in low dimensions without using a computer. In the reduced case we show that these depend only on fewer combinatorial data, and give completely explicit combinatorial formulas for the jumping coefficients and (part of) the spectrum in the case the ambient dimension is 3 or 4. We also give an analogue of Mustaţǎ’s formula for the spectrum.     

A universal formula for deformation quantization on Kähler manifolds

We give an explicit local formula for any formal deformation quantization, with separation of variables, on a Kähler manifold. The formula is given in terms of differential operators, parametrized by acyclic combinatorial graphs.     

Enumeration of Unrooted Odd-Valent Regular Planar Maps

We derive closed formulae for the numbers of rooted maps with a fixed number of vertices of the same odd degree except for the root vertex and one other exceptional vertex of degree 1. The same applies to the generating functions for these numbers. Similar results, but without the vertex of degree 1, were obtained by the first author and Rahman. We also show, by manipulating a recursion of Bouttier, Di Francesco and Guitter, that there are closed formulae when the exceptional vertex has arbitrary degree. We combine these formulae with results of the second author to count unrooted regular maps of odd degree. In this way we obtain, for each even n, a closed formula for the function f _n whose value at odd positive integers r is the number of unrooted maps (up to orientation-preserving homeomorphisms) with n vertices and degree r. The formula for f _n becomes more cumbersome as n increases, but for n > 2 each has a bounded number of terms independent of r.     

An elementary geometric nonstandard proof of the Jordan curve theorem

We give an elementary proof, using nonstandard analysis, of the Jordan curve theorem. We also give a nonstandard generalization of the theorem. The proof is purely geometrical in character, without any use of topological concepts and is based on a discrete finite form of the Jordan theorem, whose proof is purely combinatorial.Some familiarity with nonstandard analysis is assumed. The rest of the paper is self-contained except for the proof a discrete standard form of the Jordan theorem. The proof is based on hyperfinite approximations to regions on the plane.Research of the first author partially supported by FONDECYT Grant # 91-1208 and of the second author, by FONDECYT Grant # 90-0647.     

Holographic formula for Q-curvature

This paper derives an explicit formula for Branson's Q-curvature in even-dimensional conformal geometry. The ingredients in the formula come from the Poincaré metric in one higher dimension; hence the formula is called holographic. When specialized to the conformally flat case, the holographic formula expresses the Q-curvature as a multiple of the Pfaffian and the divergence of a natural 1-form. The paper also outlines the relation between holographic formulae for Q-curvature and a new theory of conformally covariant families of differential operators due to the second author.     

Some degenerations of Kazhdan–Lusztig ideals and multiplicities of Schubert varieties

We study Hilbert–Samuel multiplicity for points of Schubert varieties in the complete flag variety, by Gröbner degenerations of the Kazhdan–Lusztig ideal. In the covexillary case, we give a manifestly positive combinatorial rule for multiplicity by establishing (with a Gröbner basis) a reduced limit whose Stanley–Reisner simplicial complex is homeomorphic to a shellable ball or sphere. We show that multiplicity counts the number of facets of this complex. We also obtain a formula for the Hilbert series of the local ring. In particular, our work gives a multiplicity rule for Grassmannian Schubert varieties, providing alternative statements and proofs to formulae of Lakshmibai and Weyman (1990) [26], Rosenthal and Zelevinsky (2001) [37], Krattenthaler (2001) [22], Kodiyalam and Raghavan (2003) [21], Kreiman and Lakshmibai (2004) [24], Ikeda and Naruse (2009) [13] and Woo and Yong (2009) [40]. We suggest extensions of our methodology to the general case.     

Polarizations and differential calculus in affine spaces

Within the framework of mappings between affine spaces, the notion of nth polarization of a function will lead to an intrinsic characterization of polynomial functions. We prove that the characteristic features of derivations, such as linearity, iterability, Leibniz and chain rules are shared - at the finite level - by the polarization operators. We give these results by means of explicit general formulae, which are valid at any order n, and are based on combinatorial identities. The infinitesimal limits of the nth polarizations of a function will yield its nth derivatives (without resorting to the usual recursive definition), and the afore-mentioned properties will be recovered directly in the limit. Polynomial functions will allow us to produce a coordinate free version of Taylor's formula.     

Simple Formulae for the Number of Quadrics and Symmetric Forms of Modules Over Local Rings

Simple formulae of similar type for the number of quadrics and symmetric forms of modules over local rings are found analytically. This simplification of known formulae of Levchuk and Starikova is achieved using integral representation method of combinatorial summation and leads to number-theoretical identities of new type. The problem of algebraic interpretation of new formulae is posed.     

The stability of barycentric interpolation at the Chebyshev points of the second kind

We present a new analysis of the stability of the first and second barycentric formulae for interpolation at the Chebyshev points of the second kind. Our theory shows that the second formula is more stable than previously thought and our experiments confirm its stability in practice.We also extend our current understanding regarding the accuracy problems of the first barycentric formula.     

Convexity results and sharp error estimates in approximate multivariate integration

An interesting property of the midpoint rule and the trapezoidal rule, which is expressed by the so-called Hermite-Hadamard inequalities, is that they provide one-sided approximations to the integral of a convex function. We establish multivariate analogues of the Hermite-Hadamard inequalities and obtain access to multivariate integration formulae via convexity, in analogy to the univariate case. In particular, for simplices of arbitrary dimension, we present two families of integration formulae which both contain a multivariate analogue of the midpoint rule and the trapezoidal rule as boundary cases. The first family also includes a multivariate analogue of a Maclaurin formula and of the two-point Gaussian quadrature formula; the second family includes a multivariate analogue of a formula by P.C. Hammer and of Simpson's rule. In both families, we trace out those formulae which satisfy a Hermite-Hadamard inequality. As an immediate consequence of the latter, we obtain sharp error estimates for twice continuously differentiable functions.

     

Applications of minor summation formula III, Plücker relations, lattice paths and Pfaffian identities

The initial purpose of the present paper is to provide a combinatorial proof of the minor summation formula of Pfaffians in [Ishikawa, Wakayama, Minor summation formula of Pfaffians, Linear and Multilinear Algebra 39 (1995) 285-305] based on the lattice path method. The second aim is to study applications of the minor summation formula for obtaining several identities. Especially, a simple proof of Kawanaka's formula concerning a q-series identity involving the Schur functions [Kawanaka, A q-series identity involving Schur functions and related topics, Osaka J. Math. 36 (1999) 157-176] and of the identity in [Kawanaka, A q-Cauchy identity involving Schur functions and imprimitive complex reflection groups, Osaka J. Math. 38 (2001) 775-810] which is regarded as a determinant version of the previous one are given.