Invited Seminars Thematic month The five weeks |
## Topological Methods For The Study Of Discrete Structures
## 1. DatesFrom March 1st to March 5th, 2010. ## 2. Description of the weekThis 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.
- Herbert Edelsbrunner: Persistence homology, algorithms, and applications
- Konstantin Mischaikow : Computational topology and dynamics
## 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*.
- about persistence
**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- AndreaCerri-TheFoliationMethod.pdf ... 786,575 bytes ... 05 March 2010 à 15h59
- BarbaraDiFabio-RecognitionOfOccludedShapesUsingSizeFunctions.pdf ... 563,058 bytes ... 05 March 2010 à 16h25
- DusanZivaljevic-BorromeanAndBrunnianRings-Video.2.avi ... 27,728,494 bytes ... 03 March 2010 à 22h40
- EliBerger-CakeSlicingAndWaitFreeSynchronizing.ppt ... 171,520 bytes ... 06 March 2010 à 22h14
- FrancisSergeraert-DiscreteVectorFieldsAndBasicAlgebraicTopology.pdf ... 171,025 bytes ... 05 March 2010 à 17h40
- HerbertEdelsbrunner-HomologyAndPersisantHomology-Talk1.pdf ... 9,704,132 bytes ... 02 March 2010 à 17h05
- HerbertEdelsbrunner-I-HomologyAndPersisantHomology.pdf ... 9,704,186 bytes ... 04 March 2010 à 11h06
- HerbertEdelsbrunner-II-AlgorithmsAndDataStructures.pdf ... 6,063,177 bytes ... 04 March 2010 à 11h06
- HerbertEdelsbrunner-III-ApplicationsOfPersisantHomology.pdf ... 11,386,854 bytes ... 04 March 2010 à 11h07
- KonstantinMischaikow-ComputationalTopologyAndDynamics.pdf ... 18,649,471 bytes ... 05 March 2010 à 10h54
- MarcEthier-CriticalRegionAnalysisOfScalarFieldsInArbitraryDimensions.pdf ... 601,598 bytes ... 27 February 2010 à 10h21
- NiccoloCavazza-ReductionAndApproximation.pdf ... 571,081 bytes ... 05 March 2010 à 16h37
- NicolasDelanoue-GuaranteeingTheHomotopyTypeOfASetDefinedByNonLinearInequalities.pdf ... 4,006,983 bytes ... 05 March 2010 à 19h05
- PavleBlagojevic-EquivariantMethodsInGeometricCombinatorics.pdf ... 2,495,769 bytes ... 12 April 2010 à 00h55
- PawelDlotko-HomologyAndCohomologyReductionAlgorithmsAndApplications.pdf ... 2,195,387 bytes ... 05 March 2010 à 17h42
- RadeZivaljevic-BorromeanAndBrunnianRings.pdf ... 1,029,362 bytes ... 05 March 2010 à 15h48
- RonAharoni-ConnectivityColorabilityAndMatchability-ToBeUpdated.pdf ... 1,156,813 bytes ... 01 March 2010 à 20h37
- SamuelPeltierGuillaumeDamiand-CellularHomologyWithGeneralizedMaps.pdf ... 1,326,880 bytes ... 03 March 2010 à 23h14
## 8. Links to some free software discussed during the week## 9. ParticipantsSee 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.