MIT-Harvard-MSR Combinatorics Seminar

Schedule 2005 Spring

February 9

Michael Mitzenmacher, Harvard University

The Power of Two Choices: Some Old Results and New Variations (PDF)

February 11

Sharad Goel, Cornell University

Mixing Times For Top To Bottom Shuffles (PDF)

February 16

Yuri Rabinovich, Univesity of Haifa

Local Versus Local Properties Of Metric Spaces (PDF)

February 18

Greg Blekherman, University of Michigan Ann Arbor

Convex Geometry Of Orbits (PDF)

February 23

Kyle Petersen, Brandeis University

Descents, Peaks and P-Partitions (PDF)

February 25

Sergi Elizalde, MSRI

Inference Functions And Sequence Alignment (PDF)

March 2

Jonathan David Farley, Harvard University

Posets With The Same Number Of Order Ideals Of Each Cardinality: A Problem From Stanley's Enumerative Combinatorics

In Richard P. Stanley's 1986 text, {\sl Enumerative Combinatorics\/}, the following problem is posed: Fix a natural number $k$. Consider the posets $P$ of cardinality $n$ such that, for $0<i<n$, $P$ has exactly $k$ order ideals (down-sets) of cardinality $i$. Let $f_k(n)$ be the number of such posets. What is the generating function $\sum f_k(n) x^n$?

We solve this problem. (Joint work with Ryan Klippenstine.)

March 4

Michael Shapiro, Michigan State University

Cluster Algebras of Finite Mutation

Coordinate rings of some natural geometrical objects (for example, Grassmannians) possess distinguished sets of generators (Plucker coordinates). Cluster algebras are generalizations of such coordinate rings. Sets of generators of a cluster algebra are organized in a tree-like structure with simple transformation rules between neighboring sets of generators.

Fomin and Zelevinsky obtained a complete classification for cluster algebras of finite type (i.e., with finite number of generators). This classification coincides with the Cartan-Killing classification of simple Lie algebras. We try to describe cluster algebras with finitely many transformation rules, so called cluster algebras of finite mutation type. We prove that a special class of cluster algebras originating from triangulation of Riemann surfaces is of finite mutation type.

This is joint work with Sergey Fomin.

March 9

James Propp

The Combinatorics Of Markoff Numbers

March 11

Alexander Yong, Berkeley

On Smoothness and Gorensteinness of Schubert Varieties

Schubert varieties are classical objects of study in algebraic geometry; their study often reduces to easy-to-state combinatorial questions.

Gorensteinness is a well-known measure of the "pathology" of the singularities of an algebraic variety. Gorensteinness is a condition that is logically weaker than smoothness but stronger than Cohen-Macaulayness.

We present a non-recursive, combinatorial characterization of which Schubert varieties in the flag variety are Gorenstein. Our answer is in terms of generalized permutation pattern avoidance conditions.

I'll explain the algebraic geometric and representation (Borel-Weil) theoretic applications of this work. I will also describe further combinatorial questions.

This is a joint project with Alexander Woo, see math.AG/0409490.

March 16

Yuval Roichman, BIU and UCSD

Statistics on Permutation Groups, Canonical Words and Pattern Avoidance

The number of left to right minima of a permutation is generalized to Coxeter (and closely related) groups, via an interpretation as the number of "long factors" in canonical expressions of elements in the group.

This statistic is used to determine a covering map, which 'lifts' identities on the symmetric group $S_n$ to the alternating group $A_{n+1}$. The covering map is then extended to 'lift' known identities on $S_n$ to new identities on $S_{n+q-1}$ for every positive integer $q$, thus yielding $q$-analogues of the known $S_n$ identities.

Equi-distribution identities on certain families of pattern avoiding permutations follow. The cardinalities of subsets of permutations avoiding these patterns are given by extended Stirling and Bell numbers. The dual systems (determined by matrix inversion) have combinatorial realizations via statistics on colored permutations.

Joint with Amitai Regev.

March 18

Egon Schulte, Northeastern University

Reflection Groups and Polytopes Over Finite Fields

Any Coxeter group G with string diagram is the automorphism group of an abstract regular polytope (typically infinite). When G is crystallographic, its standard real representation is easily reduced modulo an odd prime p, thus giving a finite representation in some finite orthogonal space V over $\Bbb F_p$. The finite group need not be polytopal; and whether or not it is depends in an intricate way on the geometry of V. The talk presents recent work with Barry Monson, in which we describe this construction in considerable generality and study in depth the interplay between the geometric properties of the polytope (if it exist) and the algebraic structure of the overlying finite orthogonal group. As a byproduct, we obtain many new maps on surfaces and even more interesting polytopes of higher rank.

March 30

Seunghyun Seo, Brandeis University

A Generelized Enumeration of Labeled Trees

In this talk, we'll give a simple combinatorial explanation of a formula of A. Postnikov relating bicolored rooted trees to bicolored binary trees. We'll also present generalized formula for the number of labeled k-ary trees, rooted labeled trees, and labeled plane trees. Combinatorial explanations of these formulas will be discussed too.

This is joint work with Ira Gessel.

April 1

Benny Sudakov, Princeton University

Dependent Random Choice and Ramsey-Turan Type Problems

