# Mathematical Sciences Research Institute

Home » Workshop on Topological Methods in Combinatorics, Computational Geometry, and the Study of Algorithms

# Workshop

Workshop on Topological Methods in Combinatorics, Computational Geometry, and the Study of Algorithms October 02, 2006 - October 06, 2006
 Registration Deadline: September 25, 2006 over 7 years ago July 02, 2006 almost 8 years ago
Parent Program: Computational Applications of Algebraic Topology
Organizers G. Carlsson, P. Diaconis, R. Jardine, and G. M. Ziegler
Speaker(s)

## Show List of Speakers

Description

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 & Logistics

## Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

## Show Lodging

MSRI has preferred rates at the Rose Garden Inn, depending on room availability. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show the MSRI rate on all room types available.

MSRI has preferred rates at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code MSRI123. Our preferred rate is $129 per night for a Deluxe Queen/King, based on availability. MSRI has preferred rates of$149 - $189 plus tax at the Hotel Shattuck Plaza, depending on room availability. Guests can either call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Inst. discount; or go to www.hotelshattuckplaza.com and click Book Now. Once on the reservation page, click “Promo/Corporate Code“ and input the code: msri. MSRI has preferred rates of$110 - \$140 at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select “I am an individual traveler affiliated with MSRI”.

Additional lodging options may be found on our short term housing page.

## Show Visa/Immigration

Schedule
Oct 02, 2006
Monday
 09:00 AM - 10:00 AM An introduction to topological persistence Herbert Edelsbrunner (Duke University) 10:30 AM - 11:30 AM Fundamental group computations in the theory of arrangements and related spaces Alexandru Suciu (Northeastern University) 02:00 PM - 03:00 PM Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes Dmitry Feichtner-Kozlov 03:30 PM - 04:00 PM Greedy drawings of planar triangulations Raghavan Dhandapani 04:00 PM - 04:30 PM The neighborhood complex of a random graph Matthew Kahle
Oct 03, 2006
Tuesday
 09:30 AM - 10:30 AM Equivariant methods Sinisa Vrecica 10:30 AM - 11:30 AM Explicit computations in algebraic topology Michael Joswig 02:00 PM - 03:00 PM Homomorphism complexes of graphs: constructions and computations Carsten Schultz 03:30 PM - 04:30 PM Graph homomorphisms and the birthday problem Persi Diaconis (Stanford University)
Oct 04, 2006
Wednesday
 09:30 AM - 10:30 AM Unknotting algorithms and their computational complexity Joel Hass (University of California, Davis) 10:30 AM - 11:30 AM Branched covers: A combinatorial model and applications Nikolaus Witte 02:00 PM - 03:00 PM Algorithms in discrete Morse theory Kevin Knudson
Oct 05, 2006
Thursday
 09:30 AM - 10:30 AM Sparseness and matrix algorithms Gunnar Carlsson (Stanford University) 10:30 AM - 12:00 PM Invariance of directed spaces and persistence Martin Raussen 02:00 PM - 03:00 PM Bounds for the f-vectors of tight spans Michael Joswig
Oct 06, 2006
Friday
 09:30 AM - 10:30 AM Convex Rank Tests Bernd Sturmfels (UC Berkeley Math Faculty) 10:30 AM - 12:00 PM Topological obstructions to polytope projection Raman Sanyal (Freie Universität Berlin) 01:30 PM - 02:00 PM Statistics on the planar shape space Abhishek Bhattacharya 02:00 PM - 02:30 PM Universality of Hom-complexes Anton Dochtermann 02:30 PM - 03:00 PM Pants decomposition of the punctured plane Shripad Thite 03:00 PM - 03:30 PM Using computational knot theory to understand DNA packing in viruses Javier Arsuaga