Math-Info 2010

Towards new interactions between mathematics and computer science


Invited Seminars

Thematic month

The five weeks

Topological Methods For The Study Of Discrete Structures

1.  Dates

From March 1st to March 5th, 2010.

2.  Description of the week

This week will focus on the use of tools coming from topology for the study of discrete structures like graphs, clouds of points,... For example, homology is a well-known concept from topology, which can be applied to combinatorial problems: the idea is to associate with a combinatorial object some simplicial complex, so that, by computing its homology, one gets informations on combinatorial properties of the original object.

The main lectures of this week will focus on

  • Topological methods for combinatorics
  • Topological methods for discrete geometry
  • Persistence and homology computation

There will be an introductory course about homology on Monday.

Note that this week, the last one of the thematic month, is followed by a (one-week) conference on computational geometry geometry organized by Éric Colin de Verdière and Boris Thibert, from 08-03 to 12-03. Participants of both weeks can thus also interact.

3.  Confirmed morning lectures (4h30 each)

  • Ron Aharoni: Connectivity, colorability and matchability.
Abstract: Hypergraphs (namely sets of sets, the latter being called "edges") can be realized geometrically: every vertex is represented by a point in R^n and every edge is represented by a "simplex", which is plainly the convex hull of the points corresponding to its vertices. (There is a simple requirement – no intersections between simplices should exist that do not follow from the intersection of the edges themselves. But this is easy to obtain if n is high enough.) The realization is called a "simplicial complex" It is usually demanded that the complex is closed downwards, so we shall always assume that the original hypergraph has this property. A closed down hypergraph is suitably called an abstract complexes, or also plainly a complex.
Surprisingly, the properties of the geometric realization can sometimes shed light on combinatorial properties of the abstract complex. In particular, one property containing important information is the connectivity of the complex. This is the dimension of the lowest dimensional "hole" in the complex, namely an image of S^n that cannot be filled by simplices from the complex. From the combinatorial point of view, connectivity of order k means being able to move continuously between edges of size up to k.
Combinatorial usage of the notion of connectivity usually consists of two parts:
1. showing how properties of the abstract complex follow from high connectivity of the geometrical complex, and
2. proving lower bounds on the connectivity in terms of combinatorial parameters.
In the talks I will discuss two applications – the Lovasz lower bound on the chromatic number of a graph in terms of the connectivity of the neighborhood complex of the graph, and my extension with P. Haxell of Hall's theorem. Most of the talks will be concerned with the latter, and its various applications.
Abstract: In this series of three lectures, I will introduce the concept of persistent homology, discuss algorithms, and present applications.
A. Homology and Persistent Homology.
Homology groups belong to the oldest topics in Algebraic Topology, dating back to the founding years. Persistence is a recent addition to the theory, motivated by practical needs that clash with the instability of homology computations for noisy data. In contrast, persistence is stable in a sense we will make precise in this first lecture.
B. Matrix Reduction Algorithms.
The classic algorithm for computing homology works by reduction of the boundary matrices to Smith normal form. A variant of this algorithm can be used to get the rich collection of persistence information of a filtration within about the same amount of time. There are fast implementations for important special cases, including functions on 2-manifolds.
C. Applications.
Persistent homology quantifies scale through a measure of the features in a discrete or continuous structure. It has been used to prove new mathematical theorems, to analyze scientific datasets, and to generally shed light on multiscale phenomena in nature.
Abstract:The focus of these lectures is on the use of computational topology to obtain coarse robust global descriptions of nonlinear dynamics. A rough breakdown of the topics is as follows:
Lecture 1: We will begin with the definitions of homology groups of spaces and the homorphisms induced by continuous maps. We will then discuss methods for computing these quantities.
Lecture 2: We will give a brief introduction to dynamical systems and bifurcation theory. The focus is on why algebraic topological methods are crucial for applications. We will then discuss isolating neighborhoods, attractor-repeller pairs, and Morse decompositions in the context of the decomposition of dynamics and discuss the computation of these objects.
Lecture 3: We will define and discuss the Conley index as a algebraic tool to understand the structure of invariant sets. We will conclude with applications to a variety of different types of problems.

4.  Schedule for the morning lectures


