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