In the twenty-seven years since Lovász solved the Kneser conjecture by an ingenious application of the Borsuk-Ulam theorem, the general area of topological methods in combinatorial, discrete-geometric and algorithmic problems has developed into a strikingly effective body of technique.

The range of problems treated, and the variety of tools brought into play are still expanding: equivariant obstruction theory, homology theory, configuration spaces and fixed-point theorems and a great variety of other topics are utilized in applications, for example, to graph coloring problems, partition problems, and in data compression for meshes. Modern homotopy theory is also starting to appear in language design and the development of models for concurrent behaviour of systems.

In this workshop, we will discuss recent successes in the application of topological methods in combinatorics, discrete and computational geometry, and algorithms. We also expect to learn more about the tools that can lead to further, future successes. Making the important developments in this area understandable will be a fundamental goal of the meeting.

Schedule with Abstracts

Program

Monday, October 2

9:00 am: Herbert Edelsbrunner (Duke University): An introduction to topological persistence

10:30 am: Alex Suciu (Northeastern University): Fundamental group computations in the theory of arrangements and related spaces

2:00 pm: Dmitry Feichtner-Kozlov (ETH Zurich/University of Bremen): Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes

3:30 pm: Contributed 30 minute talks
- Raghavan Dhandapani: Greedy drawings of planar triangulations
- Matthew Kahle: The neighborhood complex of a random graph

Tuesday, October 3

9:30 am: Sinisa Vrecica (University of Belgrade): Equivariant methods

11:00 am: Michael Joswig (Technische Universität, Darmstadt): Explicit computations in algebraic topology

2:00 pm: Carsten Schultz (Technische Universität Berlin): Homomorphism complexes of graphs: constructions and computations

3:30 pm: Persi Diaconis (Stanford University): Graph homomorphisms and the birthday problem

4:30 pm: Reception

Wednesday, October 4

9:30 am: Joel Hass (University of California, Davis): Unknotting algorithms and their computational complexity

11:00 am: Nikolaus Witte (MSRI/Technische Universität, Berlin): Branched covers: A combinatorial model and applications

2:00 pm: Kevin Knudson (Mississippi State University): Algorithms in discrete Morse theory

3:30 pm: Graham Denham (University of Western Ontario): Generalized moment-angle complexes

Thursday, October 5

9:30 am: Gunnar Carlsson (Stanford University): Sparseness and matrix algorithms

11:00 am - 12:00 noon: Martin Raussen (University of Aalborg): Invariance of directed spaces and persistence

2:00 pm: Michael Joswig (Technische Universität, Darmstadt): Bounds for the f-vectors of tight spans

4:10 pm at UC Berkeley - Math Department Colloquium: Herbert Edelsbrunner (Duke): Global methods for high-dimensional data sets

Friday, October 6

9:30 am: Bernd Sturmfels (University of California, Berkeley): Convex Rank Tests

11:00 am: Raman Sanyal (Technische Universität, Berlin): Topological obstructions to polytope projection

12:00 pm: Lunch

1:30 pm: Contributed talks:
    Anton Dochtermann (U Washington): Universality of Hom-complexes
    Shripad Thite (Eindhoven): Pants decomposition of the punctured plane
    Javier Arsuaga (SFSU): Using computational knot theory to understand DNA packing in viruses
    Abhishek Bhattacharya (Arizona): Statistics on the planar shape space


A block of rooms has been reserved at the Hotel Durant. Please mention the workshop name and reference the following code when making reservations via phone, fax or e-mail: K20000. The cut-off date for reservations is September 1, 2006.

Funding

Important