Georgia Institute of Technology College of Sciences

The correlation of gaps in dimer systems was introduced in 1963 by Fisher and Stephenson, who looked at the interaction of two monomers generated by the rigid exclusion of dimers on the closely packed square lattice. In previous work we considered the analogous problem on the hexagonal lattice, and we extended the set-up to include the correlation of any finite number of monomer clusters. For fairly general classes of monomer clusters we proved that the asymptotics of their correlation is given, for large separations between the clusters, by a multiplicative version of Coulomb's law for 2D electrostatics. However, our previous results required that the monomer clusters consist (with possibly one exception) of an even number of monomers. In this talk we determine the asymptotics of general defect clusters along a lattice diagonal in the square lattice (involving an arbitrary, even or odd number of monomers), and find that it is given by the same Coulomb law. Of special interest is that one obtains a conceptual interpretation for the multiplicative constant, as the product of the correlations of the individual clusters. In addition, we present several applications of the explicit correlation formulas that we obtain.

Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a ``master bijection'' for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of their faces. Our approach unifies and extends many known bijections. This is joint work with Eric Fusy.

A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the well-known Unique Games Conjecture -- a conjecture that has numerous implications in approximation algorithms. In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.

The quotient of a Boolean algebra by a cyclic group is proven to have a symmetric chain decomposition. This generalizes earlier work of Griggs, Killian and Savage on the case of prime order, giving an explicit construction for any order, prime or composite. The combinatorial map specifying how to proceed downward in a symmetric chain is shown to be a natural cyclic analogue of Kashiwara's sl_2 lowering operator in the theory of crystal bases. The talk will include a survey of related past work on symmetric chain decomposition and unimodality by Greene-Kleitman, Griggs-Killian-Savage, Proctor, Stanley and others as well as a discussion of open questions that still remain. This is joint work with Anne Schilling.