# 2007 Kemeny Lecture Series

## Increasing and decreasing subsequences

### (Tea 3:30 pm 300 Kemeny Hall)

Abstract: A subsequence a_{i_1},\dots,a_{i_k} of a permutation a_1,a_2,\dots, a_n of 1,2,\dots, n is increasing if a_{i_1}. A decreasing subsequence is similarly defined. We will survey the subject of increasing and decreasing subsequences, focusing on what can be said about the longest increasing and longest decreasing subsequence of a permutation. Topics will include (a) the relationship to Young tableaux and the famous RSK algorithm, (b) the asymptotic behavior of the length of the longest increasing subsequence (due to Baik, Deift, and Johansson), (c) connections with random matrix theory, and (d) an extension of the theory from permutations to complete matchings.

Note:
This talk will be accessible to graduate students.

## A Survey of Plane Tilings

### 008 Kemeny Hall

Abstract:We will survey some of the highlights of the theory of plane tilings, focusing on tiling a bounded region of the plane with finitely many tiles. A standard example, though not very mathematical, is a jigsaw puzzle. We consider such questions as the following: (1) Is there a tiling? (2) How many tilings are there? (3) About how many tilings are there? (4) Is a tiling easy to find? (5) Is it easy to prove or to convince someone that a tiling doesn't exist? (6) What does a typical tiling look like? We point out some interesting connections between tilings and such topics as computer science, continued fractions, probability theory, and mathematical logic.

Note: This talk is for a general audience and will be accessible to undergraduates.

NB: A PDF version of this announcement (suitable for posting) is also available.

## Alternating permutations

### 006 Kemeny Hall

Abstract: A permutation a_1,a_2,\dots,a_n of 1,2,\dots,n is \emph{alternating} if a_1>a_2a_4<\cdots. The number of alternating permutations of 1,2,\dots,n is denoted E_n and satisfies

\sum_{n\geq 0}E_n\frac{x^n}{n!} =\sec x +\tan x.

After a survey of the basic properties of alternating permutations and the subject of combinatorial trigonometry,'' we will discuss recent work in two areas : (a) distribution of the length of the longest alternating subsequence of a permutation of 1,2,\dots,n, and (b) enumeration of various classes of alternating permutations of 1,2,\dots,n (such as those that are involutions) using techniques from symmetric functions.

Note: This talk will be accessible to graduate students.

NB: A PDF version of this announcement (suitable for posting) is also available.