2013


Retour à la vue des calendrier
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.
Mardi 3 Décembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A branch-and-bound method for box constrained integer polynomial optimization
Description: Claudia D'Ambrosio We consider the problem of minimizing an arbitrary polynomial subject to
box and integrality constraints. We propose a new class of
under-estimators composed of separable functions of the original variables
and use it within a branch-and-bound scheme to easily and quickly compute
lower bounds. Computational results on randomly generated instances show
good performance with respect to the ones of different open-source solvers
like Couenne, Gloptipoly , and SCIP.
Moreover, the second part of the talk will be devoted to present a
different perspective on partially separable problems. In particula, an
exact algorithm for mixed integer non-linear programming problems with
separable non-convexities will be presented.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Efficient Algorithms for Dualizing Large-Scale Hypergraphs
Description: Uno Takeaki A hypergraph F is a set family defined on vertex set V.The dual of F is the set of minimal subsets H of V such thatJ cap H
e emptyset for any J in FThe computation of the dual is equivalent to many problems, such asminimal hitting set enumeration of a subset family, minimal set coverenumeration, and the enumeration of hypergraph transversals.In this paper, we introduce a new set system induced by the minimalitycondition of the hitting sets, that enables us to use efficient pruningmethods.We further propose an efficient algorithm for checking the minimality,that enables us to construct time efficient and polynomial spacedualization algorithms.The computational experiments show that our algorithms are quite fasteven for large-scale input for which existing algorithms do notterminate in practical time.
Mercredi 4 Décembre
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A New Approach to String Pattern Mining with Approximate Match
Description: Uno Takeaki Frequent string mining is the problem of finding frequently appearingstrings in a given string database or large text.It has many applications to string data analysis on strings such as texts,word sequences, and genome sequences.The problem becomes difficult if the string patterns are allowed to matchapproximately, i.e., a fixed number of errors leads to an explosionin the number of small solutions, and a fixed ratio of errors violatesthe monotonicity that disables hill climbing algorithms, and thusmakes searching difficult.There would be also a difficulty on the modeling of the problem;simple mathematical definitions would result explosion of the solutions.To solve this difficulty, we go back to the motivations to find frequentstrings, and propose a new method for generating string patternsthat appear in the input string many times.In the method, we first compute the similarity between the stringsin the database, and enumerate clusters generated by similarity.We then compute representative strings for each cluster, and therepresentatives are our frequent strings.Further, by taking majority votes, we extend the obtained representativesto obtain long frequent strings.The computational experiments we performed show the efficiency of bothour model and algorithm; we were able to find many stringpatterns appearing many times in the data, and that were long butnot particularly numerous.The computation time of our method is practically short, such as20 minutes even for a genomic sequence of 100 millions of letters.
Vendredi 6 Décembre
Heure: 00:59 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Data-race freedom by typing in Mezzo
Description: Thibaut Balabonski Mezzo is a typed programming language in the ML family whose static discipline controls aliasing and ownership. This rules out certain mistakes, including representation exposure and data races, and opens up new opportunities, such as gradual initialization or (more generally, and somewhat speculatively) the definition and enforcement of object protocols.

In this talk, I will explain the basic design of Mezzo on examples, and show how its type system inspired by separation logic gives a simple way of tracking ownership of fragments of shared memory between concurrent threads. Beyond the usual claim that "well-typed programs do not go wrong", we guarantee that well-typed Mezzo programs have no data-races.
Mardi 10 Décembre
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Autour des arbres de coalescence
Description: Olivier Hénard Les arbres de coalescence utilisés en phylogénétique sont naturellementconstruits depuis les feuilles. Nous posons la question d'une descriptionde ces arbres depuis la racine. Parmi les arbres de coalescence, les Betacoalescents constituent une classe d'étude favorite, et des liens récentsavec certaines classes d'arbres combinatoires (arbres récursifs et arbresbinaires) ont récemment permis d'en améliorer la compréhension. Nouscommencerons par rappeler ces constructions alternatives, duesrespectivement à Goldschmidt et Martin, et Abraham et Delmas. Nousprésenterons ensuite notre propre contribution, basée sur la représentationdite "lookdown".
Heure: 11:30 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Comportements asymptotiques dans quelques problèmes de sous-suites communes et/ou croissantes
Description: Christian Houdré Cet exposé présentera un panorama partiel et quelques résultatsrécents sur le comportement asymptotique (moyenne, variance, loislimites) dans certains problèmes de plus longue sous-suite croissanteet/ou commune.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Diamant aztèque, pyramides, et pavages pentus de Z^2
Description: Guillaume Chapuy Je parlerai de modèles de pavages par dominos de certaines régions duplan que nous appelons les «pavages pentus». Ces modèles contiennentplusieurs classes de pavages pour lesquelles des propriétésremarquables (énumératives et probabilistes) avaient été obtenues,notamment le «diamant aztèque» et les «partitions pyramides». Nousélucidons leur structure combinatoire en les mettant en correspondanceavec des suites de partitions entrelacées, faisant ainsi le lien avecles «processus de Schur» introduits par Okounkov et Reshetikhin. Laméthode permet non seulement une compréhension unifiée des formulesd'énumération, et leur généralisation à une famille infinie demodèles, mais également le calcul de fonctions de corrélation entreparticules, ouvrant potentiellement la voie à l'étude unifiée desformes limites (théorèmes de type «cercle arctique»). Notre point devue conduit par ailleurs à des algorithmes plaisants de générationaléatoire.L'exposé contiendra de nombreuses illustrations et peut-être même uneapplet java. Aucun pré-requis n'est nécessaire.(Travail commun avec Jérémie Bouttier et Sylvie Corteel)
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sur la structure conforme des cartes planaires aléatoires
Description: Nicolas Curien Une triangulation est un graphe (planaire, fini connexe) dessiné proprementdans la sphère de dimension 2 dont toutes les faces sont des triangles.On considère une triangulation aléatoire T_n choisie uniformément dansl'ensemble de toutes les triangulations à n faces.La structure métrique de T_n munie de la distance de graphe a été étudiéeen profondeur récemment.En particulier, Le Gall (voir aussi Miermont) a prouvé que T_nrenormalisée par n^{-1/4} converge vers une surface aléatoirefractale appelée la carte brownienne.Dans cet exposé nous nous intéresserons à un autre aspect destriangulations aléatoires. En effet, $T_n$ peut naturellement être munied'une structure de surface de Riemann et l'on peut ainsi étudier sa"structure conforme" qui est censée être très liée au champs libregaussien en dimension 2. Je présenterai un chemin pour l'étude de cette structureconforme fondé sur l'exploration markovienne des cartes planaires à l'aided'un processus SLE_6.
Mardi 17 Décembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Konig's edge-colouring theorem for all graphs
Description: Denis Cornaz We show that the maximum degree of a
graph G is equal to the minimum number of ocm sets covering G,
where an ocm set is the vertex-disjoint union of elementary odd
cycles and one matching, and a collection of ocm sets covers G if
every edge is in the matching of an ocm set or in some odd cycle
of at least two ocm sets.
This min-max relation gives a linear description of the star
polytope with a minimal TDI-system.
Joint work with V. H. Nguyen from LIP6.