|
|
Groupe de travail de l'équipe combinatoire
|
english |
Les propositions d'exposés sont bienvenues, n'hésitez
pas à
contacter Gilles
Schaeffer ou Eric Fusy.
Soient k et n deux entiers avec n supérieur à 2k+1.
On appelle k-triangulation d'un polygone convexe à n côtés tout ensemble maximal de diagonales qui ne contient pas de sous-ensemble de k+1 arêtes qui se croisent deux-à-deux.
Plusieurs propriétés des triangulations ont d'ores et déjà été généralisées aux k-triangulations, parmi lesquelles :
1) toutes les k-triangulations d'un polygone convexe à n côtés ont le même nombre d'arêtes : k(2n-2k-1).
2) toute arête d'une k-triangulation (de longueur au moins k+1) peut être flippée d'une unique manière. Le graphe des flips est régulier et connexe.
3) l'ensemble des k-triangulations d'un polygone convexe à n côtés est compté par le même déterminant de nombres de Catalan qui énumère les familles de k chemins de Dyck disjoints.
Bien que ces résultats aient déjà été démontrés (par des arguments récursifs), nous présentons de nouvelles preuves (directes) des propriétés (1) et (2) utilisant le nouveau concept d'étoiles dans les multi-triangulations qui généralise les triangles dans les triangulations. Nous présentons quelques questions ouvertes dont l'analyse pourrait être simplifiée par ce nouvel outil.
(Travail en commun avec Francisco Santos, Santander, Espagne)
Résumé: On s'intéresse à la classe STRING des graphes d'intersection de courbes dans le plan. C'est-à-dire qu'un graphe appartient à STRING si on peut associer à chaque sommet une courbe du plan de sorte que deux sommets sont adjacents si et seulement si les courbes associées s'intersectent. Cette classe contient beaucoup de classes de graphes intéressantes (graphes de corde, d'intervalle, co-bipartis ...), notamment les graphes planaires, pour lesquels Chalopin et Goncalves ont récemment montré qu'ils admettent un modèle d'intersection dont les courbes sont des segments. Les problèmes ouverts ne manquerons pas.
Les tresses mathématiques sont issues d'une idée assez simple et naturelle. Cependant, leur étude mathématique, commencée par Artin en 1926, soulève des problèmes intéressants et difficiles. Je commencerai par donner différentes présentations du groupe des tresses. Je parlerai plus particulièrement de la présentation par générateurs et relations, du problème du mot dans ce cas et comment y répondre. J'expliquerai ensuite comment généraliser la notion d'empilements de pièces pour calculer la série génératrice des tresses positives.
On définit deux classes de séries hypergéométriques basiques multiples V_{k,t}(a, q) et W_{k,t}(a, q) qui généralisent des séries multiples étudiées par Agarwal, Andrews et Bressoud. On montre comment interpréter ces séries comme les fonctions génératrices de chemins avec certaines restrictions et de surpartitions n-colorées vérifiant des conditions de différences pondérées. On remarque aussi que certaines spécialisations de nos séries peuvent s'écrire comme des produits infinis, ce qui conduit à des identités combinatoires reliant les surpartitions n-colorées aux partitions ou surpartitions ordinaires.
A series is D-finite if it satisfies a linear differential equation with polynomial coefficients. The class includes algebraic and rational functions, both of which have very nice combinatorial representations using generating functions of context free languages and regular languages respectively. In this talk, we will explore combinatorial interpretations of D-finite functions. First, we shall consider lattice paths in restricted regions, and then we shall consider the types of formal languages that arise when we add the (disjoint) shuffle product to our expressive power. We will describe a system that can achieve any D-finite series.
(Travail en collaboration avec L. Addario-Berry et B. Reed.) L'arbre couvrant minimal d'un graphe pondéré représente une sorte de squelette du reseau qui peut-être utilisé pour approximer des problèmes difficiles ou comme support à un réseau plus dense. Dans les deux cas, sa structure et la distance typiques entre les noeuds influencent la qualité des applications. Nous nous plaçons dans le cas où le graphe sous-jacent est complet et pondéré de manière aléatoire. Nous étudions les liens qui existent entre l'arbre couvrant minimal et de nombreuses structures fondamentales telles que les graphes aléatoires de Erdos-Renyi, les arbres récursifs et les arbres simplement générés. Nous en déduisons l'ordre de grandeur des distances dans l'arbre couvrant minimal.
Towards computational information geometry
Multi-dimensional heterogeneous data sets are ubiquituous in visual computing (eg., image classification, face recognition, texture synthesis, etc.). For example, in image recognition or classification, various low-level features are first extracted and stacked onto a high-dimensional vector encoding the individual image properties. In these high dimensional Cartesian product spaces, it becomes challenging to guess by ad-hoc methods (meaning hard-coding distances in the software) the "right" distance measure. This is all the more problematic as the Euclidean distances or other classic norms fail in most cases. A novel algorithmic trend consists in learning from the data sets themselves the most appropriate distance function belonging to a class of measures. In order to solve the task at hand, this implies that the latter algorithm has to work for *any* member of the distance class. In this talk, I will consider the class of information-theoretic Bregman divergences that are axiomatically neatly characterized as generalizing least-square projections. Bregman divergences are not necessarily symmetric distortions that encapsulate the (squared) Euclidean distance and the relative entropy. This makes it very attractive since Bregman-compliant algorithms will be able to handle indifferently geometric or statistical data sets (eg, histograms or parametric distributions) We review our recent work on generalizing core geometric algorithms to the class of Bregman divergences: