|
|
 |
|
Mardi 27 Mars
| Heure: |
11:00 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Combinatorial bases of KZn |
| Description: |
Gleb Koshevoy TBA (discussion) |
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Complexity of the cluster deletion problem on cographs and subclasses of chordal graphs |
| Description: |
Mario Valencia Pabon We consider the following vertex-partition problem on graphs,
known as the CLUSTER DELETION (CD) problem: given a graph with real
nonnegative edge weights, partition the vertices into clusters (in this
case, cliques) to minimize the total weight of edges outside the
clusters. The decision version of this
optimization problem is known to be NP-complete even for unweighted
graphs and has been studied extensively. In this talk, I will focus on
the complexity of the decision CD problem for the family of chordal
graphs, showing that it is NP-complete for weighted split graphs,
weighted interval graphs and unweighted chordal graphs. We will also see
that the problem is NP-complete for weighted cographs. Some
polynomial-time solvable cases of the optimization problem will be
identified, in particular CD for unweighted cographs, split graphs,
unweighted proper interval graphs and weighted block graphs.
This is a joint work with Flavia Bonomo and Guillermo Duràn (University
of Buenos Aires). |
| Heure: |
14:00 - 15:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Cluster relations among Schur functions and a positivity conjecture |
| Description: |
Gleb Koshevoy Cluster algebras, invented by Sergey Fomin and Andrei Zelevinsky around 2000,
are commutative algebras whose generators and relations are constructed in a recursive manner.
Due to cluster recursion we obtain Laurent polynomials in the initial variables, so-called Laurent
phenomenon of cluster algebras. The coordinate ring of base affine space C[N_-SL_n] plays an important role in representation theory and is endowed with a cluster algebra structure. We show that under specialization of minors to Schur functions, Laurent polynomials of this cluster algebra turn into 'homogeneous' sums of Schur function. A positivity conjecture says that these sums have positive coefficients. This conjecture is true for finite cluster subalgebras. |
Vendredi 30 Mars
| Heure: |
11:00 - 13:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Un calcul des séquents avec des types dépendants pour l'arithmétique classique |
| Description: |
Etienne MIQUEY En 2012, Hugo Herbelin définit dPA?, un langage typé qui fournit, dans un cadre compatible avec la logique classique, un terme de preuve pour laxiome du choix dépendant, qui peut être vu comme une adaptation de la preuve constructive de laxiome du choix en théorie des types de Martin-Löf ou une internalisation dans un système de preuve de lapproche en réalisabilité de Berardi, Bezem et Coquand. Malheureusement ce calcul ne dispose pas d'une preuve de normalisation, la difficulté d'une telle preuve est liée à la présence simultanée de types dépendants (pour la partie constructive du choix), d'opérateurs de contrôle (pour la logique classique), d'objets co-inductifs (pour "encoder" les fonctions de type N ? A par des streams (a?,a?,...)) et d'évaluation paresseuse avec partage (pour ces objets co-inductifs).
Durant cet exposé, nous verrons comment définir une variante de dPA? en calcul des séquents dont on pourra prouver la correction. Au passage, on montrera la normalisation du call-by-need classique (présenté comme une extension du ?µµ?-calcul avec des environnements partagés) en utilisant notamment des techniques de réalisabilité à la Krivine ; et l'on développera un calcul des séquents classique avec types dépendants, dont la correction est prouvable à l'aide d'une traduction CPS tenant compte des dépendances. |
|
|
