14,761 research outputs found
Correction to “Combinatorics and geometry of power ideals”: Two counterexamples for power ideals of hyperplane arrangements
No full textWe disprove Holtz and Ron’s conjecture that the power ideal
C[subscript A,−2] of a hyperplane arrangement A (also called the internal zonotopal space) is generated by A-monomials. We also show that, in contrast with the case k ≥ −2, the Hilbert series of C[subscript A,k] is not determined by the matroid of A for k ≤ −6.National Science Foundation (U.S.) (CAREER Award DMS-0504629
Branched Polymers and Hyperplane Arrangements
No full textOriginal manuscript December 17, 2009We 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 (Ann Math, 158:1019–1039, 2003), and Kenyon and Winkler (Am Math Mon, 116(7):612–628, 2009) to any central hyperplane arrangement A A . The volume of the resulting configuration space of connected branched polymers associated to the hyperplane arrangement A A is expressed through the value of the characteristic polynomial of A A at 0. We give a more general definition of the space of branched polymers, where we do not require connectivity, and introduce the notion of q-volume for it, which is expressed through the value of the characteristic polynomial of A A at −q − q . Finally, we relate the volume of the space of branched polymers to broken circuits and show that the cohomology ring of the space of branched polymers is isomorphic to the Orlik–Solomon algebra.National Science Foundation (U.S.) (Grant DMS 6923772)National Science Foundation (U.S.) (CAREER Award DMS 0504629
Arrangements of equal minors in the positive Grassmannian
No full textWe 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öbner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the Eulerian number. On the other hand, we prove in many cases that arrangements of equal minors of smallest value are weakly separated sets. Weakly separated sets, originally introduced by Leclerc and Zelevinsky, are closely related to the positive Grassmannian and the associated cluster algebra. However, we also construct examples of arrangements of smallest minors which are not weakly separated using chain reactions of mutations of plabic graphs. Keywords: Totally positive matrices; The positive Grassmannian; Minors and Plücker coordinates; Matrix completion problem; Arrangements of equal minors; Weakly separated and sorted sets; Triangulations and thrackles; Cluster algebras and plabic graphs; The Laurent phenomenon; Alcoved polytopeshypersimplices; The affine Coxeter arrangement; The Eulerian numbers; Chain reactions of mutations; Mutation distancehoneycombs; Gröbner bases; Schur positivit
Proof of a conjecture of Bergeron, Ceballos and Labbé
No full text© 2017, University at Albany. All rights reserved. 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 ∈ S) by tsts … (where both subwords have length m s,t , the order of st ∈ W). We prove a strong bipartiteness-type result for this graph R(w): Not only does every cycle of R(w) have even length; actually, the arcs of R(w) can be colored (with colors corresponding to the type of braid moves used), and to every color c corresponds an “opposite” color c op (corresponding to the reverses of the braid moves with color c), and for any color c, the number of arcs in any given cycle of R(w) having color in {c, c op } is even. This is a generalization and strengthening of a 2014 result by Bergeron, Ceballos and Labbé
Schur Times Schubert via the Fomin-Kirillov Algebra
No full textWe study multiplication of any Schubert polynomial S[subscript w] by a Schur polynomial sλ (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 λ, including hooks and the 2×2 box. We also prove combinatorially the existence of such nonnegative expansion when the Young diagram of λ is a hook plus a box at the (2,2) corner. We achieve this by evaluating Schubert polynomials at the Dunkl elements of the Fomin-Kirillov algebra and proving special cases of the nonnegativity conjecture of Fomin and Kirillov.
This approach works in the more general setup of the (small) quantum cohomology ring of the complex flag manifold and the corresponding (3-point) Gromov-Witten invariants. We provide an algebro-combinatorial proof of the nonnegativity of the Gromov-Witten invariants in these cases, and present combinatorial expressions for these coefficients.National Science Foundation (U.S.) (Grant DMS-6923772
Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
No full textLet G be a connected bipartite graph with colour classes E and V and root polytope Q. Regarding the hypergraph H=(V,E) induced by G, we prove that the interior polynomial of H is equivalent to the Ehrhart polynomial of Q, which in turn is equivalent to the h-vector of any triangulation of Q. It follows that the interior polynomials of H and its transpose H=(E,V) agree. When G is a complete bipartite graph, our result recovers a well-known hypergeometric identity due to Saalschütz. It also implies that certain extremal coefficients in the Homfly polynomial of a special alternating link can be read off of an associated Floer homology group.National Science Foundation (U.S.) (Grant DMS‐1100147)National Science Foundation (U.S.) (Grant DMS‐1362336
Combinatorics related to the totally nonnegative Grassmannian
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011.Cataloged from PDF version of thesis.Includes bibliographical references (p. 77).In this thesis we study the combinatorial objects that appear in the study of nonnegative part of the Grassmannian. The classical theory of total positivity studies matrices such that all minors are nonnegative. Lustzig extended this theory to arbitrary reductive groups and flag varieties. Postnikov studied the nonnegative part of the Grassmannian, showed that it has a nice cell decomposition using matroid strata, and introduced several combinatorial objects that encode such cells. In this thesis, we focus on the combinatorial aspects of such associated objects. In chapter 1, we review the definition of the cells in the totally nonnegative part of the Grassmannian, and the associated combinatorial objects. Each cell corresponds to a certain matroid called positroid. There are numerous combinatorial objects that can represent a positroid, such as a J-diagram, a Grassmann necklace or a decorated permutation. We will go over the definitions of such objects and check some of their properties. And for decorated permutations, there are certain planar graphs called plabic graphs, that plays the role of wiring diagrams for permutations, and this would serve as the main tool for our result in chapter 3. In chapter 2, we prove a conjecture by Postnikov, that allows us to give a purely combinatorial definition of positroids without relying on its realizability. We will show that positroids can be defined as certain collections that satisfy some cyclic inequalities. In other words, we express positroids using cyclically shifted Schubert matroids. Postnikov showed that each positroid cell is an intersection of the totally nonnegative Grassmannian and cyclically shifted Schubert cells. Combinatorially, this result implies that each positroid is included in an intersection of cyclically shifted Schubert matroids. We extend this result: each positroid is exactly an intersection of certain cyclically shifted Schubert niatroids. In chapter 3, we study maximal weakly separated collections. Weak separation is a condition on pair of sets that first appeared in Leclerc and Zelevinsky's work describing quasicommuting families of quantum minors. They conjectured that all maximal by inclusion weakly separated collections of minors have the same cardinality (the purity conjecture), and that they can be related to each other by a sequence of mutations. We link the study of weak separation with the totally nonnegative Grassmannian, by extending the notion of weak separation to positroids. By using plabic graphs, we generalize the results and conjectures of Leclerc and Zelevinsky, and prove them in this more general setup. This part of the thesis is based on joint work with Alexander Postnikov and David Speyer. In chapter 4, we prove a property on h-vector of positroids. The h-vector of a matroid is an interesting Tutte polynomial evaluation, which is originally defined as the h-vector of the corresponding independent complex of a matroid. Stanley conjectured that h-vector of any matroid is a pure O-sequence, which is a sequence coming froi a Hilbert function of a monomial Artinian level algebra. We show that the conjecture holds for positroids: that is, the h-vector of a positroid is a pure O-sequence.by SuHo Oh.Ph.D
Inequalities and Asymptotic Formulas in Algebraic Combinatorics
No full textThis thesis concerns certain inequalities and asymptotic formulas in algebraic combinatorics. It consists of two separate parts. The first part studies inequalities concerning triangular-grid billiards and plabic graphs of Lam–Postnikov essential dimension 2. The material in this part is based on joint work with Colin Defant. The second part studies inequalities and asymptotic formulas concerning large-scale rook placements.Ph.D
Studies on quasisymmetric functions
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2016.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (pages 297-302).In 1983, Ira Gessel introduced the ring of quasisymmetric functions (QSym), an extension of the ring of symmetric functions and nowadays one of the standard examples of a combinatorial Hopf algebra. In this thesis, I elucidate three aspects of its theory: 1) Gessel's P-partition enumerators are quasisymmetric functions that generalize, and share many properties of, the Schur functions; their Hopf-algebraic antipode satisfies a simple and explicit formula. Malvenuto and Reutenauer have generalized this formula to quasisymmetric functions "associated to a set of equalities and inequalities". I reformulate their generalization in the handier terminology of double posets, and present a new proof and an even further generalization in which a group acts on the double poset. 2) There is a second bialgebra structure on QSym, with its own "internal" comultiplication. I show how this bialgebra can be constructed using the Aguiar-Bergeron- Sottile universal property of QSym by extending the base ring; the same approach also constructs the so-called "Bernstein homomorphism", which makes any connected graded commutative Hopf algebra into a comodule over this second bialgebra QSym. 3) I prove a recursive formula for the "dual immaculate quasisymmetric functions" (a certain special case of P-partition enumerators) conjectured by Mike Zabrocki. The proof introduces a dendriform algebra structure on QSym. Two further results appearing in this thesis, but not directly connected to QSym, are: 4) generalizations of Whitney's formula for the chromatic polynomial of a graph in terms of broken circuits. One of these generalizations involves weights assigned to the broken circuits. A formula for the chromatic symmetric function is also obtained. 5) a proof of a conjecture by Bergeron, Ceballos and Labbé on reduced-word graphs in Coxeter groups (joint work with Alexander Postnikov). Given an element of a Coxeter group, we can form a graph whose vertices are the reduced expressions of this element, and whose edges connect two reduced expressions which are "a single braid move apart". The simplest part of the conjecture says that this graph is bipartite; we show finer claims about its cycles.by Darij Grinberg.Ph. D
Mixed volumes of hypersimplices, root systems and shifted young tableaux
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010.Cataloged from PDF version of thesis.Includes bibliographical references (p. 40-41).This thesis consists of two parts. In the first part, we start by investigating the classical permutohedra as Minkowski sums of the hypersimplices. Their volumes can be expressed as polynomials whose coefficients - the mixed Eulerian numbers - are given by the mixed volumes of the hypersimplices. We build upon results of Postnikov and derive various recursive and combinatorial formulas for the mixed Eulerian numbers. We generalize these results to arbitrary root systems [fee], and obtain cyclic, recursive and combinatorial formulas for the volumes of the weight polytopes ([fee]-analogues of permutohedra) as well as the mixed [fee]-Eulerian numbers. These formulas involve Cartan matrices and weighted paths in Dynkin diagrams, and thus enable us to extend the theory of mixed Eulerian numbers to arbitrary matrices whose principal minors are invertible. The second part deals with the study of certain patterns in standard Young tableaux of shifted shapes. For the staircase shape, Postnikov found a bijection between vectors formed by the diagonal entries of these tableaux and lattice points of the (standard) associahedron. Using similar techniques, we generalize this result to arbitrary shifted shapes.by Dorian Croitoru.Ph.D
- …
