Georgia Institute of Technology College of Sciences

This mini-conference will feature about six speakers on various topics in additive combinatorics.

I will describe some results concerning factorizations ofdiffeomorphisms of compact surfaces with boundary. In particular, Iwill describe a refinement of the well-known \emph{right-veering}property, and discuss some applications to the problem ofcharacterization of geometric properties of contact structures interms of monodromies of supporting open book decompositions.

We consider a the minimum k-way cut problem for unweighted graphs with a bound $s$ on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm runs in quadratic time while we have a different linear time algorithm for planar graphs and bounded genus graphs. Our result solves some open problems and contrasts W[1] hardness (no FPT unless P=NP) of related formulations of the k-way cut problem. Without the size bound, Downey et al.~[2003] proved that the minimum k-way cut problem is W[1] hard in k even for simple unweighted graphs. A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard in terms of k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard in s. Marx asked about FPT status with edge cuts, which is what we resolve here. We also survey approximation results for the minimum k-way cut problem, and conclude some open problems. Joint work with Mikkel Thorup (AT&T Research).

East Coast Computer Algebra Day (ECCAD) is an informal one-day meeting for those active or interested in computer algebra. It provides opportunities to learn and to share new results and work in progress.  The schedule includes invited speakers, a panel discussion, and contributed posters and software demonstrations. Importantly, plenty of time is allowed for unstructured interaction among the participants.  Researchers, teachers, students, and users of computer algebra are all welcome! Visit ECCAD for more details.