2013


Retour à la vue des calendrier
Mardi 17 Septembre
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Une famille de contrexemples liée à l'infiltration des automates
Description: Gérard H. E. Duchamp It is now sure that one can show a version of the CQMM theorem which holds even in presence of heavy torsion. However the arrow constructed from the enveloping algebra of the primitive elements may not be into. There is a strange connection between the counter-example given on Mathoverflow and the q-infiltration product discovered by Luque et al.
Heure: 13:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Valeurs de G-functions
Description: Stéphane Fischler Une sous-classe importante des fonctions holonomesest la classe des G-fonctions (définie par Siegel), qui jouent notamment un rôle important en théorie des nombres, en physique et en combinatoire.Une grande question, qui demeure en partie ouverte, est de comprendre de façon finela structure de l'ensemble des valeurs prises par ces fonctions en des points algébriques.Ces valeurs englobent de célèbres constantes mathématiques, comme pi, les polyzêtas,des valeurs de fonctions hypergéométriques... Nous montrerons le résultat suivant : toute valeur en un point algébrique d'une G-fonction peut s'écrire f(1), où f est une G-fonction à coefficients rationnels dont le rayon de convergence peut de surcroît être choisi arbitrairement grand. On démontre aussi d'autres propriétés de ces valeurs de G-fonctions ; par exemple les constantes de connexion obtenues en prolongeant des G-fonctions sont de tels nombres. Il s'agit d'un travail en commun avec Tanguy Rivoal, dédié à la mémoire de Philippe Flajolet.
Heure: 14:30 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Pavages : quantifier l'aperiodicité d'un jeu de tuiles
Description: Thierry Monteil Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut être recouvert par des translatés de copies d'éléments de T (selon Z^2), de sorte que les arêtes en contact de deux tuiles adjacentes soient de même couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si aucun pavage obtenu n'est invariant par une translation. La plupart des jeux de tuiles apériodiques sont construits de façon autosimilaire (via une règle de substitution). Le but de cet exposé est d'introduire des invariants permettant de quantifier le niveau d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature topologique, l'autre est métrique. Ils reposent sur la manière dont le jeu de tuiles pave d'autres objets que le plan. Ces invariants nous permettent de démontrer que les jeux de tuiles de Kari et Culik ne sont pas gouvernés par une construction autosimilaire, car trop apériodiques.
Heure: 15:30 - 18:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Thé combinatoire et réunion d'équipe
Mardi 24 Septembre
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: From PROs to combinatorial Hopf algebras
Description: Samuele Giraudo There is a well-known natural functorial construction which, from a set-operad, produces a Hopf algebra. We extend this construction to the category of PROs with some extra properties. By this generalization, we retrieve, among other, the Hopf algebra of noncommutative symmetric functions in various bases and the noncommutative Faà di Bruno Hopf algebra. We also obtain new ones, as some Hopf algebras involving forests, heaps of pieces, and some kinds of combinational circuits. All these Hopf algebras are similar in a sense to the Connes-Kremier Hopf algebra. In this talk, we shall recall some background about PROs, then present the construction associating a Hopf algebra with a PRO, and finally, review some examples of applications.
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Trees and graphs (from algebraic combinatorics to topology and random tensor models):
Description: Journées Math-STIC
Heure: 11:15 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Kontsevich graph complexes
Description: Emily Burgunder Kontsevich proved that the Lie homology of symplectic Hamiltonians can be encoded as the homology of a Hopf bialgebra of graph complex attached to the commutative world. In this talk we will see some generalisation of this theorem : commutative world being replaced by operad, symplectic by a classical group, and we can consider Lie homology or its lifting to Leibniz homology.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Action of the symmetric groups on the homology of the hypertree posets
Description: Bérénice Oger The set of hypertrees on n vertices can be endowed with a poset structure. This poset has been used by McCammond and Meier to study the group of motions of the trivial link, which is an analogue of the braid group. They also proved that this poset is Cohen-Macaulay and computed the dimension of its only homology group. After a short introduction on this topological context, we explain how we used the theory of species to compute the action of the symmetric group on this homology group. We then link it with the PreLie operad.
Heure: 15:15 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Connes-Kreimer combinatorial Hopf algebra for the Ben Geloun-Rivasseau tensor field model
Description: Matti Raasakkar The Ben Geloun-Rivasseau quantum field theoretical model is the first tensor model shown to be perturbatively renormalizable. We define here an appropriate Hopf algebra describing the combinatorics of this new tensorial renormalization. The structure we propose is significantly different from the previously defined Connes-Kreimer combinatorial Hopf algebras due to the involved combinatorial and topological properties of the tensorial Feynman graphs. In particular, the 2- and 4-point function insertions must be defined to be non-trivial only if the superficial divergence degree of the associated Feynman integral is conserved.
Vendredi 27 Septembre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Intensionnalité vs. extensionnalité : où est-elle la frontière ? (1ère partie)
Description: Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).

Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.


Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.

Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis.
Mardi 1 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Etude de chaînes de Markov à l'aide de représentations de monoïdes
Description: Nicolas M. Thiéry Etude de chaînes de Markov à l'aide de représentations de monoïdesLa théorie des représentations des groupes finis est un sujetclassique. Dans le cadre plus général des monoïdes finis, la théorieest plus récente et a priori plus complexe. Cependant il existe desclasses de monoïdes où, comme pour les groupes, la théorie sesimplifie et fait surgir de la combinatoire, ce qui ouvre la porte àdes applications.Dans cet exposé, nous présenterons brièvement les éléments de lathéorie en mentionnant quelques développements algorithmiques récents[1], et décriront une application typique à l'étude d'une chaîne deMarkov sur des tas de sable à écoulement orienté [2]. La démarcheexploratoire sera illustrée par quelques calculs typiques avec lelogiciel Sage.Refs:- [1] Cartan invariant matrices for finite monoids http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAR0178- [2] arXiv:1305.1697: Directed nonabelian sandpile models on trees Ayyer, Schilling, Steinberg, T.
Mardi 8 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Normalité et automates
Description: Olivier Carton We strengthen the theorem that establishes that deterministic finitetransducers can not compress normal infinite words. We prove that, indeed,non-deterministic finite transducers, even augmented with a fixed number ofcounters, can not compress normal infinite words. However, there arepush-down non-deterministic transducers that can compress normal infinitewords. We also obtain new results on the preservation of normality withautomata selectors. Complementing Agafonov's theorem for prefix selectors,we show that suffix selectors also preserve normality. However, there aresimple two-sided selectors that do not preserve normality.
Vendredi 11 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Intensionnalité vs. extensionnalité : où est-elle la frontière ? (2e partie)
Description: Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).

Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.


Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.

Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis.
Mardi 15 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Le rang d'une suite unimodale et fonctions theta partielles
Description: Jeremy Lovejoy Il existe des égalités inattendues autour du rang d'unesuite unimodale, telle que U(1,5,5n+3) = U(2,5,5n+3), où U(t,m,n) estle nombre de suites unimodales de poids n avec rang congru à t modulom. De telles égalités rappellent celles pour le rang d'une partitionqui ont été observées par F. Dyson et qui sont liées aux formesmodulaires et mock modulaires. Dans le cas des suites unimodales, iln'y a pas cette structure modulaire ; la démonstration dépend d'uneidentité de fonctions thêta partielles due à Ramanujan. Ceci est untravail en commun avec B. Kim (Séoul).
Vendredi 18 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Intensionnalité vs. extensionnalité : où est-elle la frontière ? (3e partie)
Description: Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).

Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.


Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.

Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis.
Mardi 22 Octobre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Programmation linéaire colorée
Description: Pauline Sarrabezolles Considérons d + 1 ensembles de points de R^d en position
générique, et attribuons à chacun des ces ensembles une couleur
distincte. D'après le théorème de Carathéodory coloré, prouvé par Imre
Barany en 1982, si un point est contenu dans l'enveloppe convexe de
chacun de ces ensembles, alors il est contenu dans l'enveloppe convexe
d'un simplexe formé d'un point de chaque couleur. Un tel simplexe est
dit arc-en-ciel. La conjecture de la profondeur
simpliciale colorée, formulée par Antoine Deza et ses coauteurs en
2006, dit qu'un tel point est en fait contenu dans au moins d^2 + 1
simplexes arc-en-ciel, ce qui a été vérifié par différents auteurs
pour d = 1, 2 et 3. Nous vérifions cette conjecture en dimension 4 et
améliorons les bornes connues dans les dimensions plus élevées. Ces
résultats sont obtenus grâce à une généralisation combinatoire des
configurations colorées de points, suggérée par Imre Barany : les
systèmes octaédriques. Nous présentons de plus des algorithmes
résolvant divers problèmes de programmation linéaire colorée.
Vendredi 25 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques remarques d'ordre logique sur la théorie des types homotopiques (1ère partie)
Description: Christophe Fouqueré A partir du livre "Homotopy Type Theory", seront abordés les points
suivants: théorie des types (à la Martin-Löf), notions (très)
élémentaires d'homotopie et axiome d'univalence, hiérarchisation des
types et conséquences sur la partie interprétant la logique (en
particulier le tiers-exclus). Nous n'aborderons pas nombre de points
(théorie des catégories, types homotopiques d'ordre supérieur,
reconstruction des réels, ...) hautement intéressants de ce livre.
Mardi 29 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Random Boolean functions generated by random Boolean expressions
Description: Bernhard Gittenberger We will investigate the probability distribution on the set of Booleanfunctions in n variables if a Boolean function is generated by a largeBoolean expression drawn uniformly at random from all expressions ofthe same size. We show that a precise quantitative relation betweenthe probability of a function and its complexity which is defined asthe minimal size of an expression representing the function.
Mardi 5 Novembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Associaèdres d'arbres signés
Description: Vincent Pilaud Un associaèdre est un polytope dont les sommets correspondent aux triangulations d'un polygone convexe et dont les arêtes correspondent aux flips entre cestriangulations. J.-L. Loday en a donné une réalisation particulièrement élégante qui a été généralisée ensuite dans deux directions : d'un côté par C. Hohlweg et C. Lange pour obtenir de multiples réalisations de l'associaèdre paramétrées par une séquence de signes, et de l'autre par A. Postnikov pour obtenir une réalisation des associaèdres de graphes de M. Carr et S. Devadoss. Le but de cet exposé est de présenter une généralisation commune de ces constructions aux associaèdres d'arbres signés. Nous présenterons aussi les riches propriétés combinatoires et géométriques des polytopes qui en résultent. L'exposé sera illustré par le cas de l'associaèdre classique, dont l'interprétation en termes d'épine dorsale (arXiv:1307.4391, travail en commun avec C. Lange) est le fil directeur de ce travail.
Mardi 12 Novembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Disjunctive conic cuts for mixed integer convex optimization
Description: Pietro Belotti We study the convex hull of the intersection of a convex set E and a linear disjunction, which is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K that has the same intersection with the boundary of the disjunction as E, then the convex hull is the intersection of E with K. The existence of such a cone is difficult to prove for general conic optimization. However, for the special case of Mixed Integer Second Order Cone Optimization (MISOCO), such a cone can be efficiently generated. This cone provides a conic cut for MISOCO that can be used effectively in branch-and-cut algorithms for MISOCO problems. We show some preliminary computational results that substantiate our claims. (Joint work with Julio C. Goez, Imre Polik, Ted K. Ralphs, Tamas Terlaky)
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Distances in random planar maps and discrete integrability
Description: Jérémie Bouttier
Jeudi 14 Novembre
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Coloriage des graphes sur les surfaces
Description: Omid Amini Je commencerai par introduire le concept de S-coloriage de graphe :étant donné un sous-ensemble S(v) de voisins de v pour tout sommet v d'ungraphe G, c'est un coloriage propre des sommets de G tel que, en outre, les sommets qui appartiennent ensemble à un même S(v) pour un sommet v reçoivent des couleurs différentes.Ceci généralise à la fois le concept de coloriage du carré de graphe etle coloriage cyclique des graphes plongés.Je présenterai un résultat structurel fort pour les graphes plongésdans une surface fixe, qui permet par exemple de démontrer que lataille maximum d'une clique dans le carré d'un tel graphede degré maximum D est au plus 3D / 2 plus une constante.En utilisant ce résultat de structure, le S-coloriage d'un graphe plongépeut se réduire au coloriage d'arêtes d'un multigraphe.Je donnerai ensuite un aperçu général du travail de Jeff Kahn surarête-coloriage d'un multigraphe H, basé sur l'utilisation desdistributions hardcores sur les couplages, définies par des points àl'intérieur du polytope des couplages de H.En combinant ces résultats, on peut établir un résultat général sur leS-coloriage des graphes plongés, impliquant notamment les versionsasymptotiques des conjectures de Wegner et de Borodin sur le coloriage du carré et le coloriagecyclique des graphes planaires. Mon exposé est basé sur un travail en commun avecL. Esperet et J. van den Heuvel.
Heure: 11:15 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Critical and dual Gaussian multiplicative chaos
Description: Vincent Vargas The theory of Gaussian multiplicative chaos enables to makesense of random measures defined formally by the exponential of aGaussianFree Field (and more generally any logarithmically correlated field inalldimensions). These random measures are conjectured to be the scalinglimitof random planar maps coupled to a CFT and conformally mapped to thesphere or the upper half plane.The construction of the measures involve a parameter gamma related tothecentral charge c of the CFT. The classical construction does not settlethe question of constructing the measure for c=1 or equivalentlygamma=2as it yields a vanishing measure. In this talk, I will explain theappropriate construction and some properties of Gaussian multiplicativechaos at criticality, i.e. for gamma=2. If time permits, I will alsoexplain the construction of the dual measure (gamma larger than 2) andhowto make sense of the KPZ equation in this context.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Regular colored graphs of positive degree
Description: Gilles Schaeffer Regular colored graphs are dual representations of pure coloredD-dimensional complexes. These graphs can be classified with respectto an integer, their degree, much like maps are characterized by thegenus. We analyse the structure of regular colored graphs of fixedpositive degree and perform their exact and asymptotic enumeration. Inparticular we show that the generating function of the family ofgraphs of fixed degree is an algebraic series with a positive radiusof convergence, independant of the degree. We describe the singularbehavior of this series near its dominant singularity, and use theresults to establish the double scaling limit of colored tensor models.
Heure: 15:15 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Next-to-leading order in the large N expansion of the multi-orientable tensor model
Description: Matti Raasakka After providing some background and motivation for random tensormodels and their large N expansion, I will discuss recent results onthe next-to-leading order of the large N expansion for themulti-orientable tensor model. I will describe the class of Feynmantensor graphs contributing to this order in the expansion, and thecharacteristic properties of the next-to-leading order series for thismodel. These results represent the first step towards the larger goalof defining an appropriate double-scaling limit for themulti-orientable tensor model.
Heure: 16:15 - 19:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Melons are branched polymers
Description: James Melonic graphs constitute the family of graphs arising at leadingorder in the 1/N expansion of tensor models. They were shown to leadto a continuum phase, reminiscent of branched polymers. We show herethat they are in fact precisely branched polymers, that is, theypossess Hausdorff dimension 2 and spectral dimension 4/3.
Mardi 19 Novembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Line graphs and Facility Location Problem
Description: Laurent Beaudou (This is a joint work with M. Baïou, Z. Li and V. Limouzy) The line graph of a digraph can be defined in a few different ways. One 
of them came naturally from our study of a facility location problem. We discuss the complexity of recognizing such graphs and their cousins. During this seminar, we shall also have an overview of the historical birth 
of facility location problems.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Cartography on unoriented surfaces, with applications to real and quaternionic random matrices
Description: Emily Redelmeier I will discuss the cartographic machinery (encoding of mapson surfaces by permutations) on unoriented surfaces. I will discusshow these appear in calculations with real and quaternionic randommatrices, and their connections with other combinatorial objectsassociated with these objects, such as the hyperoctahedral group andmatricial cumulants. I will present some results in asymptoticsecond-order freeness which may be approached using these objects.
Jeudi 21 Novembre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Classification with reject option
Description: Blaise Hanczar Given a classification task, an approach to improve accuracy relies on theuse of classifiers with reject option. These classifiers are trained toreject observations for which predicted values are not reliable enough.During the classifier construction, a rejection area is defined around thedecision boundary in the feature space. There are two approaches fordefining the reject option: the plug-in rules where two decision thresholdsare computed on the classifier output and the embedded rejection rules wherethe rejection area is computed during the classifier fitting. We propose newmethods of plug-in reject for small-sample data and new ways of research forthe embedded reject.
Mardi 26 Novembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On unified methods for multi-attribute VRPs, route evaluation operators and large neighborhoods
Description: Thibaut VIDAL The research on
heuristics for VRP has been historically articulated around several
streams of research dedicated to some major problem variants, e.g.
with time windows, multiple depots, multi-period deliveries. Such
diverse research lines are justified if the nature of problems calls
for drastically different approaches. However, VRP variants share
naturally many common aspects, and many specific heuristic strategies
may be applicable to a broader range of problems. The identification
of fundamental resolution strategies is thus of primary concern to
progress towards more unified VRP algorithms, providing the means to
address various application cases in a timely manner without
extensive problem-tailored development.
Vendredi 29 Novembre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Présentation de l2coq : une bibliothèque pour des preuves linéaires en Coq
Description: Micaela Mayero Dans cette séance je présenterai l2coq, développé par O. Laurent et D.
Pous. Il s'agit d'un "sous-ensemble de Coq" (sous la forme d'une
bibliothèque "restrictive") permettant de faire des preuves de
propriétés linéaires (ILL, ELL, LLL, SLL). Olivier en avait fait une
présentation le jour de la soutenance d'HDR de Virgile. En 1 an, l2coq a
continué d'évoluer. Je vous propose de revenir sur les bases de l2coq en
vous montrant également le code et j'expliquerai pourquoi j'ai mis
quelques mots entre guillemet dans les phrases précédentes. Pour cela,
je ferai des rappels (ou pas pour certains) de la théorie de Coq en me
basant sur l'exposé précédent de Christophe, la partie théorie des
types. Vers la fin ou en cours d'exposé, je vous ferai une démo, durant
laquelle nous pourrons tenter ensemble de faire des preuves formelles de
propriétés linéaires (ILL dans un premier temps).
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Vector space decomposition for linear programming
Description: Jacques Desrosiers This presentation describes a vector space decomposition algorithm for
a linear program with bounded variables. Given a current feasible
solution, the exchange mechanism towards the next one is split into
independent parts based on two orthogonal vector subspaces, that is,
the master and the subproblem ones. The subproblem generates
directions (rays) compatible with the vector subspace of the master
problem. Indeed the subproblem partially satisfies the exchange
mechanism that is completed at the master level. Special cases of this
generic vector space decomposition algorithm are, amongst others, the
Primal Simplex, the Improved Primal Simplex yielding non-degenerate
pivots only, the Dynamic Constraints Aggregation method for the set
partitioning problem, and the strongly polynomial Minimum Mean
Cycle-Cancelling algorithm for the capacitated network flow problem.