The SPAMS Schedule - Fall 2002

What is common among a gas, a ferromagnet, the brain, the lines at the post office in beautiful Italy? They can all be described with similar mathematical models, known as "interacting particle systems". In the talk I will give a brief introduction to the theory of interacting particle systems, describing in some detail the stochastic dynamics and the hydrodynamic limit of one of them: the zero range model.

Have you ever wanted a basic introduction to finance and investment science? Have you ever wondered why financial firms started hiring mathematicians and physicists to solve PDE? I will give an introduction to fundamental concepts like risk aversion, arbitrage, and linear pricing. From these concepts, I will discuss how they can be used to understand options and their prices which will then motivate an non-rigorous introduction to the Black-Scholes Equation.

Back in 1971, a student of Gian-Carlo Rota by the name of Richard Stanley graduated from Harvard with a Ph. D. thesis entitled "Ordered Structures and Partitions". Among many other things, the thesis contains a conjecture which brings together symmetric functions and partially ordered sets. Despite its innocent appearance, this conjecture remains very much an open problem.

We will give the necessary background, which is good to know in its own right, and tell some more of the story of the conjecture. I'll also discuss my own love-hate relationship with this problem.

In the nineteenth century Louis Pasteur, studying fermentation of grape juice by yeast, and Gregor Mendel, studying heredity in pea plants, began the fields of biochemistry and genetics. In the twentieth century they were united when DNA was discovered to be the molecular carrier of genes.

For biology, the twenty-first century will be the century of computation. With the biochemical description of a gene in hand, computational biologists have already begun scanning sequenced genomes to predict which parts encode for proteins. A genome and its proteins can be modeled as chosen from a probability measure in the class of stochastic regular languages. Such a "Hidden Markov Model" is exactly the tool upon which modern gene-finding programs are based.

Catalan numbers are back.

Matroids are back.

This time, they're together.

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena recently gave the most exciting result in the theory of computation in ten years, namely the first provably efficient algorithm for testing whether a number is prime.

I will give the algorithm and its simple proof. No real knowledge of algorithms or number theory is required.

Since the beginning of times, men always wanted to know about the teleportation of Quantum-bit. In this talk, we will first discuss briefly about quantum information and then explain why it is possible from a theoretical point of view to teleport a Quantum-bit.

Warning: Fans of Star Trek might be bitterly disappointed.

It is clear that you can cover an 8x8 chessboard with dominoes (1x2 or 2x1 rectangles) without any overlap. An old combinatorial game/problem asks whether you can still do so if you removed two opposite corners from the chessboard. Using a very little bit of commutative algebra, I'll give a vast generalisation of this tiling problem and also discuss exactly when the solution can be generalised. This is joint and ongoing work with Ezra Miller and Igor Pak.

Formal concept analysis is a (REALLY SCARY) way of thinking about (HORRIFIC) qualitative data. As such, it has (MONSTROUS) applications to (TERRIFYING THINGS LIKE) information retrieval and classification, automated learning, and the meaning of life. I will tell you some of the (FRIGHTENING) basic ideas and how (DEMONIC) complete lattices arise (SUPER)naturally in this context.

I realize that coming to this talk would severely reduce your quality trick-or-treating time. FEAR NOT, for your loyalty shall be rewarded.

Concepts such as fixed points or excedances in permutaTions arise wHen we look at them As bijectIons FrOm {1,2,...,n} tO {1,2,...,n}. On the other hanD, pattern-avoidance appears when we consider a permutAtion as a word. It was not until a Few months ago That these two concepts wERe studied together. It was noticed that the classical result saying that the number of 321-avoiding permutations (i.e., not containing any decreasing subsequence of length three) equals the number of 132-avoiding permutations can be refined by restricting to permutations having any given number of fixed points.

A few days ago we were able to prove a furTHEr refinement of this result. No bijective proofs of these refinemenTs Are known (yet), but there are some interesting bijections invoLving DycK paths that come up.

This abstract contains one reason why you should come to the talk.

The van der Waerden theorem in Ramsey theory states that for every k and t and sufficiently large N, every k-coloring of [N] contains a monochromatic arithmetic progression of length t. Motivated by this result, I conjectured some time ago that every equinumerous 3-coloring of [3n] contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are colored with distinct colors. The conjecture is still open. I will show that every 3-coloring of the set of natural numbers for which each color class has density more than 1/6, contains a 3-term rainbow arithmetic progression.

I will discuss similar results for colorings of Z_n and try to give a general perspective on other "anti-Ramsey-type" problems that can be considered.

If time and audience permits, I might show some other recent raves in Ramsey theory.

Vector algorithms allow the computation of an output vector given an input vector in a bounded number of operations, "independent" of 'm' the length of the vectors. These algorithms can thus be implemented in parallel, and/or, with bit-wise operations available in processors, leading to highly efficient computations.

These algorithms are usually derived from an input-output automaton that models a computation, but they often use specific properties of its transition table in order to produce an efficient algorithm. It is thus natural to ask whether there is a general way to construct them.

We will identify a class of automata, the "solvable" automata, for which we can prove the existence of bit-vector algorithms. This will allow us to show that efficient algorithms exist for the problem of approximate string matching with arbitrary weighted distances.

I would like to expand David Vener's introduction to arbitrage pricing of financial derivatives (claims) with an emphasis on the probability and measure theory as an apparatus in solving these problems.

One of the central concepts in the theory is the equivalent martingale measure, under which all securities prices processes are martingales. It can be shown that the no-arbitrage assumption is equivalent to the existence of such a measure.

In the theory of option pricing, most often, one takes as given the price dynamics of some traded securities (such as stocks and bonds). From this and the no-arbitrage assumption alone he tries to determine prices of other contingent claims (which are functions of the above securities prices). Another interesting problem to address is to determine the range of possible values for the price of a given claim based only on the prices of other traded claims and the no-arbitrage assumption, but with no assumption on the model for the price dynamics of the underlying asset.