This thesis is about a generalization of permutation theory. The concept of pattern avoidance in permutation matrices is investigated in a larger class of matrices – the alternating sign matrices. The main result is that the set of alternating sign matrices avoiding the pattern 132, is counted by the large Schröder numbers. An algebraic and a bijective proof is presented. Another class is shown to be counted by every second Fibonacci number. Further research in this new area of combinatorics is discussed…
Contents
1 Introduction
2 Basic concepts
3 The alternating sign matrices
3.1 Introduction
3.2 Determinants and permutations
3.3 Dodgson’s condensation
3.3.1 The algorithm
3.4 λ-determinants and alternating sign matrices
3.5 The ASM conjecture
3.6 The proof
4 Pattern avoidance in permutations
4.1 Introduction
4.2 Counting Sn(132)
4.2.1 The Catalan numbers
4.2.2 Proofs that Sn(132) are counted by the Catalan numbers
4.3 Counting Sn(123)
4.3.1 A bijection to Dyck paths
4.4 Current research on pattern-avoiding permutations
5 Pattern avoidance in alternating sign matrices
5.1 Introduction
5.2 Counting pattern-avoiding alternating sign matrices
5.3 Counting An(132)
5.3.1 The large Schr¨oder numbers
5.3.2 A bijection to Schr¨oder paths
5.4 Counting An(123)
5.5 Counting alternating sign matrices avoiding two different pat-terns of order three
5.5.1 Counting An(132, 123) and An(132, 213)
5.5.2 Counting An(132, 231)
5.5.3 Counting An(132, 321)
5.5.4 Summary of all classes
5.6 Discussion and future research
Author: Johansson, Robert
Source: Linköping University
Download URL 2: Visit Now