Nicolas juge - Arithmétique et combinatoire effectives des cartes cellulaires

Thèse Arithmétique et combinatoire effectives des cartes cellulaires de Nicolas Juge, soutenue le 13 octobre 2005 à l'Université François Rabelais, Tours.

Résumé :

Partant de la classification des cartes cellulaires obtenues par P. Damphousse à la suite d'un travail initié par A. Grothendieck, nous proposons un codage "compact", effectif, de toutes les cartes (dans la pratique finie), orientables ou non. Sur la base de ce codage nous avons développé des algorithmes permettant de "voyager dans le dictionnaire combinatoire <-> topologie" de la classification des cartes cellulaires. Nous résolvons de manière efficace, entre autres, le problème de la reconnaissance des cartes (tests d'isomorphie), celui de la déterminant des invariants topologiques usuels de la surface sous-jacente à une carte (genre, orientabilité, connexité et nombre de composantes, caractéristique d'Euler-Poincarré), celui du calcul effectif des limites usuelles de la catégorie des cartes cellulaires. Le résultat de ce travail est un logiciel de topologie combinatoire, appelé Humboldt, composé de trois programmes principaux : cmshell, cmedit et cmatlas.

 

Starting from the classification of cellular maps (CM) obtained by P. Damphousse, extending an original idea of A. Grothendieck, we propose a compact and efficient encoding of all CM, not necessarily orientable (finite in practice). Using this encoding, we have developped algorithms for "travelling in both directions between combinatorics and topology ". We solve, among others, the identification problem (isomorphy test), and the problem of computing usual topological invariants of the underlying surface of a CM (genus, orentability, number of connected components, Euler characteristic). We also show how to compute usual limits in the category of CM. The result of this work is a combinatorial topology software, called Humboldt, composed of 3 main programs : cmshell, cmedit and cmatlas.

Auteurs