Speakers, Titles and Abstracts for BAD Math Day XVI

Abstract: We give an overview of the theory of Macdonald polynomials, focusing on the combinatorial constructions which have arisen in the last few years, where quasisymmetric functions and permutation statistics play an important role.

Abstract: We introduce an analogue of the Solomon descent algebra for the complex reflection groups. Similar to the Solomon descent algebra, our algebra has a basis given by sums of distinguished coset representatives for certain 'reflection subgroups'. We give an explicit combinatorial description of the structure constants with respect to this basis and show that they are polynomials. This allows us to define a deformation, or q-analogue, of these algebras which depend on a parameter q.

This is joint work with Andrew Mathas.

Abstract: The Littlewood-Richardson numbers show up in a number of different areas of mathematics. They are structure constants of the ring of symmetric functions, which connects them to representation theory and cohomology of Grassmannians. There are now several well known combinatorial rules for computing Littlewood-Richardson numbers. I will talk about two of the main ones: the original rule of Littlewood and Richardson, which is phrased in terms of tableaux, and the Knutson-Tao ``puzzle rule'', which looks very different. Most every other known rule is just a variant on one or the other. Yet it is not immediately obvious why these two are rules are the same, or why they are correct. I will give a new construction---mosaics---which interpolates between puzzles and tableaux. Then a miracle will occur: just using the fact that one can interpolate between them, a new and pleasant proof of correctness (for both rules) will appear out of thin air.

Abstract: All known efficient algorithms for computing the determinant of a matrix rely on commutativity of the matrix entries. How important is this property, and could we make use of an algorithm that computes determinants without assuming commutativity? In this talk I will discuss both aspects of this question:
1. If we could efficiently compute the determinant over a sufficiently rich class of non-commutative algebras, then we would get an extremely simple and efficient approximation scheme for the permanent of a 0-1 matrix (which is a central hard combinatorial problem).
2. The algebraic branching program complexity of the determinant over almost any non-commutative algebra is exponentially large.
If one is a pessimist, these results suggest that non-commutative determinant computation would be nice but is hopelessly hard. If one is an optimist, they represent a challenge to devise a new approximation scheme for the permanent.

Joint work with Steve Chien and Lars Rasmussen.

Abstract: In this talk, we introduce online optimization, a methodology for decision making under uncertainty, where probabilistic distributions are not available. We then discuss two applications of online optimization in the area of operations research: (1) the Traveling Salesman Problem (TSP) and (2) Inventory Control.

Abstract: We discuss a simple idea in the analysis of high dimensional data using long increasing sequences under a natural partial order. The motivating example is from current human genetic research: Biologists are exploring ways to predict the behavior of a cell (for example, a brain cell or a white blood cell) based on patterns of gene transcription. Gene transcription is an intricate cellular process in which a specific segment of the DNA code (i.e. a 'gene') is used as a template to produce a specific RNA molecule. At each moment the cell needs to decide (intelligently in a certain sense, in respond to its internal conditions as well as external environment) which genes to turn up or down (speed up or slow down transcription). This choice need to be made continuously and simultaneously for tens of thousands of genes, with significant consequences: the resulting pool of RNA molecules are translated into a pool of proteins which collectively define the biological role of the cell. A popular research technique is to extract the RNA content of a cell and examine the relative transcription abundance of all known genes. This results in a 'gene transcription profile' of the cell. A typical gene transcription data set is a large matrix containing tens of thousands of rows (corresponding to genes) and hundreds of columns (corresponding to cell samples to be compared with each other). We look at this data as n points in a m-dimensional space, where n is the number of genes and m is the number of samples. One of the simplest transcription patterns one could formulate is 'gene X is more abundant than gene Y in every sample', which naturally leads to the consideration of the partial order defined by 'X is larger than Y if every coordinate of X is larger than the corresponding coordinate of Y'. A totally ordered subset of sufficient size (long increasing sequence) under this partial order is a very useful pattern, and will be the main theme of this talk. This idea is closely related to the well-known classical work on longest increasing subsequences in a permutation, but with some differences: First, the increasing sequence need not have the longest possible length; Second, our starting point is a point set, not a sequence, therefore the formulation is in terms of subsets, not subsequences; Third, we work with a partially-ordered set instead of a well-ordered set.

This is joint work with Susan Holmes and Peter Lee.