. 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
Thursday, May 3, 2007
7:00 -- 8:00 pm
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
Friday, May 4, 2007
2:00 - 3:00 pm
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.
