On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-14

AUTHORS

Karola Mészáros, Alejandro H. Morales, Jessica Striker

ABSTRACT

We study an alternating sign matrix analogue of the Chan–Robbins–Yuen polytope, which we call the ASM-CRY polytope. We show that this polytope has Catalan many vertices and its volume is equal to the number of standard Young tableaus of staircase shape; we also determine its Ehrhart polynomial. We achieve the previous by proving that the members of a family of faces of the alternating sign matrix polytope which includes ASM-CRY are both order and flow polytopes. Inspired by the above results, we relate three established triangulations of order and flow polytopes, namely Stanley’s triangulation of order polytopes, the Postnikov–Stanley triangulation of flow polytopes and the Danilov–Karzanov–Koshevoy triangulation of flow polytopes. We show that when a graph G is a planar graph, in which case the flow polytope FG is also an order polytope, Stanley’s triangulation of this order polytope is one of the Danilov–Karzanov–Koshevoy triangulations of FG. Moreover, for a general graph G we show that the set of Danilov–Karzanov–Koshevoy triangulations of FG equals the set of framed Postnikov–Stanley triangulations of FG. We also describe explicit bijections between the combinatorial objects labeling the simplices in the above triangulations. More... »

PAGES

1-36

References to SciGraph publications

  • 2008-12. Kostant Partitions Functions and Flow Polytopes in TRANSFORMATION GROUPS
  • 1986-03. Two poset polytopes in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2009-08. A generating function for all semi-magic squares and the volume of the Birkhoff polytope in JOURNAL OF ALGEBRAIC COMBINATORICS
  • 2010-09. Enumeration formulas for young tableaux in a diagonal strip in ISRAEL JOURNAL OF MATHEMATICS
  • 1997-10. Reduced Words and Plane Partitions in JOURNAL OF ALGEBRAIC COMBINATORICS
  • 1978-09. Extreme points and adjacency relationship in the flow polytope in CALCOLO
  • 2003-10. The Ehrhart Polynomial of the Birkhoff Polytope in DISCRETE & COMPUTATIONAL GEOMETRY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00454-019-00073-2

    DOI

    http://dx.doi.org/10.1007/s00454-019-00073-2

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1112774968


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute for Advanced Study", 
              "id": "https://www.grid.ac/institutes/grid.78989.37", 
              "name": [
                "Department of Mathematics, Cornell University, 14853, Ithaca, NY, USA", 
                "School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "M\u00e9sz\u00e1ros", 
            "givenName": "Karola", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Department of Mathematics and Statistics, UMass, 01003, Amherst, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Morales", 
            "givenName": "Alejandro H.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "North Dakota State University", 
              "id": "https://www.grid.ac/institutes/grid.261055.5", 
              "name": [
                "Department of Mathematics, North Dakota State University, 58102, Fargo, ND, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Striker", 
            "givenName": "Jessica", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1515/9781400881970-002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000543319"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10801-008-0155-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004488591", 
              "https://doi.org/10.1007/s10801-008-0155-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10801-008-0155-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004488591", 
              "https://doi.org/10.1007/s10801-008-0155-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008694825493", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007605742", 
              "https://doi.org/10.1023/a:1008694825493"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008694825493", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007605742", 
              "https://doi.org/10.1023/a:1008694825493"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02575918", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014336759", 
              "https://doi.org/10.1007/bf02575918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02575918", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014336759", 
              "https://doi.org/10.1007/bf02575918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11856-010-0061-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022750489", 
              "https://doi.org/10.1007/s11856-010-0061-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11856-010-0061-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022750489", 
              "https://doi.org/10.1007/s11856-010-0061-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0097-3165(83)90068-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035588813"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187680", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048318263", 
              "https://doi.org/10.1007/bf02187680"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187680", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048318263", 
              "https://doi.org/10.1007/bf02187680"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10586458.2000.10504639", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049860582"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-003-2850-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050453872", 
              "https://doi.org/10.1007/s00454-003-2850-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-003-2850-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050453872", 
              "https://doi.org/10.1007/s00454-003-2850-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00031-008-9019-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050965400", 
              "https://doi.org/10.1007/s00031-008-9019-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00031-008-9019-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050965400", 
              "https://doi.org/10.1007/s00031-008-9019-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0195-6698(13)80128-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052692802"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/imrn/rnt212", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059691344"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-14", 
        "datePublishedReg": "2019-03-14", 
        "description": "We study an alternating sign matrix analogue of the Chan\u2013Robbins\u2013Yuen polytope, which we call the ASM-CRY polytope. We show that this polytope has Catalan many vertices and its volume is equal to the number of standard Young tableaus of staircase shape; we also determine its Ehrhart polynomial. We achieve the previous by proving that the members of a family of faces of the alternating sign matrix polytope which includes ASM-CRY are both order and flow polytopes. Inspired by the above results, we relate three established triangulations of order and flow polytopes, namely Stanley\u2019s triangulation of order polytopes, the Postnikov\u2013Stanley triangulation of flow polytopes and the Danilov\u2013Karzanov\u2013Koshevoy triangulation of flow polytopes. We show that when a graph G is a planar graph, in which case the flow polytope FG is also an order polytope, Stanley\u2019s triangulation of this order polytope is one of the Danilov\u2013Karzanov\u2013Koshevoy triangulations of FG. Moreover, for a general graph G we show that the set of Danilov\u2013Karzanov\u2013Koshevoy triangulations of FG equals the set of framed Postnikov\u2013Stanley triangulations of FG. We also describe explicit bijections between the combinatorial objects labeling the simplices in the above triangulations.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00454-019-00073-2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3089399", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.3849072", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.4179262", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1043660", 
            "issn": [
              "0179-5376", 
              "1432-0444"
            ], 
            "name": "Discrete & Computational Geometry", 
            "type": "Periodical"
          }
        ], 
        "name": "On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope", 
        "pagination": "1-36", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5ded22ff96a675a666f820603ed6f0d6ad0d760471174ed57189ae32ac2a798d"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00454-019-00073-2"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112774968"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00454-019-00073-2", 
          "https://app.dimensions.ai/details/publication/pub.1112774968"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:53", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29197_00000004.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00454-019-00073-2"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00454-019-00073-2'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00454-019-00073-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00454-019-00073-2'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00454-019-00073-2'


     

    This table displays all metadata directly associated to this object as RDF triples.

    121 TRIPLES      21 PREDICATES      36 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00454-019-00073-2 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N6e46615d31644dcf823017f71524d209
    4 schema:citation sg:pub.10.1007/bf02187680
    5 sg:pub.10.1007/bf02575918
    6 sg:pub.10.1007/s00031-008-9019-8
    7 sg:pub.10.1007/s00454-003-2850-8
    8 sg:pub.10.1007/s10801-008-0155-y
    9 sg:pub.10.1007/s11856-010-0061-6
    10 sg:pub.10.1023/a:1008694825493
    11 https://doi.org/10.1016/0097-3165(83)90068-7
    12 https://doi.org/10.1016/s0195-6698(13)80128-x
    13 https://doi.org/10.1080/10586458.2000.10504639
    14 https://doi.org/10.1093/imrn/rnt212
    15 https://doi.org/10.1515/9781400881970-002
    16 schema:datePublished 2019-03-14
    17 schema:datePublishedReg 2019-03-14
    18 schema:description We study an alternating sign matrix analogue of the Chan–Robbins–Yuen polytope, which we call the ASM-CRY polytope. We show that this polytope has Catalan many vertices and its volume is equal to the number of standard Young tableaus of staircase shape; we also determine its Ehrhart polynomial. We achieve the previous by proving that the members of a family of faces of the alternating sign matrix polytope which includes ASM-CRY are both order and flow polytopes. Inspired by the above results, we relate three established triangulations of order and flow polytopes, namely Stanley’s triangulation of order polytopes, the Postnikov–Stanley triangulation of flow polytopes and the Danilov–Karzanov–Koshevoy triangulation of flow polytopes. We show that when a graph G is a planar graph, in which case the flow polytope FG is also an order polytope, Stanley’s triangulation of this order polytope is one of the Danilov–Karzanov–Koshevoy triangulations of FG. Moreover, for a general graph G we show that the set of Danilov–Karzanov–Koshevoy triangulations of FG equals the set of framed Postnikov–Stanley triangulations of FG. We also describe explicit bijections between the combinatorial objects labeling the simplices in the above triangulations.
    19 schema:genre research_article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree false
    22 schema:isPartOf sg:journal.1043660
    23 schema:name On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope
    24 schema:pagination 1-36
    25 schema:productId N8058cf81e727412fb035bcaa5fc5c60a
    26 Nb0dde6509fcc4703bd9b76caa718305f
    27 Nf22398d23c53485ea911a64242239e38
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112774968
    29 https://doi.org/10.1007/s00454-019-00073-2
    30 schema:sdDatePublished 2019-04-11T11:53
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N20cb8d2b01624c7fa3895fff399eb0a6
    33 schema:url https://link.springer.com/10.1007%2Fs00454-019-00073-2
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset articles
    36 rdf:type schema:ScholarlyArticle
    37 N20cb8d2b01624c7fa3895fff399eb0a6 schema:name Springer Nature - SN SciGraph project
    38 rdf:type schema:Organization
    39 N2d2f463c27754685aa197b6105def0d7 schema:affiliation https://www.grid.ac/institutes/grid.261055.5
    40 schema:familyName Striker
    41 schema:givenName Jessica
    42 rdf:type schema:Person
    43 N6e46615d31644dcf823017f71524d209 rdf:first Ncc268ab42324445a87f353445a625fb8
    44 rdf:rest N7a5d228a0bea4b1faa0d89aba7cd68f8
    45 N6fd22773ef944cc6ae8706f4faec7700 schema:name Department of Mathematics and Statistics, UMass, 01003, Amherst, MA, USA
    46 rdf:type schema:Organization
    47 N7a5d228a0bea4b1faa0d89aba7cd68f8 rdf:first Nf10b416188bd431a8d4726d2b27ac7d4
    48 rdf:rest Nbc2096c6560e489b80f2d7b2ac8ec8d0
    49 N8058cf81e727412fb035bcaa5fc5c60a schema:name dimensions_id
    50 schema:value pub.1112774968
    51 rdf:type schema:PropertyValue
    52 Nb0dde6509fcc4703bd9b76caa718305f schema:name doi
    53 schema:value 10.1007/s00454-019-00073-2
    54 rdf:type schema:PropertyValue
    55 Nbc2096c6560e489b80f2d7b2ac8ec8d0 rdf:first N2d2f463c27754685aa197b6105def0d7
    56 rdf:rest rdf:nil
    57 Ncc268ab42324445a87f353445a625fb8 schema:affiliation https://www.grid.ac/institutes/grid.78989.37
    58 schema:familyName Mészáros
    59 schema:givenName Karola
    60 rdf:type schema:Person
    61 Nf10b416188bd431a8d4726d2b27ac7d4 schema:affiliation N6fd22773ef944cc6ae8706f4faec7700
    62 schema:familyName Morales
    63 schema:givenName Alejandro H.
    64 rdf:type schema:Person
    65 Nf22398d23c53485ea911a64242239e38 schema:name readcube_id
    66 schema:value 5ded22ff96a675a666f820603ed6f0d6ad0d760471174ed57189ae32ac2a798d
    67 rdf:type schema:PropertyValue
    68 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Mathematical Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Pure Mathematics
    73 rdf:type schema:DefinedTerm
    74 sg:grant.3089399 http://pending.schema.org/fundedItem sg:pub.10.1007/s00454-019-00073-2
    75 rdf:type schema:MonetaryGrant
    76 sg:grant.3849072 http://pending.schema.org/fundedItem sg:pub.10.1007/s00454-019-00073-2
    77 rdf:type schema:MonetaryGrant
    78 sg:grant.4179262 http://pending.schema.org/fundedItem sg:pub.10.1007/s00454-019-00073-2
    79 rdf:type schema:MonetaryGrant
    80 sg:journal.1043660 schema:issn 0179-5376
    81 1432-0444
    82 schema:name Discrete & Computational Geometry
    83 rdf:type schema:Periodical
    84 sg:pub.10.1007/bf02187680 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048318263
    85 https://doi.org/10.1007/bf02187680
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/bf02575918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014336759
    88 https://doi.org/10.1007/bf02575918
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/s00031-008-9019-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050965400
    91 https://doi.org/10.1007/s00031-008-9019-8
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/s00454-003-2850-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050453872
    94 https://doi.org/10.1007/s00454-003-2850-8
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/s10801-008-0155-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1004488591
    97 https://doi.org/10.1007/s10801-008-0155-y
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/s11856-010-0061-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022750489
    100 https://doi.org/10.1007/s11856-010-0061-6
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1023/a:1008694825493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007605742
    103 https://doi.org/10.1023/a:1008694825493
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0097-3165(83)90068-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035588813
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/s0195-6698(13)80128-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1052692802
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1080/10586458.2000.10504639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049860582
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1093/imrn/rnt212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059691344
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1515/9781400881970-002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000543319
    114 rdf:type schema:CreativeWork
    115 https://www.grid.ac/institutes/grid.261055.5 schema:alternateName North Dakota State University
    116 schema:name Department of Mathematics, North Dakota State University, 58102, Fargo, ND, USA
    117 rdf:type schema:Organization
    118 https://www.grid.ac/institutes/grid.78989.37 schema:alternateName Institute for Advanced Study
    119 schema:name Department of Mathematics, Cornell University, 14853, Ithaca, NY, USA
    120 School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA
    121 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...