MIT-Harvard-MSR Combinatorics Seminar

Schedule 1995 Fall

Organizer: Jim Propp

Wednesday, September 20, 4:35 p.m.; MIT, room 2-338

Joseph Bonin (GWU and MIT)

Matroids with no (q+2)-point-line minors

We are concerned with U(q), the class of matroids containing no minor isomorphic to the (q+2)-point line. This class is of interest in part because of its connections with representability questions and its role in extremal matroid theory, in particular, in connection with size functions.

For any prime power q, L(q) is a subset of U(q), where L(q) is the class of matroids representable over GF(q). In 1958, Tutte proved that L(2) = U(2). We will give a new proof of Tutte's theorem and sketch several other applications of the techniques used.

For prime powers q>2, the (q+2)-point line is not the only excluded minor for GF(q)-representability. However, we show that with enough points in a geometry, the (q+2)-point line is the only minor one must exclude to guarantee that the geometry is representable over GF(q). Indeed, such geometries are uniquely representable over GF(q). We will apply these ideas to bound the size function of U(q) and to obtain a simple counting characterization of affine space.

Friday, September 22, 4:35 p.m.; MIT, room 2-338

William Jockusch

Antisymmetric monotone triangles and domino tilings of quartered Aztec diamonds

In earlier work it was shown that the Aztec diamond of order n has 2^{n(n+1)/2} domino-tilings, and connections were established with monotone triangles and alternating sign matrices. In this talk I will describe follow-up work that establishes formulas for the number of domino-tilings of a ``quarter'' of an Aztec diamond of order n, with different formulas depending on exactly how the quartering is done as well as on the residue of n mod 4.

This turns out to be a special case of a more general enumeration problem, where the number of domino-tilings of a certain kind of region is always equal to a power of 2 times the dimension of a particular representation of a Lie algebra. Our method of proof uses a weighted count of certain sorts of monotone triangles. Interestingly, if one considers other enumeration problems for these monotone triangles, one gets conjectural product-formulas that generalize earlier conjectures of Mills, Robbins and Rumsey.

This is joint work with Jim Propp.

Friday, September 29, 4:35 p.m.; MIT, room 2-338

Karen Collins (Wesleyan)

Symmetry breaking in graphs

A classic elementary problem with a surprise answer is the following: if a circular key ring holds n identically shaped keys, and in order to tell them apart, we plan to affix to each one a colored label, what is the minimum number of different colors needed to distinguish the keys? The surprise is that if n is at least 6, there need only be 2 different colors of labels; but if there are three, four, or five keys on the ring, there must be 3 different colors of labels. If we consider the keys as vertices in the n-cycle, then the effect of the labels on the vertices is to destroy every symmetry of the n-cycle.

Define a labeling of a graph G, l:V(G) --> {1,2,...,r}, to be _r-distinguishing_ if no automorphism of G preserves all of the vertex labels. Then a natural question is, for any graph G, what is the minimum r such that G is r-distinguished? For an n-cycle, the answer is 3 if n=3,4,5 and 2 if n is at least 6. For a complete graph on m vertices, the answer is m. We give a bound on the minimum distinguishing number of a graph in terms of the order of its automorphism group, as well as finding the distinguishing numbers of graphs whose automorphism groups are abelian, dihedral, S_3, or S_4.

This is joint work with Michael Albertson.

AMS meeting at Northeastern, October 7 & 8

