Dyck paths and positroids from unit interval orders

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:154

Article

Chavez, Anastasia¹  Gotti, Felix¹ 

[1] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA

关键词: Positroid;    Dyck path;    Unit interval order;    Decorated permutation;    Le diagram;    Positive Grassmannian;   

DOI  :  10.1016/j.jcta.2017.09.005

来源: Elsevier

【 摘 要 】

It is well known that the number of non-isomorphic unit interval orders on [n] equals the n-th Catalan number. Using work of Skandera and Reed and work of Postnikov, we show that each unit interval order on [n] naturally induces a rank n positroid on [2n]. We call the positroids produced in this fashion unit interval positroids. We characterize the unit interval positroids by describing their associated decorated permutations, showing that each one must be a 2n-cycle encoding a Dyck path of length 2n. We also provide recipes to read the decorated permutation of a unit interval positroid P from both the antiadjacency matrix and the interval representation of the unit interval order inducing P. Using our characterization of the decorated permutation, we describe the Le-diagrams corresponding to unit interval positroids. In addition, we give a necessary and sufficient condition for two Grassmann cells parameterized by unit interval positroids to be adjacent inside the Grassmann cell complex. Finally, we propose a potential approach to find the f-vector of a unit interval order. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free