24-25 Avril 2011

Première réunion ANR – TEOMATRO

(Nouvelles Tendances dans les Matro´des : Polytopes des bases, Structures, Algorithmes et Interactions)


salle C319 du bâtiment C (l'Institut National Polytechnique de Grenoble)
46, Avenue Félix Viallet, Grenoble
Contacts : Myriam PREISSMANN (ING Grenoble), András SEBÖ (ING, Grenoble), Zoltán SZIGETI (ING, Grenoble)

Programme

JEUDI 24 FEVRIER 2011

10h30-11h15
Accueil et informations gènèrales

Intervention d'Olivier COUCHARIERE
(représentant de l'ANR)

11h15 -12h
Jorge RAMIREZ ALFONSIN (Université Montpellier 2)
Sur la décomposition du polytope des bases d'un matroïde

Une décomposition du polytope des bases, P(M), d'un matroïde M est une subdivision de P(M) en polytopes P(Mi) telle que 1) P(Mi) est également un polytope des bases d'un matroïde pour un certain matroïde Mi, et 2) l'intersection de P(Mi) et P(Mj) est une face de P(Mi) et de P(Mj). Dans cet exposé, nous étudions la séparation par hyperplan, autrement dit, la décomposition en deux polytopes. Nous donnons des conditions suffisantes sur M pour que P(M) puisse avoir une séparation par hyperplan. Nous caractérisons également les cas où P(M1+M2) a une séparation par hyperplan où M1+M2 dénote la somme directe des matroïdes M1 et M2. Nous montrerons finalement que P(M) n'a pas de séparation par hyperplan si M est binaire.
Transparents de l'exposè

12h15 - 14h
Dèjeuner

14h00-14h45
Emeric GIOAN (Universitè Montpellier 2 - CNRS)
Quelques propriétés structurelles liées aux activités du Polyn˘me de Tutte

15h00 - 15h30
Kevin SOL (Universitè Montpellier 2)
La dètermination du chirotope d'une base en fonction d'ordres sur les coordonés de ses sommets

L'orientation d'un simplexe (chirotopes du matroïde orienté) se calcule en cherchant le signe d'un déterminant. Nous nous intéressons à des simplexes pour lesquels, pour chaque coordonnée de l'espace, un ordre est fixé entre les différents sommets. Selon les ordres choisis, tous les simplexes satisfaisant ces ordres peuvent avoir la même orientation, le signe du déterminant est alors constant, ou bien des simplexes peuvent avoir des orientations différentes en satisfaisant ces mêmes ordres, le déterminant peut alors avoir des signes opposés selon les valeurs prises par les coordonnées. Nous avons montré, pour les cas en 2D et 3D, que ce signe est constant si et seulement si il existe un développement adéquat du déterminant permettant d'en déterminer directement le signe à partir des ordres donnés, et sans calcul numérique. Autrement dit, nous avons un algorithme combinatoire qui décide si un déterminant est de signe constant quelles que soient les coordonnées des points, uniquement à partir d'un ensemble d'ordres sur les coordonnées des points. Nous conjecturons que cette méthode de caractérisation combinatoire se généralise en dimensions supérieures. Mais nous ne nous sommes pas penchés particulièrement sur ces généralisations puisque notre motivation est une application en 3 dimensions. Cette dernière consiste en un codage combinatoire de structures anatomiques à l'aide de matroĽdes orientés, dans le but de classifier des données médicales ou anthropologiques. Pour chaque modèle dont nous souhaitons étudier la forme, nous disposons d'un ensemble de points 3D, dont nous calculons notamment l'orientation de tous les tétraèdres. Sur tous les modèles d'une même structure anatomique, les coordonnées des points 3D respectent certains ordres. Par exemple, sur tous les modèles de crânes, les points du menton sont naturellement avant les points des orbites selon l'axe vertical. Le résultat ci-dessus permet donc de distinguer certains tétraèdres dont l'orientation est déterminée par la forme générale des modèles et non pas par leurs spécificités anatomiques.
Transparents de l'exposè


15h45 - 16h30
Victor CHEPOI (Universitè d'Aix-Marseille)
Graphes des bases des matroïdes et delta-matroïes


16h30 - 17h
Pause

17h - 17h30
Daria STEPANOVA (Universitè Montpellier 2)
Gèomètrie tropicale des éventails de Bergman associés aux matro´des

Dans cet exposé, on explique le lien entre la géométrie tropicale et la théorie des matroïdes donné par la construction d'une M-ultramétrique la plus proche d'un point de IRE présentée par F. Ardila dans Subdominant matroid ultrametrics. On introduit ainsi les outils de base des deux domaines permettant la vision bilatérale sur la convexité combinatoire
Transparents de l'exposè

VENDREDI 25 FEVRIER 2011

9h00 - 9h45
Michel POCCHIOLA (Universitè Pierre et Marie Curie)
Arrangements de double pseudodroites

Une double pseudodroite est une courbe simple fermée du plan projectif homotope à un point et un arrangement de double pseudodroites est une famille finie de double pseudodroites qui s'intersectent deux-à-deux en quatre points et qui induisent deux-à-deux une décomposition cellulaire du plan projectif. Nous présenterons l'état de nos connaissances sur cette classe d'arrangements et les questions que nous nous posons à son sujet.
Transparents de l'exposè

10h - 10h30
Viet-Hang NGUYEN (INP Grenoble)
Regidité des graphes

Une charpente constituée de barres et de joints (bar-and-joint framework) est une paire (G,p) d'un graphe G et un plongement p des sommets de G dans R^d. (G,p) est dit rigide si pour tout déplacement continu préservant la distance entre deux sommets adjacents, la distance entre deux sommets quelconques est préservée. Pour tout plongement générique, la rigidité de la charpente dépend uniquement du graphe. Le problème central de l'étude de la rigidité est de caractériser les graphes dont les charpentes génériques sont rigides. Nous présenterons des résultats connus sur la rigidité générique et des questions ouvertes importantes sur ce sujet.
Travail en commun avec Joseph Cheriyan et Zoltàn Szigeti.
Transparents de l'exposè

10h45 - 11h30
Andràs SEBÖ (INP Grenoble - CNRS)
Problès ouverts sur les bases

Nous avons collecté un bouquet de problèmes naturels sur les bases de matroïdes, qui, pour la plupart conduisent à des questions intéressantes ouvertes pour les arbres des graphes aussi. Peut-on trouver une solution au moins pour des cas géométriques intéressants ? Ou les résoudre en utilisant la présence de multiples compétences ? Nous pourrions donner des réponses, au moins partiels, pendant les trois années qui nous sont accordées.
Transparents de l'exposè
11h30 - 12h
Bilan (discussion projet TEOMATRO)