Discrete Mathematics Day at Wesleyan

Saturday, February 26, 2005, 9:30 a.m. - 5:30 p.m.
Woodhead Lounge, Exley Science Center
Wesleyan University
Middletown CT 06459
Preprints/Reprints
Pictures
Program
Poster
Lodging
Directions

Program

10:00
Diane Maclagan (Rutgers): Holes in semigroups

Given a finite set of vectors A={a₁, . . . , a_n} generating Z^d as a group, the semigroup NA consists of all sums (with repetition allowed) of elements of A. We are interested the difference between NA and its normalization, which is the intersection of the cone generated by A in R^d with Z^d. Bounding this difference has implications for toric geometry.

11:00
Julianna Tymoczko (University of Michigan): Noncrossing partitions and ad-nilpotent ideals

Suppose n points on a circle are labelled clockwise from 1 through n. A subset of these points can be represented by the polygon that is the convex hull of the vertices. A partition corresponds to a collection of (possibly degenerate) polygons. We call a partition noncrossing if none of the edges of these polygons intersect. For instance, the partition {1,2,4,5}{3} is noncrossing while the partition {1,2,4},{3,5} is crossing.

Noncrossing partitions are naturally associated to certain hyperplane arrangements, certain ideals in a Lie algebra, and certain special subvarieties of the flag variety. We describe some of these connections and show how a generating function for each of these objects can be factored. Much of this talk is joint work with E. Sommers.

12:00
Lunch

1:30
Igor Pak (MIT): The nature of partition bijections

The study of partition identities has a long history going back to Euler, with applications ranging from Analysis to Number Theory, from Enumerative Combinatorics to Probability. Partition bijections is a combinatorial approach which often gives the shortest and the most elegant proofs of these identities. These bijections are then often used to generalize the identities, find ``hidden symmetries", etc. But to what extent can we use these bijections? Do they always, or at least often exist, and how do you find them? Why is it that some bijections seem more important than others, and what is the underlying structure behind the ``important bijections''? I will try to cover a whole range of partition bijections and touch upon these questions. The talk assumes no background whatsoever, and hopefully will be somewhat entertaining.

2:45
Ann Trenk (Wellesley College): The fractional weak discrepancy of a partially ordered set

In this talk we introduce the fractional weak discrepancy of a poset, building on previous work on weak discrepancy. Both are a measure of how far a poset is from being a weak order. Such problems are motivated by wanting to assign ranks to elements of a poset that respect the ordering and assign ranks that are not too far apart to incomparable pairs of elements. We give a structural characterization of weak discrepancy and show a connection to linear programming.

4:00
Ileana Streinu (Smith College): Pebble Game Algorithms with Inverse Ackermann complexity for
Body-and-Bar Rigidity

We present a simple and easy to implement algorithm, called the (k,1)-pebble game, for deciding if a multi-graph is the union of k edge-disjoint spanning trees (what we call a k-tree). If it is not, the algorithm computes a maximal independent subset of edges and k-subtree components. We apply this algorithm for testing generic rigidity for body-and-bar, body-and-hinge and panel-and-hinge frameworks in arbitrary dimension d, for finding the rigid components of an under-constrained framework and for extracting a maximal independent sub-framework from an over-constrained one.

Along the way, we extend the well-known theorem of Nash-Williams and Tutte on k-trees with an equivalent characterization via (k,1)-pebble games.

Our algorithm uses the union-find data structure, which leads to the appearance of \alpha, the inverse Ackermann function, in its complexity analysis. On a graph G with n vertices and m edges, it runs in O(kn² + (m+n)alpha(n,m)) and linear space.

This is joint work with Audrey Lee from UMass Amherst.