Alternating sign matrices and tournaments

DOI10.1006/AAMA.2001.0737MaRDI QIDQ5956769zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robin Chapman

Publication date 8 August 2002

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0008029

zbMATH Keywords

alternating sign matrixbijective proofcomplete monotone trianglesix vertex modelsquare ice modeltournament

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Directed graphs (digraphs), tournaments (05C20)

Abstract: We settle a question of Bressoud concerning the existence of an explicit bijection from a class of oriented square-ice graphs to a class of tournaments. We give an algorithm constructing such a bijection.

Review text

An alternating sign matrix is a square matrix of entries from \(\{-1,0,1\}\) with the property that in any row or column the entries sum to 1 and the non-zero entries alternate in sign. A tournament is an orientation of the complete graph. An upset in a tournament is an edge directed from a higher numbered vertex to a lower numbered vertex. This paper answers a challenge laid down by Bressoud in the same volume; see \textit{D. M. Bressoud} [Adv. Appl. Math. 27, No. 2-3, 289-297 (2001; Zbl 0990.05001)]. Namely, it gives a bijective proof of a particular identity relating the alternating sign matrices of order \(n\) to the upsets in tournaments on \(n\) vertices.NEWLINENEWLINENEWLINEThe proof makes clever use of orientations of complete monotone triangles. These are triangular arrays in which (i) the \(k\) entries in the \(k\)th row are strictly increasing, (ii) the final row is \(1,2,3,\dots,n\) and (iii) entries in other rows lie weakly between their two neighbours in the row below.

Recommendations

• Three alternating sign matrix identities in search of bijective proofs
• scientific article; zbMATH DE number 4066905
• Some Combinatorially Defined Matrix Classes
• The poset perspective on alternating sign matrices
• A unifying poset perspective on alternating sign matrices, plane partitions, Catalan objects, tournaments, and tableaux

Cites work

• A complementation theorem for perfect matchings of graphs having a cellular completion
• Alternating-sign matrices and domino tilings. I
• Determinants and alternating sign matrices
• scientific article; zbMATH DE number 1380572 (Why is no real title available?)
• Three alternating sign matrix identities in search of bijective proofs

Cited in

(4)

• Alternation acyclic tournaments
• Multiply-refined enumeration of alternating sign matrices
• Three alternating sign matrix identities in search of bijective proofs
• Bijective proofs of shifted tableau and alternating sign matrix identities

This page was built for publication: Alternating sign matrices and tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956769)