Vince Vatter (Rutgers)
Packing densities of permutations

The packing density of a permutation measures how densely many copies of that permutation may be packed together into a larger permutation. This statistic has been studied extensively since the early 90s when Herb Wilf first formulated it formally, although the progress is still modest. This talk will be an introductory survey of these efforts.

Tanya Berger-Wolf (DIMACS)
Persistent Social Structures

Humans, zebras, geese, ants, bacteria, all form social groups. Taken as a snapshot any population of social animals will have several groups in it. However, a snapshot taken at a different time may show totally different groups. Social associations change from minute to minute, hour to hour, day to day. Some groups tend to change more, while others, less. Some just loose or gain a few members at a time while others break up into many smaller groups and reassemble again. Other still just reappear every now and then. Which social groups are important, significant, stable? What does it mean for a group to persist over time? And over what time? We try to answer these questions algorithmically, modeling populations as dynamic graphs. We give a formal general definition of persistence of a social group and try to analyze what it means in various contexts and what algorithms are appropriate for various applications. Our main application right now is the social structure of zebras at the Mpala Conservancy in Kenya, Africa, and onagers in India. This project is in collaboration with Dan Rubenstein's group from Princeton, Jared Saia from University of New Mexico and S. Muthukrishnan from Rutgers University.

Bruce Sagan (DIMACS, Michigan State University)
Maximal Independent Sets in Graphs

A combinatorial graph G consists of a set V of vertices and a set E of edges between them. For example, V could be a set of cities with an edge between two cities if there is a direct airline flight between them. Graphs are of interest in many disciplines, for example, biology and computer science. An independent set in G is a subset I of the vertex set such that there is no edge between any two vertices in I. Independent sets are crucial in the proof of the famous Four Color Theorem. We will investigate counting maximal independent sets, which are those which are not contained in any larger independent set, starting with a fundamental question of Paul Erdos and Leo Moser.

Joint work with G. Guo, M. Kho, and V. Vatter.

Endre Boros (Rutgers)
How Good (or Bad) Can Stable Marriages Be?

Stable marriages are widely used in game theory, economics and sociology to model e.g., job markets, supplier-consumer relations, etc., and even the fairness and/or robustness of certain economic or social processes. A recent bibliography contains well over 100 items published just in the past decade. Most of these studies focus on the properties of and/or algorithms for finding a stable matching in a particular situation. In this study we focus on quality measures associated to stable matchings, and study their properties over all possible input situations. In particular, we associate a so called rank- profile to stable marriages, which describes the quality of the marriages from the point of view of the participating individuals. We give a full characterization of stable rank-profiles, and prove that there are instances when no individual can get better than the middle in his/her preference list in any stable marriage. We also study unique rank-profiles, and demonstrate by troubling examples that a "miserable couple moving into the village can easily spoil the life for everybody."

Joint work with L. Fedzhora, V. Gurvich and S. Jaslar.

Dominique Foata (Strasbourg)
Combinatorics and Special Functions: the Hermite Polynomials

The classical orthogonal polynomials (Hermite, Laguerre, Jacobi, Meixner,...) form a hard kernel within the study of Special Functions. Several closed formulas are known, with explicit coefficients. Does there exist a hidden geometry that explains those formulas?

For a combinatorial approach we have to introduce a sequence of discrete structures, count them in two different ways, which correspond to the two sides of the identity to be proved, finally bring an algebraic tool to put the two ways together. Illustration with the Hermite polynomials.

Diane Maclagan (Rutgers)
The card game Set.

SET is an extremely addictive, fast-paced card game found in toy stores nationwide. Although children often beat adults, the game has a rich mathematical structure linking it to the combinatorics of finite affine and projective spaces and the theory of error-correcting codes. In this talk I will introduce this mathematics behind SET. I won't assume familiarity with the game, but anyone wanting to be more prepared could look at the game's webpage: http://www.setgame.com/.

Panel on Graduate School in Mathematics and Computer Science

Panel members:
Eric Allender, Rutgers, Department of Computer Science
Peter Hammer, Rutgers, RUTCOR
John Kolassa, Rutgers, Department of Statistics
Chuck Weibel, Rutgers, Department of Mathematics