|
|
 |
|
Mardi 7 Mai
| Heure: |
14:00 - 15:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Topology of the arc complex |
| Description: |
Pallavi Panda The arc complex is a pure flag simplicial complex associated to a finite-type topological surface with marked points. It was discovered by Harvey and used by geometers like Harer, Penner, Bowditch, Epstein to study geometric properties of hyperbolic surfaces, their Teichmüller spaces and their mapping class groups. The arc complex is also a subcomplex of the cluster complex of a cluster algebra, defined by Fomin-Zelevinksy. For most of the surfaces, the arc complex is locally non-compact. In this talk, I will discuss about the simplicial topology of the arc complex in the finite cases. In particular, I will focus on the shellability (analogous to simply-connectedness) and collapsibility (analogous to contractibility) of these finite complexes and prove that they are closed combinatorial balls.
Related articles: https://arxiv.org/abs/2402.10530, https://arxiv.org/abs/2306.06695 |
| Heure: |
16:00 - 17:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Mini course on popular matchings, lecture 1 |
| Description: |
Prof. Kavitha Telikepalli Lecture 1, Introduction to popular matchings.
The problem of computing a stable matching in a bipartite graph is an old and well-studied problem. Gale and Shapley showed in 1962 that such a matching always exists and can be efficiently computed. This is a classical result in algorithms with many applications in economics and computer science. Stability is a strong and rather restrictive notion. This series of talks will be on a relaxation of stability called "popularity". In the first talk we will see simple and efficient algorithms for some popular matching problems. No background in algorithms or matching theory will be assumed.
This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/. |
Mardi 14 Mai
| Heure: |
14:00 - 15:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Mini course on popular matchings, lecture 2 |
| Description: |
Prof. Kavitha Telikepalli Lecture 2: Popular matchings and optimality.
In this talk we will consider algorithms for finding optimal popular matchings. While it is easy to find max-size popular matchings, it is NP-hard to find a min-cost popular matching. This motivates us to relax popularity to a weaker notion called "quasi-popularity". Describing the popular and quasi-popular matching polytopes is hard, but there is an easy-to-describe integral polytope sandwiched between these two hard ones. So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching.
This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/. |
Mardi 21 Mai
| Heure: |
14:00 - 15:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Mini course on popular matchings, lecture 3 |
| Description: |
Prof. Kavitha Telikepalli Lecture 3: Popular assignments and extensions.
This talk will be on popular matchings in the one-sided preferences model. Popular matchings need not always exist in this model and there is a simple combinatorial algorithm to decide if one exists. We will see an LP-duality inspired algorithm for the more general problem of deciding if a popular assignment (i.e., a popular maximum-matching) exists or not. This algorithm can be generalized to solve the popular common base problem in the intersection of two matroids where one matroid is the partition matroid, this implies the popular arborescence problem (relevant in liquid democracy) can be solved efficiently.
This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/. |
|
|
