Séminaire de Géométrie Algorithmique et Combinatoire

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

Il se tient un jeudi par mois, de 14h à 17h, à l'Institut Henri Poincaré à Paris (plan d'accès), en salle 201.

Contact: seminaire [dot-sign] gac [the-funny-at-sign] ens [dot-sign] fr. Pour recevoir les annonces de ce séminaire, envoyer un message à cette adresse avec [inscription] dans le titre.

La liste des exposés passés est disponible ici.


8 déc. 2016
14h Luca Castelli Aleardi LIX, École Polytechnique
Mesures spectrales de distortion pour la visualisation de réseaux dynamiques
Dans cet exposé nous allons considérer le problème de la détection et visualization des modifications dans un graphe qui évolue dans le temps. Le problème de visualiser un graphe dynamique pose des défis supplémentaires par rapport au cas statique: en plus des contraintes esthétiques usuelles, on souhaite détecter les changements structurels du graphe de manière robuste et efficace. Notre contribution principale consiste à proposer une nouvelle notion de distortion (une fonction qui quantifie les changements dans le graphe) basée sur des méthodes spectrales et faisant intervenir l'optimization d'une fonction énérgie associée aux sommets du graphe. Notre approche est assez générale et flexible, permettant à l'utilisateur d'adapter de manière fine et multi-échelle le calcul de la distortion pour tenir compte de la nature des modifications dans le graphe. Pour conclure, nous allons montrer comment intégrer notre mesure de distortion dans un algorithme de visualisation de type "force-directed" capable de préserver la "mental map" du graphe.

Travail en collaboration avec Rania Ibrahim, Semih Salihoglu et Maks Ovsjanikov.

15h30 Xavier Goaoc Université Paris-Est Marne-la-Vallée
Topological Helly theorems
I will discuss how topological Helly-type theorems, which restrict the intersection patterns of families of sets of bounded topological complexity, relates to various classical topics: nerve theorems, non-embeddability of certain simplicial complexes, upper bound theorems, and sampling.
19 janv. 2017
Pierre Dehornoy Institut Fourier, Université Grenoble-Alpes
Intersection norms on the homology of surfaces
Intersection numbers of curves on surfaces are a topological and an algorithmic topic. In this talk we introduce for every finite collection of closed curves on a surface a norm on the first homology group of the surface that captures some properties of the intersection. These norms are 2-dimensional analogs of the Thurston norms that are famous among 3d-topologists. In particular their unit balls are also finite polyhedra. We give an explicit way to compute them. We also give an application that actually motivated these norms: we show how the integer points inside the unit balls classify certain topological/dynamical objects, namely the surfaces transverse to the geodesic flow in the unit tangent bundle to the surface.
Brigitte Servatius Worcester Polytechnic Institute
23 févr. 2017
Jérémie Chalopin CNRS, LIF, Marseille
23 mars 2017
Raphaëlle Chaine LIRIS, Université Claude Bernard Lyon 1
Louis Esperet CNRS, G-SCOP, Grenoble
20 avr. 2017
Jean-François Marckert CNRS, LaBRI, Université Bordeaux 1
Pierre-Guy Plamondon Université Paris-Sud
Combinatoire des triangulations de surfaces
11 mai 2017
14h
15h30
22 juin 2017
Boris Bukh Carnegie Mellon University

Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.

Le comité scientifique est constitué de:

Le comité d'organisation est constitué d'Éric Colin de Verdière, Steve Oudot et Vincent Pilaud.