Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Aztec Diamonds and Baxter Permutations"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Aztec Diamonds and Baxter Permutations. | Aztec Diamonds and Baxter Permutations Hal Canary Mathematics Department University of Wisconsin-Madison h3@halcanary.org Submitted Jul 19 2009 Accepted Jul 31 2010 Published Aug 9 2010 Mathematics Subject Classifications 52C20 05A19 Abstract We present a proof of a conjecture about the relationship between Baxter permutations and pairs of alternating sign matrices that are produced from domino tilings of Aztec diamonds. It is shown that a tiling corresponds to a pair of ASMs that are both permutation matrices if and only if the larger permutation matrix corresponds to a Baxter permutation. There has been a thriving literature on both pattern-avoiding permutations of various kinds Baxter 1964 Dulucq and Guibert 1988 and tilings of regions using dominos or rhombuses as tiles Elkies et al. 1992 Kuo 2004 . However there have not as of yet been many links between these two areas of enumerative combinatorics. This paper gives one such link. 1 Introduction Figure 1 shows two of the 64 different ways of tiling an order three Aztec diamond with dominoes. Aztec Diamonds are defined in Alternating-Sign Matrices and Domino Tilings by Elkies Kuperberg Larsen and Propp 3 . Each tiling will be referred to as a TOAD a Tiling Of an Aztec Diamond. In all of the illustrations we have rotated the Aztec Diamonds and drawn spurs on each corner to simplify later calculations. An Alternating Sign Matrix ASM is a square matrix whose entries are 0 1 or 1 such that the entries of each row or column must add up to 1 and all nonzero entries must alternate in sign. Examples 0 1 1 0 0 0 0 1 0 1 0 00 0 0 01 1 1 10 0 1 00 Current address c o James Propp Department sachusetts Lowell Lowell MA 01854. of Mathematical Sciences University of Mas- THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R105 1 Figure 1 Two examples of tilings of Aztec diamonds. Elkies Kuperberg Larsen and Propp showed that there are 2ra ra 1 2 tilings of an order n Aztec diamond with dominoes 3 . As part of their proof they .