## Bay Area Discrete Math Day XVII, Fall 2008

### Saturday, September 27, 2008

The Seventeenth Bay Area Discrete Math Day (BADMath Day), sponsored by D.E. Shaw & Co., will take place at Stanford University on Saturday, September 27, 2008 between 10:00 AM and 5:00 PM.

We will meet in Bldg. 370, Rm. 370, which is on the main quad. A link to a campus map can be found here.

BADMath Days are one-day meetings aimed at facilitating communication between researchers and graduate students of discrete mathematics around the San Francisco Bay Area. These days happen twice a year and strive to create an informal atmosphere to talk about discrete mathematics. The term "discrete mathematics" is chosen to include at least the following topics: Algebraic and Enumerative Combinatorics, Additive Combinatorics, Discrete Geometry, Graph Theory, Coding and Design Theory, Combinatorial Aspects of Computational Algebra and Geometry, Combinatorial Optimization, Probabilistic Combinatorics, Combinatorial Aspects of Statistics, and Combinatorics in Mathematical Physics.

## Directions and parking

Full directions to the Stanford University math department (building 380, also known as Sloan Hall) can be found here. Your best bet for parking is to park in the Oval, free and generally available on weekends. If this should prove to be full for some reason, there are several parking lots nearby. Getting to the Oval is simple: get on 101, take the University Avenue exit towards Palo Alto (southwest), and follow University all the way to its end (it will turn into Palm Drive.) From 280, take the Sand Hill Road exit towards Stanford, then take a right on El Camino and a right on University (this will involve taking a ramp.)

## Carpooling and public transportation

We will have more carpool information soon, but if you are interested in carpooling, for the moment contact your local organizer. We'd especially love volunteers to drive!

If you prefer to take public transportation, Caltrain conveniently stops at the edge of Stanford's campus (the downtown Palo Alto stop.) From this stop, it is about a 10- to 15-minute walk to the math building: just walk southwest on University/Palm through campus. There is a Caltrain leaving San Francisco at 8:00 and arriving at PA at 9:02 AM. From the East Bay, there is no good option since the Dumbarton Express (a bus from the Fremont BART) does not run on weekends. We recommend driving, but if this is completely out of the question, BART to Millbrae to pick up the Caltrain is theoretically possible.

## Registration

There is no registration fee, but please register with the local organizer, Matt Kahle (mkahle [at] math dot stanford dot edu), on or before September 20. This is essential so we know how much food to get for lunch. If you do not pre-register, you will not have any food, and we will be very mad at you. In your RSVP, please include any dietary restrictions you may have (vegetarian, etc.), as well as whether or not you will be attending dinner afterwards.

## Speakers

We have a fantastic lineup of speakers. The schedule for BADMath Day XVII is as follows:

## Titles & abstracts

Eric Babson: Graph homomorphisms

The talk will focus on homomorphisms between graphs. There are three basic questions which have been addressed here and they have been studied with a variety of techniques. First are questions relating structural facts about the homomorphisms into one graph to the existence of homomorphisms into another. The structural facts which have been studied include topological, metric and measure theoretic ones and the upshot has been a lower bound on chromatic number. It is notable that the different methods have produced very similar, but different, results. Second is the question of the complexity of testing for the existence of a map. For this question there has been work relating these complexities to the same question for related structures. One resulting theorem is that for graphs the problem of testing for a map into a fixed graph is always either np complete or polynomial time. Third is the question of counting the maps between two graphs. This is closely related to the generalized birthday problem and has been studied via linear algebraic and statistical methods. One theorem here characterizes the possible functions counting maps from graphs into a fixed target graph.

Brendon Rhoades: Fixed Point Enumeration and Ribbon Operators

Using plethystic operators of Lascoux, Leclerc, and Thibon, we answer a question of Reiner, Stanton, and White regarding fixed point enumeration for the action of cyclic row and column rotation on certain finite sets of matrices. Our fixed point results are stated using the bicyclic sieving phenomenon, defined in a 2008 paper of Barcelo, Reiner, and Stanton. Using similar methods, we also obtain a module isomorphism due to Morita and Nakajima.

Chris Peterson: Inexact methods for exact results

In this talk I hope to illustrate, in very concrete terms, the essence (and utility) of generic points on algebraic varieties. The connection to Discrete Mathematics is through a warm-up example using continued fractions and a more souped up version using "lattice basis reduction". A very brief reference to aliens will also be included.

Brant Jones: Pattern avoidance enumeration and heaps of pieces

Several disparate phenomena have been characterized by permutation pattern avoidance including: stack sortability in computer science, geometric information about Schubert varieties, and properties of the set of reduced words of a permutation. In this talk, we will discuss an approach for enumerating certain classes of pattern-avoiding permutations using partial orders called heaps that have been introduced by Viennot and Stembridge. This is joint work with Hugh Denoncourt.

Glenn Appleby: Invariants of Matrix Pairs over Discrete Valuation Rings and Littlewood-Richardson Fillings

Suppose $\mu$ is the partition of (orders of) the invariant factors of an $n \times n$ matrix $M$ over a discrete valuation $R$ of characteristic zero. Suppose $\nu$ is the partition associated to $N$ and $\lambda$ the partition for the product $MN$. It is known in this case that the Littlewood-Richardson coefficient $c_{\mu \nu}^{\lambda}$ is non-zero, and that this coefficient can be enumerated combinatorially by Littlewood-Richardson fillings of the skew-shape $\lambda / \mu$ with content $\nu$. Recent work shows that these combinatorially defined fillings actually form natural matrix invariants. In fact, we can find matrix realizations that interpret such fillings (so that, for instance, each orbit of a matrix pair under a natural group action determines a unique filling), as well as bijections between fillings (that establish the equality $c_{\mu \nu}^{\lambda} = c_{\nu \mu}^{\lambda}$ and also other combinatorially defined procedures defining and calculating Littlewood-Richardson coefficients. The determinantal formulas we obtain for these combinatorial objects suggest other generalizations of Littlewood-Richardson-like phenomena.

Ben Green: Some themes in Additive Combinatorics

I will introduce some of the main themes in additive combinatorics. Specifically, I will introduce the Gowers norms and the "inverse conjectures" concerning them, as well as the circle of questions surrounding Freiman's theorem on the structure of sets with small doubling.

## Food

Lunch (free) will be provided on-site. There will be a conference dinner, generously sponsored by D.E. Shaw & Co.; this will be held at Ming's (see above link.) Everyone is very much invited to attend dinner (typically most of the conference does so.) Both meals will be vegetarian- and vegan-friendly, but please e-mail Matt (mkahle [at] math dot stanford dot edu) with any dietary restrictions you have and for a headcount on how many vegetarian meals to order.