The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics and it belongs to those areas of mathematical research that have experienced a most impressive growth in recent years. One of the parts of discrete mathematics where this approach has proved to be especially useful is Extremal Combinatorics. In fact, many of the strongest results in this area in the last few decades are examples of this method.

In this talk we discuss a few recent applications of this methodology. In particular, we present simple but yet surprisingly powerful probabilistic arguments which were used recently to make progress on some long-standing Ramsey and Turan type problems.

April 6

Lauren Williams, Massachusetts Institute of Technology

Bergman Complexes, Coxeter Arrangements, and Graph Associahedra

The Bergman complex B(M) and the positive Bergman complex B+(M) of an oriented matroid M generalize to matroids the notions of tropical varieties and positive tropical varieties. Our main result is that if M is the oriented matroid of a Coxeter arrangement, then B(M) equals the nested set complex of that arrangement, and B+(M) is dual to the corresponding graph associahedron. This recovers Carr and Devadoss' tiling of the minimal blowup of a Coxeter complex by graph associahedra.

This is joint work with Federico Ardila and Vic Reiner.

April 8

Thorsten Theobald, TU Berlin and Yale University

Combinatorial Aspects of Tropical Geometry

Tropical geometry is the geometry of the tropical semiring $(\mathbb{R}, \min, +)$. Tropical varieties are polyhedral cell complexes which behave like complex algebraic varieties. The link between classical complex geometry and tropical geometry is provided by amoebas, which are logarithmic images of complex varieties.

In this talk, we begin with a combinatorially oriented review of some fundamental concepts in tropical geometry (aimed at a general audience), and then we turn towards some algorithmic problems concerning the intersection of tropical hypersurfaces in general dimension: deciding whether this intersection is nonempty, whether it is a tropical variety, and whether it is connected, as well as counting the number of connected components. We characterize the borderline between tractable and hard computations by proving NP-hardness and #P-hardness results even under various strong restrictions of the input data, as well as providing polynomial time

April 13-15

Noga Alon, Tel Aviv University & IAS

Structures and Algorithms in External Combinatorics (Simons Lectures)

  1. Ramsey Theory: Motivation, Results and Challenges
  2. The Structure of Graphs and Grothendieck Type Inequalities
  3. Property Testing and Approximation Algorithms

April 20

Peter Cameron, University of London

Tutte Polynomial and Orbit Counting

Many counting problems for graphs, codes, etc. are solved by appropriate specialisations of the Tutte polynomial. Suppose that we have a group of automorphisms of the structure in question, and we want to count orbits of this group acting on the appropriate objects. Is there a polynomial which does this? Two such polynomials have been proposed; the first combines the cycle index of the group with the Tutte polynomial, the second directly generalises the Tutte polynomial itself. The second example works only for matroids representable over a principal ideal domain, and is a multivariate generating function for the invariant factors of certain matrices.

April 27

Derek Smith, Lafayette College

A Family of Configurations From Quantum Logic

This broadly-accessible talk will introduce certain finite collections of vectors in $2n$-dimensional Euclidean space with combinatorial and geometrical properties that are useful in the study of quantum logic. These configurations generalize the $4$-dimensional configurations employed by Peres (1993), Navara and Pt\'{a}k (2004), and others in various treatments of the Kochen-Specker theorem. We will discuss applications, including the characterization of certain group-valued measures on the closed subspaces of Hilbert space, and we will conclude with several open problems.

This work is joint with John Harding and Ekaterina Jager.

April 29

David Gamarnik, IBM

Applications of the Local Weak Convergence Method to Random Graph Problems

Local Weak Convergence method (LWC) exploits local structure (typically a tree) of a large random combinatorial object and leads to a complete asymptotic solutions to several optimization problems on random graphs. The method reduces the original problem into the problem of finding fixed points of a certain distributional operator. We show that when the fixed point of the second iterate of the distributional operator is unique, it determines the value of the underlying combinatorial optimization problem.

May 4

Martin Kassabov, Cornell University

Symmetric Groups and Expanders

A finite graphs with large spectral gap are called expanders. These graphs have many nice properties and have many applications. It is easy to see that a random graph is an expander but constructing an explicit examples is very difficult. All known explicit constructions are based on the group theory --- if an infinite group G has property T (or its variants) then the Cayley graphs of its finite quotients form an expander family.

This leads to the following question: For which infinite families of groups G_i, it is possible to find generating sets S_i which makes the Cayley graphs expanders?

The answer of the question is known only in few case. It seems that if G_i are far enough from being abelian then the answer is YES. However if one takes 'standard' generating sets the resulting Cayley graphs are not expanders (in many cases).

I will describe a recent construction which answers the above question in the case of the family of all symmetric/alternating groups. It is possible to construct explicit generating sets S_n of Alt_n, such that the Cayley graphs C(Alt_n,S_n) are expanders, and the expanding constant can be estimated.

Unlike the usually constructions of expanders, the proof does not use an infinite group with property T (although such group exists) but uses the representation theory of the symmetric groups directly.

May 11

József Solymosi, UBC

On The Number Of Sums And Products (PDF)


All announcements since Fall 2007 are in the Google Calendar