39
39
Sep 19, 2013
09/13
by
Alexander Postnikov
texts
eye 39
favorite 0
comment 0
The quantum Bruhat graph, which is an extension of the graph formed by covering relations in the Bruhat order, is naturally related to the quantum cohomology ring of G/B. We enhance a result of Fulton and Woodward by showing that the minimal monomial in the quantum parameters that occurs in the quantum product of two Schubert classes has a simple interpretation in terms of directed paths in this graph. We define path Schubert polynomials, which are quantum cohomology analogues of skew Schubert...
Source: http://arxiv.org/abs/math/0206077v1
44
44
Sep 22, 2013
09/13
by
Alexander Postnikov
texts
eye 44
favorite 0
comment 0
This article presents a formula for products of Schubert classes in the quantum cohomology ring of the Grassmannian. We introduce a generalization of Schur symmetric polynomials for shapes that are naturally embedded in a torus. Then we show that the coefficients in the expansion of these toric Schur polynomials, in terms of the regular Schur polynomials, are exactly the 3-point Gromov-Witten invariants; which are the structure constants of the quantum cohomology ring. This construction implies...
Source: http://arxiv.org/abs/math/0205165v2
43
43
Jul 20, 2013
07/13
by
Alexander Postnikov
texts
eye 43
favorite 0
comment 0
The group (Z/nZ)^2 is shown to act on the Gromov-Witten invariants of the complex flag manifold. We also deduce several corollaries of this result.
Source: http://arxiv.org/abs/math/0009174v2
46
46
Sep 19, 2013
09/13
by
Alexander Postnikov
texts
eye 46
favorite 0
comment 0
The volume and the number of lattice points of the permutohedron P_n are given by certain multivariate polynomials that have remarkable combinatorial properties. We give several different formulas for these polynomials. We also study a more general class of polytopes that includes the permutohedron, the associahedron, the cyclohedron, the Pitman-Stanley polytope, and various generalized associahedra related to wonderful compactifications of De Concini-Procesi. These polytopes are constructed as...
Source: http://arxiv.org/abs/math/0507163v1
214
214
Jul 20, 2013
07/13
by
Alexander Postnikov
texts
eye 214
favorite 0
comment 0
The aim of this paper is to discuss a relationship between total positivity and planar directed networks. We show that the inverse boundary problem for these networks is naturally linked with the study of the totally nonnegative Grassmannian. We investigate its cell decomposition, where the cells are the totally nonnegative parts of the matroid strata. The boundary measurements of networks give parametrizations of the cells. We present several different combinatorial descriptions of the cells,...
Source: http://arxiv.org/abs/math/0609764v1
131
131
Sep 19, 2013
09/13
by
Karola Meszaros; Alexander Postnikov
texts
eye 131
favorite 0
comment 0
We generalize the construction of connected branched polymers and the notion of the volume of the space of connected branched polymers studied by Brydges and Imbrie, and Kenyon and Winkler to any hyperplane arrangement A. The volume of the resulting configuration space of connected branched polymers associated to the hyperplane arrangement A is expressed through the value of the characteristic polynomial of A at 0. We give a more general definition of the space of branched polymers, where we do...
Source: http://arxiv.org/abs/0909.4547v2
42
42
Sep 22, 2013
09/13
by
Cristian Lenart; Alexander Postnikov
texts
eye 42
favorite 0
comment 0
We give an explicit combinatorial Chevalley-type formula for the equivariant K-theory of generalized flag varieties G/P which is a direct generalization of the classical Chevalley formula. Our formula implies a simple combinatorial model for the characters of the irreducible representations of G and, more generally, for the Demazure characters. This model can be viewed as a discrete counterpart of the Littelmann path model, and has several advantages. Our construction is given in terms of a...
Source: http://arxiv.org/abs/math/0309207v3
40
40
Sep 22, 2013
09/13
by
Sara Billey; Alexander Postnikov
texts
eye 40
favorite 0
comment 0
The aim of this article is to present a smoothness criterion for Schubert varieties in generalized flag manifolds $G/B$ in terms of patterns in root systems. We generalize Lakshmibai-Sandhya's well-known result that says that a Schubert variety in $SL(n)/B$ is smooth if and only if the corresponding permutation avoids the patterns 3412 and 4231. Our criterion is formulated uniformly in general Lie theoretic terms. We define a notion of pattern in Weyl group elements and show that a Schubert...
Source: http://arxiv.org/abs/math/0205179v2
32
32
Sep 18, 2013
09/13
by
Cristian Lenart; Alexander Postnikov
texts
eye 32
favorite 0
comment 0
We present a simple combinatorial model for the characters of the irreducible integrable highest weight modules for complex symmetrizable Kac-Moody algebras. This model can be viewed as a discrete counterpart to the Littelmann path model. We describe crystal graphs and give a Littlewood-Richardson rule for decomposing tensor products of irreducible representations. The new model is based on the notion of a lambda-chain, which is a chain of positive roots defined by certain interlacing...
Source: http://arxiv.org/abs/math/0502147v4
45
45
Sep 23, 2013
09/13
by
Thomas Lam; Alexander Postnikov
texts
eye 45
favorite 0
comment 0
This is the second of two papers where we study polytopes arising from affine Coxeter arrangements. Our results include a formula for their volumes, and also compatible definitions of hypersimplices, descent numbers and major index for all Weyl groups. We give a q-analogue of Weyl's formula for the order of the Weyl group. For A_n, C_n and D_4, we give a Grobner basis which induces the triangulation of alcoved polytopes.
Source: http://arxiv.org/abs/1202.4015v1
51
51
Sep 18, 2013
09/13
by
Federico Ardila; Alexander Postnikov
texts
eye 51
favorite 0
comment 0
We investigate ideals in a polynomial ring which are generated by powers of linear forms. Such ideals are closely related to the theories of fat point ideals, Cox rings, and box splines. We pay special attention to a family of power ideals that arises naturally from a hyperplane arrangement A. We prove that their Hilbert series are determined by the combinatorics of A, and can be computed from its Tutte polynomial. We also obtain formulas for the Hilbert series of the resulting fat point ideals...
Source: http://arxiv.org/abs/0809.2143v2
6
6.0
Jun 26, 2018
06/18
by
Miriam Farber; Alexander Postnikov
texts
eye 6
favorite 0
comment 0
We discuss arrangements of equal minors of totally positive matrices. More precisely, we investigate the structure of equalities and inequalities between the minors. We show that arrangements of equal minors of largest value are in bijection with sorted sets, which earlier appeared in the context of alcoved polytopes and Gr\"obner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the...
Topics: Mathematics, Combinatorics
Source: http://arxiv.org/abs/1502.01434
48
48
Sep 20, 2013
09/13
by
Alexander Postnikov; Bruce Sagan
texts
eye 48
favorite 0
comment 0
Given a sequence of integers b = (b_0,b_1,b_2,...) one gives a Dyck path P of length 2n the weight wt(P) = b_{h_1} b_{h_2} ... b_{h_n}, where h_i is the height of the ith ascent of P. The corresponding weighted Catalan number is C_n^b = sum_P wt(P), where the sum is over all Dyck paths of length 2n. So, in particular, the ordinary Catalan numbers C_n correspond to b_i = 1 for all i >= 0. Let xi(n) stand for the base two exponent of n, i.e., the largest power of 2 dividing n. We give a...
Source: http://arxiv.org/abs/math/0601339v2
29
29
Sep 18, 2013
09/13
by
Denis Chebikin; Alexander Postnikov
texts
eye 29
favorite 0
comment 0
We consider the inversion enumerator I_n(q), which counts labeled trees or, equivalently, parking functions. This polynomial has a natural extension to generalized parking functions. Substituting q = -1 into this generalized polynomial produces the number of permutations with a certain descent set. In the classical case, this result implies the formula I_n(-1) = E_n, the number of alternating permutations. We give a combinatorial proof of these formulas based on the involution principle. We...
Source: http://arxiv.org/abs/0806.0440v1
29
29
Sep 20, 2013
09/13
by
Alexander Postnikov; Boris Shapiro
texts
eye 29
favorite 0
comment 0
For a graph G, we construct two algebras, whose dimensions are both equal to the number of spanning trees of G. One of these algebras is the quotient of the polynomial ring modulo certain monomial ideal, while the other is the quotient of the polynomial ring modulo certain powers of linear forms. We describe the set of monomials that forms a linear basis in each of these two algebras. The basis elements correspond to G-parking functions that naturally came up in the abelian sandpile model....
Source: http://arxiv.org/abs/math/0301110v3
47
47
Sep 23, 2013
09/13
by
Oleg Gleizer; Alexander Postnikov
texts
eye 47
favorite 0
comment 0
The purpose of this paper is to present an interpretation for the decomposition of the tensor product of two or more irreducible representations of GL(N) in terms of a system of quantum particles. Our approach is based on a certain scattering matrix that satisfies a Yang-Baxter type equation. The corresponding piecewise-linear transformations of parameters give a solution to the tetrahedron equation. These transformation maps are naturally related to the dual canonical bases for modules over...
Source: http://arxiv.org/abs/math/9909124v1
2
2.0
Jun 29, 2018
06/18
by
Darij Grinberg; Alexander Postnikov
texts
eye 2
favorite 0
comment 0
The reduced expressions for a given element w of a Coxeter group (W, S) can be regarded as the vertices of a directed graph R(w); its arcs correspond to the braid moves. Specifically, an arc goes from a reduced expression a to a reduced expression b when b is obtained from a by replacing a contiguous subword of the form stst... (for some distinct s, t in S) by tsts... (where both subwords have length m_{s, t}, the order of st in W). We prove a strong bipartiteness-type result for this graph...
Topics: Combinatorics, Mathematics
Source: http://arxiv.org/abs/1603.03138
56
56
Sep 22, 2013
09/13
by
Thomas Lam; Alexander Postnikov
texts
eye 56
favorite 0
comment 0
The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of...
Source: http://arxiv.org/abs/math/0501246v2
44
44
Sep 18, 2013
09/13
by
Alexander Postnikov; Richard P. Stanley
texts
eye 44
favorite 0
comment 0
We study a family of polynomials whose values express degrees of Schubert varieties in the generalized complex flag manifold G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive several explicit formulas for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters, and generalized Littlewood-Richardson coefficients. In the second half of the paper, we concern with the case of to the...
Source: http://arxiv.org/abs/math/0502363v1
93
93
Jul 20, 2013
07/13
by
Alexander Postnikov; Richard P. Stanley
texts
eye 93
favorite 0
comment 0
We investigate several hyperplane arrangements that can be viewed as deformations of Coxeter arrangements. In particular, we prove a conjecture of Linial and Stanley that the number of regions of the arrangement x_i - x_j = 1, 1 \leq i
Source: http://arxiv.org/abs/math/9712213v1
59
59
Sep 21, 2013
09/13
by
Alexander Postnikov; David Speyer; Lauren Williams
texts
eye 59
favorite 0
comment 0
In this paper we use toric geometry to investigate the topology of the totally non-negative part of the Grassmannian (Gr_{kn})_{\geq 0}. This is a cell complex whose cells Delta_G can be parameterized in terms of the combinatorics of plane-bipartite graphs G. To each cell Delta_G we associate a certain polytope P(G). The polytopes P(G) are analogous to the well-known Birkhoff polytopes, and we describe their face lattices in terms of matchings and unions of matchings of G. We also demonstrate a...
Source: http://arxiv.org/abs/0706.2501v3
40
40
Sep 21, 2013
09/13
by
Suho Oh; Alexander Postnikov; Hwanchul Yoo
texts
eye 40
favorite 0
comment 0
The aim of this article is to link Schubert varieties in the flag manifold with hyperplane arrangements. For a permutation, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincare polynomial of the corresponding Schubert variety if and only if the Schubert variety is smooth. We give an explicit combinatorial formula for the Poincare polynomial. Our main technical tools are chordal graphs and...
Source: http://arxiv.org/abs/0709.3259v1
34
34
Sep 22, 2013
09/13
by
Karola Meszaros; Greta Panova; Alexander Postnikov
texts
eye 34
favorite 0
comment 0
We study multiplication of any Schubert polynomial \mathfrak{S}_w by a Schur polynomial s_\lambda (the Schubert polynomial of a Grassmannian permutation) and the expansion of this product in the ring of Schubert polynomials. We derive explicit nonnegative combinatorial expressions for the expansion coefficients for certain special partitions \lambda, including hooks and the 2x2 box. We also prove combinatorially the existence of such nonnegative expansion when the Young diagram of \lambda is a...
Source: http://arxiv.org/abs/1210.1295v2
32
32
Jul 20, 2013
07/13
by
Alexander Postnikov; Victor Reiner; Lauren Williams
texts
eye 32
favorite 0
comment 0
The aim of the paper is to calculate face numbers of simple generalized permutohedra, and study their f-, h- and gamma-vectors. These polytopes include permutohedra, associahedra, graph-associahedra, simple graphic zonotopes, nestohedra, and other interesting polytopes. We give several explicit formulas for h-vectors and gamma-vectors involving descent statistics. This includes a combinatorial interpretation for gamma-vectors of a large class of generalized permutohedra which are flag simple...
Source: http://arxiv.org/abs/math/0609184v2
68
68
Sep 22, 2013
09/13
by
Francesco Brenti; Sergey Fomin; Alexander Postnikov
texts
eye 68
favorite 0
comment 0
We introduce and study a family of operators which act in the span of a Weyl group $W$ and provide a multi-parameter solution to the quantum Yang-Baxter equations of the corresponding type. Our operators generalize the "quantum Bruhat operators" that appear in the explicit description of the multiplicative structure of the (small) quantum cohomology ring of $G/B$. The main combinatorial applications concern the "tilted Bruhat order," a graded poset whose unique minimal...
Source: http://arxiv.org/abs/math/9805079v1
32
32
Sep 18, 2013
09/13
by
Alexander Postnikov; Boris Shapiro; Mikhail Shapiro
texts
eye 32
favorite 0
comment 0
Let C(X) be the algebra generated by the curvature 2-forms of the standard hermitian line bundles over the complex homogeneous manifold X=G/B. We calculate the Hilbert polynomial of C(X) and give its presentation as a quotient of a polynomial ring. In particular, we show the dimension of C(X) is equal to the number of independent subsets of roots in the corresponding root system. As a tool we study a more general algebra associated with a point on a Grassmannian and calculate its Hilbert...
Source: http://arxiv.org/abs/math/9901075v1
44
44
Sep 18, 2013
09/13
by
Thomas Lam; Alexander Postnikov; Pavlo Pylyavskyy
texts
eye 44
favorite 0
comment 0
We prove Okounkov's conjecture, a conjecture of Fomin-Fulton-Li-Poon, and a special case of Lascoux-Leclerc-Thibon's conjecture on Schur positivity and give several more general statements using a recent result of Rhoades and Skandera. An alternative proof of this result is provided. We also give an intriguing log-concavity property of Schur functions.
Source: http://arxiv.org/abs/math/0502446v3
43
43
Sep 18, 2013
09/13
by
Ron M. Adin; Alexander Postnikov; Yuval Roichman
texts
eye 43
favorite 0
comment 0
In this note a combinatorial formula related to the symmetric group is generalized to an arbitrary finite Weyl group.
Source: http://arxiv.org/abs/math/0005021v1
67
67
Sep 23, 2013
09/13
by
Ron M. Adin; Alexander Postnikov; Yuval Roichman
texts
eye 67
favorite 0
comment 0
Two actions of the Hecke algebra of type A on the corresponding polynomial ring are studied. Both are deformations of the natural action of the symmetric group on polynomials, and keep symmetric functions invariant. We give an explicit description of these actions, and deduce a combinatorial formula for the resulting graded characters on the coinvariant algebra.
Source: http://arxiv.org/abs/math/9908090v2
54
54
Sep 20, 2013
09/13
by
Ron M. Adin; Alexander Postnikov; Yuval Roichman
texts
eye 54
favorite 0
comment 0
A Gelafand model for wreath products $\Z_r\wr S_n$ is constructed. The proof relies on a combinatorial interpretation of the characters of the model, extending a classical result of Frobenius and Schur.
Source: http://arxiv.org/abs/0802.2824v1
54
54
Sep 21, 2013
09/13
by
Ron M. Adin; Alexander Postnikov; Yuval Roichman
texts
eye 54
favorite 0
comment 0
A combinatorial construction of a Gelafand model for the symmetric group and its Iwahori-Hecke algebra is presented.
Source: http://arxiv.org/abs/0709.3962v2
47
47
Sep 20, 2013
09/13
by
Cecilia Bebeacua; Toufik Mansour; Alexander Postnikov; Simone Severini
texts
eye 47
favorite 0
comment 0
The X-ray of a permutation is defined as the sequence of antidiagonal sums in the associated permutation matrix. X-rays of permutation are interesting in the context of Discrete Tomography since many types of integral matrices can be written as linear combinations of permutation matrices. This paper is an invitation to the study of X-rays of permutations from a combinatorial point of view. We present connections between these objects and nondecreasing differences of permutations, zero-sum...
Source: http://arxiv.org/abs/math/0506334v1
2
2.0
Jun 30, 2018
06/18
by
Nima Arkani-Hamed; Jacob L. Bourjaily; Freddy Cachazo; Alexander Postnikov; Jaroslav Trnka
texts
eye 2
favorite 0
comment 0
We initiate an exploration of on-shell functions in $\mathcal{N}=4$ SYM beyond the planar limit by providing compact, combinatorial expressions for all leading singularities of MHV amplitudes and showing that they can always be expressed as a positive sum of differently ordered Parke-Taylor tree amplitudes. This is understood in terms of an extended notion of positivity in $G(2,n)$, the Grassmannian of 2-planes in $n$ dimensions: a single on-shell diagram can be associated with many different...
Topic: High Energy Physics - Theory
Source: http://arxiv.org/abs/1412.8475
102
102
Sep 23, 2013
09/13
by
Nima Arkani-Hamed; Jacob L. Bourjaily; Freddy Cachazo; Alexander B. Goncharov; Alexander Postnikov; Jaroslav Trnka
texts
eye 102
favorite 0
comment 0
We establish a direct connection between scattering amplitudes in planar four-dimensional theories and a remarkable mathematical structure known as the positive Grassmannian. The central physical idea is to focus on on-shell diagrams as objects of fundamental importance to scattering amplitudes. We show that the all-loop integrand in N=4 SYM is naturally represented in this way. On-shell diagrams in this theory are intimately tied to a variety of mathematical objects, ranging from a new...
Source: http://arxiv.org/abs/1212.5605v1
28
28
Sep 22, 2013
09/13
by
Neil R. Constable; Daniel Z. Freedman; Matthew Headrick; Shiraz Minwalla; Lubos Motl; Alexander Postnikov; Witold Skiba
texts
eye 28
favorite 0
comment 0
Recently, Berenstein et al. have proposed a duality between a sector of N=4 super-Yang-Mills theory with large R-charge J, and string theory in a pp-wave background. In the limit considered, the effective 't Hooft coupling has been argued to be lambda'=g_{YM}^2 N/J^2=1/(mu p^+ alpha')^2. We study Yang-Mills theory at small lambda' (large mu) with a view to reproducing string interactions. We demonstrate that the effective genus counting parameter of the Yang-Mills theory is g_2^2=J^4/N^2=(4 pi...
Source: http://arxiv.org/abs/hep-th/0205089v3
