Logo

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 about 13 years ago
To apply for Funding you must register by: July 02, 2006 over 13 years ago
Parent Program:
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.
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Funding & Logistics Show All Collapse

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 does not hire an outside company to make hotel reservations for our workshop participants, or share the names and email addresses of our participants with an outside party. If you are contacted by a business that claims to represent MSRI and offers to book a hotel room for you, it is likely a scam. Please do not accept their services.

MSRI has preferred rates at the Hotel Shattuck Plaza, depending on room availability. Guests can call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Institute discount. To book online visit this page (the MSRI rate will automatically be applied).

MSRI has preferred rates at the Graduate Berkeley, depending on room availability. Reservations may be made by calling 510-845-8981. When making reservations, guests must request the MSRI preferred rate. Enter in the Promo Code MSRI123 (this code is not case sensitive).

MSRI has preferred rates 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 "Affiliated with the Space Sciences Lab, Lawrence Hall of Science or MSRI." When prompted for your UC Contact/Host, please list Chris Marshall (coord@msri.org).

MSRI has a preferred rates at Easton Hall and Gibbs Hall, depending on room availability. Guests can call the Reservations line at 510-204-0732 and ask for the MSRI- Mathematical Science Research Inst. rate. To book online visit this page, select "Request a Reservation" choose the dates you would like to stay and enter the code MSRI (this code is not case sensitive).

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

Show Directions to Venue

Show Visa/Immigration

Show MSRI Collegiality Statement

Schedule, Notes/Handouts & Videos
Show Schedule, Notes/Handouts & Videos
Show All Collapse
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 (Ohio State University)
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 (TU Berlin)
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 (TU Berlin)
Oct 06, 2006
Friday
09:30 AM - 10:30 AM
  Convex Rank Tests
Bernd Sturmfels (University of California, Berkeley)
10:30 AM - 12:00 PM
  Topological obstructions to polytope projection
Raman Sanyal (Johann Wolfgang Goethe-Universität Frankfurt)
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