5.  Proposed workshops (add your suggestions here)

  • People from the ANR project "Graphs through Topological Structures": The topological meaning of the Colin-de-Verdiere invariant {{$\mu$}} defined for graphs (and other similar parameters)
  • Pavle Blagojevic : "Topological methods in geometric combinatorics with the view toward open problems"
  • Pedro Real: {$A_{(\infty)}$}-algebras, homological trees, and digital images";
  • Javier Carnero Iglesias.
  • Nicolas Delanoue. Guaranteeing the homotopy type of a set defined by non-linear inequalities.
  • Samuel Peltier and Guillaume Damiand: Presentation of a cellular combinatorial structure used in geometric modeling, generalized maps, and its use in homology computation
  • Christian Mercat: "Discrete Complex Analysis" How to turn a weighted graph into a discrete Riemann structure and how far the analogy goes (very far!).
  • Eli Berger : Cake slicing and wait-free synchronizing.
    • Suppose {$n$} people {$p_1, ..., p_n$} want to share a cake between them, namely, they want to agree on numbers {$x_1, ..., x_n$} where {$x_i$} is the part of the cake that {$p_i$} gets. (So each {$x_i$} should be between 0 and 1 and the sum should be 1.) We assume they need to overcome two problems. The first is that their communication is not synchronized. One person can transmit a message to all the other, but there is no way to be sure who got it yet and when. The second problem is that some of the {$n$} people might not participate at all, in which case we demand that their share is zero. In this talk I will show a way to do this. More precisely, I will show an infinite algorithm in which the ideas of the people about the how the cake should be shared {\em converge into an agreement}.
    • I will then show how this relates to more ``mainstream" computer science, where algorithms should terminate after some finite period of time. Problem of this sort are called ``wait-free synchronization problems". I will use the cake slicing algorithm in order to obtain an alternative (possibly simpler) proof of the famous result of Herlihy and Shavit saying that for problems of this sort there exists a solution if and only if some topological property holds, which resembles the Knaster-Kuratowski-Mazurkiewicz (KKM) structure.
    • If time allows, I will discuss another corollary, saying that in a wait-free synchronization problems one can make a ``write together - read together" assumptions about the scheduling, namely that each time there is a set of people transmitting their messages together, and then each person in this set receives all messages ``in the air".
    • I also suggest a way of putting the Herlihi-Shavit theorem and the KKM theorem on the two ends of a continuum of conjectures, proved for a special case.
  • Francis Sergeraert: Discrete vector fields in algebraic topology.
  • Pawel Dlotko, Andrea Cerri, Niccolo' Cavazza, Marc Ethier, Barbara Di Fabio: Homology and cohomology reduction algorithms and applications.
  • Pavel Salimov : "Uniform recurrence of products of infinite words".

6.  General Schedule

  • Monday 01st
    • 09h00-10h30 R. Aharoni - Connectivity, colorability and matchability.
    • 11h00-12h30 K. Mischaikow - Computational topology and dynamics
    • 15h00-15h30 N.Delanoue-Guaranteeing the homotopy type of a set defined by non-linear inequalities.
    • 16h00-17h00 E. Berger-Cake slicing and wait-free synchronizing.
    • 18h00-19h15 Apéritif at IML.
  • Tuesday 02th
    • 09h00-10h30 H. Edelsbrunner - Persistence homology, algorithms, and applications.
    • 11h00-12h30 R. Aharoni - Connectivity, colorability and matchability.
    • 17h00-18h00 F. Sergeraert - Discrete vector fields and basic algebraic topology.
    • 18h30-19h30 P. Dłotko - Homology and cohomology reduction algorithms and applications.
  • Wednesday 03th
    • 09h00-10h30 K. Mischaikow - Computational topology and dynamics.
    • 11h00-12h30 H. Edelsbrunner - Persistence homology, algorithms, and applications.
    • 15h00-16h00 D. Gonçalves - Representation of cellular complexes.
    • 16h15-17h00 M. Ethier - Critical Region Analysis of Scalar Fields in Arbitrary Dimensions.
    • 17h30-18h15 S. Peltier and G. Damiand - Cellular homology with generalized maps (demo!).
    • 18h30-19h15 R. Zivaljevic - Borromean and Brunnian rings (video!).
  • Thursday 04th
    • 09h00-10h30 H. Edelsbrunner - 'Persistence homology, algorithms, and applications.
    • 11h00-11h30 R. Aharoni - Connectivity, colorability and matchability (with focus on the nerve theorem).
    • 11h30-12h30 P. Blagojevic - Equivariant methods in geometric combinatorics.
    • 15h30-16h30 P. Real - {$A_{(\infty)}$}-algebras, homological trees, and digital images.
    • 17h00-19h00 - Two parallel sessions
      • about persistence
        • 17h00-17h30 B. Di Fabio - Recognition of occluded shapes using size functions.
        • 17h50-18h20 A. Cerri - The foliation method: Recent results in multidimensional Persistence Topology (and applications to shape comparison).
        • 18h40-19h10 N. Cavazza - On estimating the rank invariant of a submanifold through a finite sampling of points.
      • about combinatorics on words
        • 17h00-18h00 Anna Frid - Morphisms on (infinite) permutations.
        • 18h15-19h15' Pavel Salimov - Uniform recurrence of products of infinite words.
  • Friday 04th
    • 09h00-10h30 P. Blagojevic - Equivariant methods in geometric combinatorics.
    • 11h00-12h30 K.Mischaikow - Computational topology and dynamics.

7.  Currently uploaded slides and videos

8.  Links to some free software discussed during the week

9.  Participants

See the page Topological Methods For The Study Of Discrete Structures Participants


For any technical question or comment regarding this wiki, you can contact the wemaster.