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