Name
Abstract | ||
|---|---|---|
The set Sn of nn permutation matrices forms a ranked partially ordered set under the Bruhat order. The Bruhat order on Sn can be equivalently defined by means of an entrywise partial order on an associated matrix. Lascoux and Schtzenberger proved that the MacNeille completion (the unique smallest lattice containing a partially ordered set) of the Bruhat order on Sn is the set An of nn alternating sign matrices (ASMs) with a partial order defined by this same entrywise order giving a ranked lattice. We continue investigations of the structure of this lattice. We show that the lattice contains some special dense ASMs defining intervals which are Boolean lattices which together span (in terms of hitting all ranks) the lattice from its minimal element to its maximal element. We also show that the number of ASMs of a given rank is a polynomial in n of degree r and obtain a natural maximal saturated chain. The Hasse diagram of a poset can be regarded as a (directed) graph, and we determine the maximal indegree, outdegree, and total degree of ASMs in An; a similar determination was done by Adin and Roichman for the Bruhat order on Sn. The join-irreducible permutations in Pn are the bigrassmanians, that is, permutations such that both and its inverse 1 have exactly one descent. The bigrassmanians are also the join-irreducible elements of the lattice on An. We determine the minimal set of bigrassmanians whose joins are the special dense ASMs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.10.010 | Discrete Mathematics |
Keywords | Field | DocType |
Permutations,Bigrassmanians,Alternating sign matrices (ASMs),Bruhat order | Discrete mathematics,Combinatorics,Bruhat order,Lattice (order),Matrix (mathematics),Permutation,Hasse diagram,Permutation matrix,Maximal element,Partially ordered set,Mathematics | Journal |
Volume | Issue | ISSN |
340 | 8 | 0012-365X |
Citations | PageRank | References |
1 | 0.40 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard A. Brualdi | 1 | 389 | 95.40 |
| Michael W. Schroeder | 2 | 22 | 4.37 |