Participants in the MIT combinatorics seminar may be interested in attending the special session on "Representation Theory and Combinatorics" that will be held at Northeastern University as part of the AMS regional meeting on October 7 and 8.


            Saturday, October 7

            8:30 am   C. Kenneth Fan (Harvard University)
            9:00 am   Peter Magyar (University of Utrecht)
            9:30 am   Mark Shimozono (Massachusetts Institute of Technology)
            10:00 am   Francesco Brenti (University of Perugia)
            10:30 am   J. Matthew Douglass (University of North Texas)

            2:30 pm   Philip Hanlon (University of Michigan)
            3:00 pm   Daniel Rockmore (Dartmouth College)
            3:30 pm   David  Grabiner (Hebrew University)
            4:00 pm   Curtis Greene (Haverford College)

            4:45 pm   John Stembridge (University of Michigan)
            5:15 pm   Robert Proctor (University of North Carolina)
            5:45 pm   Adriano Garsia (University of California at San Diego)

            Sunday, October 8

            8:30 am    Sheila Sundaram (University of Miami)
            9:00 am    Michelle Wachs (University of Miami)
            9:30 am    Victor Reiner (University of Minnesota)
            10:00 am   William  Doran (California Institute of Technology)
            10:30 am   Mark Haiman (University of California at San Diego)

            2:30 pm   Alexander Kirillov, Jr. (Yale University)
            3:00 pm   Pavel Etingof (Yale University)
            3:30 pm   Bernard Leclerc (University of Paris VII)

            4:15 pm   Toshiki Nakashima (University of Osaka)
            4:45 pm   Yan Soibelman (Kansas State University)
            5:15 pm   Eugene Stern (University of California at Berkeley)


            Saturday Morning

            8:30    Bruce Kitchens
                    Dynamics of Markov groups
            9:00    Roy Adler
                    Topological conjugacy of endomorphisms of the 2-torus
            9:30    Jane Hawkins 
                    Characterizing mildly mixing actions using ratio sets and orbit equivalence.
            10:00   Aimee S.A. Johnson 
                    Loosely Bernoulli in $Z^d$
            10:30   Cesar Silva
                    Relatively weak mixing and infinite skew product entropy
            3:30    Adam Fieldsteel
                    Dyadic equivalence to actions of completely positive entropy
            4:00    Janet Whalen Kammeyer       
                    Restricted Orbit Equivalence for Actions of Discrete Amenable Groups
            4:30    Jonthan King       
                    Interrelations between determinism, zero-entropy and orbit separation
            5:00    Andres del Junco      
                    Construction of simple measure-preserving maps with prescribed automorphism group
            5:30    Nicholas S. Ormes
                    Strong Orbit Realization for Minimal Homeomorphisms

            Sunday Morning

            8:30    Robbie Robinson      
                    Finite type property and topoloogical dynamics for polyominoe tiling dynamical systems
            9:00    Boris Solomyak
                    Ergodic theory of non-periodic tilings.
            9:30    Charles Radin
                    Ergodic theory and the symmetry of tilings
            10:00   James Propp
                    A law of large numbers for the random domino tiling process
            2:30    Geoff Goodson
                    $G$-Maps in the Centralizer of Compact Abelian Group Extensions.
            3:00    B. S. Yadav     
                    The Mean-Ergodic Theorem and Spectral 
                    Decomposition of Complete isometries
            3:30    Gary L. Raduns, Jr.
                    Comparison of Generalizations of the Hopf Decomposition.


            Organizers: Zbigniew Nitecki,   ZNitecki(at-sign), Tufts University Boris Hasselblatt,  BHasselb(at-sign), Tufts University

            Current information about  this session  is available  on the  Worldwide  Web under  the  URL,   and  from  the organizers.

            Saturday, October 7

             9:30   Juan Tolosa (Stockton College of New Jersey)
                    Pattern families
            10:00   Marco Martens (SUNY Stony Brook)
                    Hyperbolicity of Circle Renormalization
            10:30   Mark Levi (Rensselaer Polytechnic Institute)
                    Deterministic randomness with positive probability
            2:40   Michael Shub (IBM)
                    Stable Ergodicity and Partial Hyperbolicity (40 minutes)
            3:30   Slobodan Simic (UC Berkeley)
                    Synchronization of Anosov flows
            4:00   Cymra Haskell (SUNY Stony Brook)
                    The Infinite Periodic Lorentz Gas is Space-Time Bernoulli
            4:30   Amie Wilkinson (UC Berkeley)
                    Stable ergodicity of maps arising from geodesic flows
            5:00   Fern Hunt (National Institute of Standards and Technology)
                    Approximation of Attractors by Ulam's Method

            Sunday, October 8

            9:00    Ami Radunskaya
                    KAM theory and the Fermi-Pasta-Ulam string model
            9:30    Tasso Kaper (Boston University)
                    Hyperbolicity in near-integrable N degrees-of-freedom Hamiltonian systems
            10:00   Pau Atela (Smith College)
                    A remarkable global bifurcation diagram in a Hamiltonian system
            10:30   Dmitri Kleinbock (Yale University)
                    Nondense orbits of flows on homogeneous spaces
            2:30    Andrei Torok and Viorel Nitica (Princeton U. & Indiana U. Bloomington)
                    Regularity of solutions for cocycle equations
            3:00    Alexei Kononenko (Pennsylvania State University)
                    Cohomologies of group actions and their applications
            3:30    Nantian Qian (Yale University)
                    Smooth conjugacy for Anosov diffeomorphisms and rigidity of
                    Anosov actions of higher rank lattices
            4:00    Henk Bruin (Universitat Erlangen)
                    Cantor-attractors for interval maps

            Stan Eigen would like to invite all participants to the following event:

            Ig Nobel Award Ceremony
            October 6, 1995, 7:30 PM
            Lowell Hall, Harvard University

            (Tickets need to be bought in advance; contact info(at-sign)


            Saturday, Oct. 7, 1995

            8:30   Nancy Eaton, Univ. of Rhode Island
            9:00   C. Zhang, W. Virginia University
            9:30   Ruth Haas, Smith College
            10:00  Claude Tardif, University of Montreal
            10:30  Gena Hahn,  University of Montreal

            2:30   Gara Pruesse, University of Vermont
            3:00   Lenwood Heath, Virginia Polytech Inst. & State Univ.
            3:30   Kathy McKeon, Conn. College

            4:00  BREAK

            4:30   Linda Lesniak, Drew University
            5:00   Daniel Kleitman, MIT
            5:30   Seth Chaiken, SUNY Albany

            Sunday, Oct. 8, 1995

            8:30   Lauren Rose, Wellesley College
            9:00   Brigitte Servatius, WPI
            9:30   Herman Servatius, MIT
            10:00  Karen Collins, Wesleyan Univ.
            10:30  Michael Albertson, Smith College

            2:30   Ann Trenk, Wellesley College
            3:00   Ken Bogart, Dartmouth College
            3:30   Ross McConnell, Amherst College

            4:00 BREAK

            4:30   Dave Berman, Univ. of New Orleans
            5:00   Emily Petrie, Arizona State Univ.
            5:30   Kathleen Romanik, DIMACS

The NOETHERIAN RING at MIT, Friday, October 6, 5:00pm in room 2-136, MIT

Biweekly half-hour talks given by women in mathematics followed by a half-hour for socializing and refreshments.

Professor Lynne M. Butler, Haverford College

An example of the topological perspective in combinatorics

Many beautiful theorems in algebraic topology have analogues in the theory of partially ordered sets. For example, Stanley discovered an Alexander duality theorem for Eulerian posets. In this talk we show how an observation of Matveev's, on how to compute the M\"obius number of a poset from edge coverings of its incomparability graph, may be quickly deduced from Stanley's Alexander duality theorem.

Wednesday, October 11, 4:35 p.m.; MIT, room 2-338

Joseph Bonin (George Washington University and MIT)

A survey of Dowling lattices

Dowling lattices arose in connection with the theory of linear codes and as q-analogs of partition lattices, and they were quickly seen to be of use for studying arrangements of hyperplanes. These geometric lattices also provided the motivation for biased graphs, and, like projective spaces and free matroids, they are the universal models for one of the five types of varieties of combinatorial geometries. This talk will provide an introduction to these lattices and will outline several recent advances in the theory.

The first class of results to be treated brings out similarities between Dowling lattices and projective spaces. This includes an axiom scheme for Dowling lattices, analogs of Desargues' and Pappus' theorems, and a coordinatization theory analogous to that for projective spaces. We will also present an application of the automorphism theory for Dowling lattices.

The second collection of results to be discussed involves the Tutte polynomial, the matroid counterpart of the dichromatic polynomial of graph theory. The Tutte polynomial of any matroid contains much information about the matroid, and this is especially true for Dowling lattices. We will explore exactly how much information about a Dowling lattice is reflected in its Tutte polynomial.

Friday, October 13, 4:15 p.m.; MIT, room 2-338

Tal Kubo (Harvard)

Conway's recursive sequence

Sequences obeying a(n) = a(a(n-1))+a(n-a(n-1)) have been explored by Conway, Hofstadter, Mallows, Kleitman and others. They have beautiful and intricate properties: combinatorial (symmetry, self-similarity), analytic (asymptotics related to the Gaussian distribution), and arithmetic (e.g., a(2^n)=2^{n-1}). We will show that a(n) can be viewed not as a complicated sequence, but as a simple compression operation on finite sets. Combinatorial structures including trees, Fibonacci and Catalan numbers, refinements of Pascal's triangle, and a mysterious appearance of Nim-like games, are encountered on the way. (These results were obtained in collaboration with R. Vakil.)

Wednesday, October 18, 4:35 p.m.; MIT, room 2-338

Thomas Sundquist (Dartmouth)

Pfaffians and theta functions

The classical theory of Elliptic Functions gives rise to many interesting theta function identities such as P(b+e) P(b-e) P(c+d) P(c-d) - P(b+d) P(b-d) P(c+e) P(c-e) + q^(c-d) P(b+c) P(b-c) P(d+e) P(d-e) = 0, where P is a rescaled version of Jacobi's third theta function. The proofs of these identities typically are analytic, or rely on invoking standard facts about the finite dimensional space of modular forms of a given weight. Other theta function identities, like Jacobi's Triple Product which factors a theta function into three infinite products, have nice combinatorial interpretations and proofs. In this talk I will discuss a simple "symmetric function theory" proof of a generalization of the former identity. The technique involves expressing the combination of theta functions as the Pfaffian of a 4 by 4 skew-symmetric matrix, and then expanding the Pfaffian as a (vanishing) sum of alternants. Finally, we generalize the proof to give interesting expansions for Pfaffians of other "theta-like" functions.

Friday, October 20, 4:15 p.m.; MIT, room 2-338

Ruth Haas (Smith)

Decomposing graphs into trees

The original characterization for when a graph can be decomposed into k spanning forests was given by Nash-Williams in 1964. In this talk we give several old and new characterizations for the following two classes of graphs: (i) graphs for which adding _some_ m edges produces a graph which is decomposable into k spanning trees, i.e., the graph has arboricity k; and (ii) graphs for which adding _any_ m edges produces a graph which is decomposable into k spanning trees.

The study of the second of these is motivated by some results in combinatorial rigidity. In particular, a graph is rigid in the plane if it can be "constructed" using rigid bars for the edges and rotatable joints for the vertices so that the only possible motions in the plane are translation and rotation. Lovasz and Yemini showed that a graph is minimally rigid in the plane (removal of any edge would make it not rigid) if and only if adding any edge to the graph, including a multiple edge results in a graph which is decomposable into 2 spanning trees. A recent paper of Crapo gives another characterization of this class and it is this characterization that we extend to other cases.

Wednesday, October 25, 4:15 p.m.; MIT, room 2-338

C. Kenneth Fan (MIT):

Matchings and canonical forms for symmetric tensors

Let V be a q-dimensional vector space. Fix a set B of q(q-1) monomials in S^p(V) of the form x^I where i_k>0 for all k. The generic element of S^p(V) is conjugate under a suitable linear transformation to an element with support off of B. We prove this by showing the existence of a perfect matching with a unique weight in a certain weighted bipartite graph. Such a perfect matching corresponds to the non-vanishing of an appropriate determinant.

This is joint work with Jozsef Losonczy.

Friday, October 27, 4:15 p.m.; MIT, room 2-338

Greg Kuperberg (Yale)

Alternating-sign matrices and the Yang-Baxter equation

Robbins conjectured, and Zeilberger recently proved, that there are


alternating sign matrices of order n. We will discuss a new proof of this result using an analysis of the six-vertex state model (also called square ice) based on the Yang-Baxter equation.

Friday, November 3, 4:15 p.m.; MIT, room 2-338

Richard Stanley (MIT)

Hyperplane arrangements, interval orders, and trees

Abstract: A (real) hyperplane arrangement is a finite set of affine hyperplanes in R^n. A central problem in the theory of hyperplane arrangements is to count the number of regions into which the hyperplanes subdivide R^n. For instance, the number of regions of the arrangement (known as the _braid_arrangement_) consisting of all hyperplanes x_i = x_j, i<j, is easily seen to be n!. We will consider some modifications (deformations) of the braid arrangement and show some surprising connections with such topics as interval orders and the enumeration of trees. In particular, there is an explicit conjecture for the number of regions of the arrangement x_i - x_j=1, i<j. Much of this work was done in collaboration with Nati Linial, Igor Pak, Alexander Postnikov, and Schmulik Ravid.

Discrete Mathematics Dinner, Friday, November 3 at 6 p.m. at Thai's Restaurant

The cost will be $7 for grad students and undergraduates (not counting alcoholic beverages), with the rest of us making up the difference.

Wednesday, November 8, 4:35 p.m.; MIT, room 2-338

Ira Gessel (Brandeis)

Counting binary trees by ascents and descents

The number of unlabeled binary trees on n vertices is the Catalan number C_n={1 \over n+1}{2n \choose n}, so the number of labeled binary trees is n! C_n. We call a vertex of a labeled binary tree (with totally ordered vertices) a _left_ascent_ if it is a left child and is greater than its parent, and we define right ascents and left and right descents similarly.

In this talk I will count labeled binary trees by left and right ascents and descents. Special cases yield Eulerian numbers and the number (n+1)^{n-1} of labeled rooted forests. There are also some non-obvious symmetries: There is a symmetry that switches left ascents with right descents, and by allowing repeated labels we obtain symmetric functions which I conjecture to be Schur-positive.

Seventeenth One Day Conference on Combinatorics and Graph Theory

Saturday, November 11, 1995

10 a.m. to 4:30 p.m. at Smith College Northampton MA 01063


Esther Tesar (Drew University)

Some Extensions of the Genus Distribution of Closed-End Ladders


Laszlo Lovasz (Yale University)

The Matching Structure of Graphs

12:10 Lunch

Joe Bonin (George Washington University)

A Survey of Dowling Lattices


Ileana Streinu (Smith College)

Visibility in Pseudo-Polygons and Vertex-Edge Pseudo-Visibility Graphs

Our Web page site has directions to Smith College, abstracts of speakers, dates of future conferences, and other information. The address is:

We have received an NSF grant to support these conferences. This will allow us to provide a modest transportation allowance to those attendees who are not local.

Wednesday, November 15, 4:35 p.m.; MIT, room 2-338

Miklos Bona (MIT)

Permutations avoiding certain patterns

It is a long-studied, hard problem to determine how many permutations in S_n avoid a certain pattern q. The general conjecture claims that less than K^n, where K is a constant. Efforts to prove this have been unsuccessful for most patterns. (For two permutations a and b, it is NP-complete to decide whether a is a pattern of b; the problem of counting permutations in S_n avoiding q is #P-complete. Thus in general all we can expect is an upper bound or an asymptotical formula, not an exact formula). The only important cases in which the conjecture is known to be true were when k = 3 or when the pattern is monotonic. We improve these results showing that the_conjecture_on_the_exponential_ upper_bound_is_true_for_all_patterns_of_length_4.

A conjecture states that if S_n(q_1) < S_n(q_2) for some n, then this inequality holds for all N > n. We prove this conjecture for patterns of length 4. These are the first results proving that one pattern is more likely to occur in a random permutation than another one. (Even in the asymptotical sense). Finally, we prove a lemma which allows us to extend our results to some longer patterns.

Friday, November 17, 4:15 p.m.; MIT, room 2-338

David Jackson (Waterloo)

The genus series for monopoles and the Euler characteristic for the moduli spaces of real algebraic curves

This question was solved for the complex case in 1986 by Harer and Zagier. A later argument was given by Penner. The real case, however, has remained open. In this talk I will give two arguments, that are combinatorial ones, which appeal 2-cell embeddings of graphs.

The first argument is based on determining the genus series for monopoles (these are maps with one vertex) in locally orientable surfaces. This is of interest in its own right.

The moduli space question can be expressed as a particular monopole problem (joint work with Goulden and Harer). This second problem can be treated by a classical theorem about multivariate integrals, to give a very simple explicit expression for the Euler characteristic.

The integral representation for the case of orientable surfaces can also be given, and this gives a proof of the original result of Harer and Zagier that is direct.


Monday, November 20, 4:15pm, 2-105

Gil Kalai, Institute for Advanced Study and Hebrew University

All Monotone Graph Properties Have Sharp Thresholds

In their seminal work which initiated random graph theory Erd\"os and R\'enyi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. That is, if every edge of the graph is chosen with probability $p$, then when $p$ increases, the transition from a property being very unlikely to its being very likely is very swift.

We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This result applies to random subgraphs of arbitrary symmetric graphs. We will discuss the relation between the symmetry group and the length of the transition interval.

Wednesday, November 29, 4:35 p.m.; MIT, room 2-338

All of Us (from All Over the Boston Area)

Open Mike Session / Combinatorial Free-for-All

Here's another chance to share partial results, open questions, and nice ideas that aren't suited to the 50-minute talk format. Presenters will include Gian-Carlo Rota, Dan Kleitman, and Christos Athanasiadis. Let Jim Propp know ahead of time what you're bringing, if you plan on presenting something that will take longer than five minutes.

Wednesday, December 6, 4:35 p.m.; MIT, room 2-338 *and* Friday, December 8, 4:15 p.m.; MIT, room 2-338

Gian-Carlo Rota (MIT)

A formal theory of resultants

Part I: The Cliffordization of Hopf algebras

Part II: Explicit formulas for resultants

A formula for the resultant of n homogoneous polynomials will be given. This formula can be used to derive all known properties of resultants without recourse to elimination theory.

Those who attend are expected to know basic notation of Hopf algebras.

Wednesday, December 13, 4:35 p.m.; MIT, room 2-338

Heidi Burgiel (Geometry Center)

Symmetric embeddings of regular maps: regular skew polyhedra

The label "regular polytope" can be applied to objects ranging from Platonic solids to simplicial complexes. The object of this talk is to describe methods of taking regular maps --- regularly tiled 2-manifolds --- and embedding the vertices of the tilings in Euclidean space to form objects called regular skew polyhedra. These polyhedra have all the symmetries dictated by the automorphism group of the underlying manifold, but may not have planar faces. They need not even lie in three dimensional space!

For example, a sphere can be regularly tiled with pentagons. One realization of this map is the dodecahedron. More interestingly, a torus can be tiled with squares. As Coxeter and Petrie discovered in 1926, this map can be realized in four dimensions as a polyhedral surface with square faces and "skew square" vertex figures.

In my talk I will describe more skew polyhedra, and review the methods I used to discover them. These methods, involving association schemes and representation theory, can be extended to provide symmetric realizations of any graph or polytope whose automorphism group is vertex-transitive.


All announcements since Fall 2007 are in the Google Calendar