|
|
 |
|
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/. |
Mardi 28 Mai
| Heure: |
14:00 - 15:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Lattice paths and branched continued fractions: Coefficientwise Hankel total positivity of the Laguerre polynomials |
| Description: |
Bishal Deb The Laguerre polynomials are a family of orthogonal polynomials which have been well-studied in combinatorics. The coefficients of these polynomials enumerate a certain family of graphs which have been called Laguerre digraphs or Laguerre configurations. The polynomial sequence has a well-known Stieltjes moment representation, i.e., these polynomials can be expressed as the sequence of moments of a certain measure supported on the positive real-axis. It is known that a sequence is a Stieltjes moment sequence if and only if its Hankel matrix is totally positive. A natural question is to ask if the Hankel matrix is also coefficientwise totally positive. We will address this question in this talk. We will begin by stating the main theorem which will not require any prerequisites. We then motivate this result; we first state the equivalence between Stieltjes moment sequences and the total positivity of Hankel matrices, then we mention how this theory has been extended coefficientwise. We introduce the production-matrix method which is a powerful tool to prove total positivity. Finally, we sketch a proof of our main theorem. |
Lundi 17 Juin
| Heure: |
12:45 - 14:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Les innovations et défis dans l'ingénierie du langage autour des unités phraséologiques |
| Description: |
Belem Priego Sanchez TBC |
Jeudi 20 Juin
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle A303, Université de Villetaneuse |
| Résumé: |
Partial optimality in linear ordering |
| Description: |
David Stein The linear ordering problem consists in finding a linear order < on a finite set A so as to minimize the sum of costs associated with pairs of elements a,b for which a < b. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem *partially* by deciding efficiently for some pairs (a,b) whether a |
|
|
