• Thèmes de recherche
  • Théorie des matroïdes, matroïdes orientés et arrangements d'hyperplans
    
  • Décompositions de graphes et algorithmique
    
  • Codage combinatoire des dessins de graphes, des graphes spatiaux et des objets 3D
    
  • Divers
  
  
• Publications
  • En cours
  • Journaux
  • Conférences
  • Divers
• Divers
  • Présentations des matroïdes et matroïdes orientés
  • Page du Séminaire/Groupe de travail AlGCo (que je coorganise)
  • Page des Matinées Intéractions Mathématiques & Informatique de Montpellier (que j'organise)
  • Stage de recherche (pour Master 2011/2012 Université Montpellier 2)
  • Ressources d'enseignement
  
  

• Thèmes de recherche

  • Théorie des matroïdes, matroïdes orientés et arrangements d'hyperplans.

    Pour des présentations à télécharger des matroïdes et matroïdes orientés, cliquer ici.

    Note. Puisque les matroïdes et matroïdes orientés généralisent les graphes en tant qu'espaces de cycles, les travaux sur ces objets s'appliquent en particulier aux graphes.

    • Polynôme de Tutte.
      Ce polynôme issu de la théorie des graphes (années 50), étendant le polynôme chromatique à deux variables duales, se généralise très bien aux matroïdes, et contient de nombreuses informations structurelles ou énumératives (voir par exemple les préliminaires de ma thèse de [T]). Cet objet est sous-jacent dans plusieurs de mes recherches : [J4] (complexité polynomiale d'évaluation en un point resté partiellement ouvert dans le papier de Jaeger), [J5][J6] (lien avec les systèmes dynamiques de retournements d'arêtes) et surtout celles ci-dessous.
      
      
    • L'application (attr)active des matroïdes orientés ordonnés.
      Avec Michel Las Vergnas, nous avons défini et étudié une application générale et naturelle qui à un matroïde orienté ordonné associe une de ses bases, qui induit une correspondance préservant les activités (modèles d'étât du polynôme de Tutte) entre réorientations et bases d'un matroïde orienté donné. Diverses bijections appelées bijections actives apparaissent alors comme raffinements ou comme cas particuliers dans des contextes variés. Elle utilise d'une part la dualité et des décompositions des activités, et étend d'autre part la traduction combinatoire de la programmation linéaire. Pour un résumé plus précis d'après ma thèse, cliquer ici . Voir [C4] pour un condensé récent de l'ensemble en 7 pages, [C8] pour un condensé récent de la partie programmation linéaire, [C2] pour une vue d'ensemble plus ancienne mais plus complète (sauf programmation linéaire). Pour les constructions détaillées, voir [J7][R2-4], ainsi que [J1] pour le cas uniforme, [J2][R1] pour le cas des graphes, et [J3] pour le cas hyperrésoluble. Ces constructions ont été soit décrites soit ébauchées dans ma thèse [T].

    haut de page

  • Décompositions de graphes et algorithmique.

    Mes recherches sur ce thème s'intègrent actuellement au Projet ANR "Décompositions de Graphes et Algorithmes" (GRAAL).
    
    
    • Décomposition en splits.
      Avec Christophe Paul, nous travaillons sur des reformulations, applications, et généralisations de la décomposition en splits d'un graphe introduite par Cunningham. Nous en définissons une nouvelle représentation en termes d'arbres étiquetés par des graphes, capturant également la décomposition modulaire. Dans ce cadre, nous avons obtenu un algorithme dynamique optimal (linéaire) de reconnaisance des graphes distances héréditaires, pour l'insertion/suppression de sommets/arêtes, ainsi qu'un modèle d'intersection pour ces graphes (répondant à une question ouverte de Jeremy Spinrad), et ainsi que des algorithmes similaires pour des sous-classes (cographes, et graphes 3-leaf power). Voir [C5][J8].
      
      
    • Enumération et structure des orientations d'un graphe.
      Le point de vue des matroïdes orientés, qui n'utilise pas de sommets, et a une notion intrinsèque de dualité (même pour des graphes non planaires), permet de faire apparaître des propriétés structurelles et énumératives originales des graphes orientés. Par exemple en utilisant les décompositions entre sous graphes totalement cycliques (ou fortement connexes) et acycliques. On peut raffiner cette décomposition pour décomposer les orientations d'un graphe ordonné en orientations bipolaires. Ceci généralise la décomposition en composantes d'orientations acycliques pour un ordre des sommets de Viennot, étudiée par exemple par Bodo Lass. Et une décomposition similaire existe pour les arbres. De cette façon, la correspondance active mentionnée plus haut dans les matroïdes orientés étudiée avec Michel Las Vergnas, donne en particulier des bijections actives liées au polynôme de Tutte entre arbres couvrants et orientations d'un graphe ordonné, ou encore entre sous-ensembles d'arêtes (sans circuit brisé) et orientations (acycliques), voir [J2][C4].

    haut de page

  • Codage combinatoire des dessins de graphes, des graphes spatiaux et des objets 3D.

    Ces recherches s'intègrent au Projet OMSMO: Oriented Matroids for Shape Modeling.
    
    
    • Structure logique des dessins de graphes.
      J'ai étudié une strucutre logique, intermédiaire entre la 'carte planaire' et le 'sketch' utilisé par Bruno Courcelle, permettant d'axiomatiser les dessins du graphe complet à mutation de triangles près. Ceci étend le théorème de Ringel des arrangements de pseudodroites, et s'applique en particulier aux projections de graphes spatiaux codés par des matroïdes orientés. Voir [C3].
      
      
    • Objets 3D et matroïdes orientés.
      Je travaille, notamment avec Gérard Subsol et Kevin Sol, sur des propriétés des objets 3D codées par leurs matroïdes orientés associés. Un exemple est donné par le sujet précédent.

    haut de page

  • Divers.

    • Systèmes dynamiques sur les graphes (tas de sable, chip firing game, edge firing game...).
      J'ai étudié des configurations de systèmes dynamiques sur les graphes orientés (et matroïdes réguliers) à partir d'un principe nouveau, qui est de généraliser les retournements de puits à des retournements auto-duaux de cycles et cocycles, faisant ainsi apparaître certaines propriétés structurelles et énumératives pour ces systèmes, voir [J5][J6]. Le point de vue est similaire à celui présenté plus haut sur les décomposition de graphes orientés et lié encore au polynôme de Tutte. Voir également les travaux récents de Olivier Bernardi, notamment pour une jolie réponse à une question bijective que je posais dans [J5] sur un lien avec le modèle du tas de sable. Ces systèmes s'inscrivent en particulier dans la modélisation des phénomènes complexes par des automates cellulaires, on observe en effet des similitudes de comportement avec les phénomènes physiques comme le tas de sable, les avalanches, les tremblements de terre... Pour plus d'informations, voir par exemple le site de Dominique Rossin.
      
      
    • Programmation d'applications sans utiliser de mémoire.
      Avec Serge Burckel, qui est à l'initiative de ces recherches par ses travaux passés, et avec Emmanuel Thomé, nous avons travaillé à des techniques dont le principe est d'implémenter une application sur un ensemble produit fini en modifiant les coordonnées une par une, et sans utiliser d'autre variable que les variables d'entrées. Nous appelons programmation in situ ce mode de programmation. Nous montrons que c'est toujours possible et en un nombre d'assignations linéaire en l'exposant. Voir [R5][C7] pour les constructions détaillées, ou [C6] pour une courte note destinée aux micro-électroniciens. Ces techniques pourraient en effet s'appliquer à l'optimisation des calculs dans les processeurs d'ordinateurs, ce pour quoi un brevet a été déposé, voir [B].

    haut de page

  ---

  
  

• Publications

  • En cours

    • [R9] Avec Kevin Sol et Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices.
      Soumis. Voir [C9] pour une version préliminaire de conférence.
      Liens thématiques : formes 3D.
      
      
    • [R8] Avec Christophe Crespelle, Christophe Paul. Dynamic circle graph recognition.
      En préparation. Liens thématiques : split decomposition.
      
      
    • [R7] Avec Christophe Paul, Marc Tedder, Derek Corneil. Circle Graph Recognition in Time O(n+m).\alpha(n+m).
      Soumis. Télécharger : sur arXiv. Liens thématiques : split decomposition.
      
      
    • [R6] Avec Christophe Paul, Marc Tedder, Derek Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees.
      Soumis. Télécharger : sur arXiv. Liens thématiques: split decomposition.
      
      
    • [R5] Avec Serge Burckel et Emmanuel Thomé. Mapping computation with no memory, and Rearrangeable Nonblocking Multicast Networks based on Concatenation of Butterflies.
      Soumis. Voir [C7] pour une version préliminaire de conférence de cet article. Voir [C6] pour une courte note destinée aux micro-électroniciens. Voir [B] pour un brevet sur ces techniques.
      Liens thématiques : programmation in situ.
      
      
    • [R2-4] Avec Michel Las Vergnas. The active bijection in graphs, hyperplane arrangements, and oriented matroids.
      
      • 2. Decomposition of activities.
      • 3. Linear programming construction of fully optimal bases.
      • 4. Deletion/contraction constructions and universality.
        
      Série de papiers en préparation. Voir [J7] pour le n°1 de la série. Voir [C4] pour un condensé récent et disponible de l'ensemble en 7 pages. Voir [C8] pour un résumé étendu du n°3.
      Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [R1] Avec Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs 2.
      En préparation. Suite de [J2] : compléments et synthèse de résultats récents appliqués au cas des graphes.
      Liens thématiques : polynôme de Tutte , bijections actives.
      
      

    haut de page

  • Journaux

    • [J8] Avec Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs.
      A paraître dans Discrete Applied Mathematics. Voir [C5] pour une version courte et très partielle de conférence.
      Résumé. Télécharger : sur arXiv. Liens thématiques : split décomposition.
      
      
    • [J7] Avec Michel Las Vergnas. The active bijection in graphs, hyperplane arrangements, and oriented matroids - 1 - The fully optimal basis of a bounded region.
      (Special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids) European Journal of Combinatorics, volume 30 issue 8, pp 1868--1886, (2009)
      Résumé. Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [J6] Circuit-cocircuit reversing systems in regular matroids.
      (Special issue Workshop on Tutte polynomials, Barcelona 2005) Annals of Combinatorics, Vol. 12, pp. 171-182, (2008).
      Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , systèmes dynamiques .
      
      
    • [J5] Enumerating degree sequences in digraphs and a cycle-cocycle reversing system.
      European Journal of Combinatorics 28 (4): 1351--1366 (2007).
      Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , systèmes dynamiques .
      
      
    • [J4] Avec Michel Las Vergnas. On the evaluation at (j,j²) of the Tutte polynomial of a ternary matroid.
      Journal of Algebraic Combinatorics 25: 1-6 (2007).
      Télécharger : ps pdf. Liens thématiques : polynôme de Tutte .
      
      
    • [J3] Avec Michel Las Vergnas. The active bijection between regions and simplices in supersolvable arrangements of hyperplanes.
      (Stanley Festschrift) Electronic Journal of Combinatorics 11(2) #R30, 39p (2006).
      Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [J2] Avec Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs.
      (Special issue FPSAC 2002) Discrete Mathematics 298: 169--188 (2005).
      Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [J1] Avec Michel Las Vergnas. Bases, reorientations, and linear programming, in uniform and rank 3 oriented matroids.
      (Special issue Workshop on Tutte polynomials, Barcelona 2001) Advances in Applied Mathematics 32, 212--238 (2004)
      Télécharger : ps pdf. ERRATA : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      

    haut de page

  • Conférences

    • [C9] Avec Kevin Sol et Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices.
      Proceedings CCCG'2011, 6p. (2011). Version sans preuves de [R9].
      Télécharger : pdf. Liens thématiques : formes 3D.
      
      
    • [C8] - Note/Résumé - Avec Michel Las Vergnas. A linear programming construction of fully optimal bases in graphs and hyperplane arrangements.
      Proceedings EuroComb 2009 (Bordeaux), Electronic Notes in Discrete Mathematics, 34, pp. 307-311, (2009).
      Résumé. Télécharger : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [C7] Avec Serge Burckel et Emmanuel Thomé. Mapping computation with no memory
      Proceedings Unconventional Computation 2009 (Açores), LNCS 5715, pp. 85-97 (2009)
      Résumé. Télécharger : ps pdf. Liens thématiques : programmation in situ.
      
      
    • [C6] With Serge Burckel. In situ design of register operations.
      Proceedings of ISVLSI 2008, IEEE Computer Society Annual Symposium on Very-Large-Scale Integration (Montpellier) (2008).
      Télécharger: ps pdf. Lien thématique: programmation in situ .
      
      
    • [C5] Avec Christophe Paul. Dynamic distance hereditary graphs using split decomposition.
      Proceedings ISAAC 2007 (Sendai), LNCS 4835, pp 41--51 (2007).
      Télécharger : ps pdf. Transparents de l'exposé : ps pdf. Liens thématiques : split décomposition.
      
      
    • [C4] - Note/Résumé - Avec Michel Las Vergnas. Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids.
      Proceedings EuroComb 2007 (Sevilla), Electronic Notes in Discrete Mathematics 29, pp 365--371 (2007).
      Télécharger : ps pdf. Transparents de l'exposé : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [C3] Complete graph drawings up to triangle mutations.
      Proceedings WG 2005 (Metz), LNCS 3787, pp139-150 (2005)
      Télécharger : ps pdf. Transparents d'un exposé plus général sur le sujet à CSL 06 : ps pdf. Liens thématiques : dessins de graphes.
      
      
    • [C2] - Survey - Avec Michel Las Vergnas. On a natural correspondence between bases and reorientations, related to the Tutte polynomial and linear programming, in graphs, hyperplane arrangements, and oriented matroids.
      Proceedings FPSAC 2003 (Linköping).
      Télécharger : ps pdf. Transparents de l'exposé : ps pdf. Liens thématiques : polynôme de Tutte , bijections actives.
      
      
    • [C1] Avec Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs.
      Proceedings FPSAC 2002 (Melbourne).
      Ce papier obsolète est une version tronquée de [J2].
      

    haut de page

  • Divers

    • Brevet

      [B] Avec Serge Burckel, et l'Université de la Réunion. Implémentation de calculs pour processeurs.
      Numéro INPI d'enregistrement national : 07 05152. Date de dépôt : 17/07/2007. Date de publication : 25/03/2011.
      Liens thématiques : programmation in situ .
      

      haut de page

    • Résumés (conférences sans actes étendus)

      • [A2] Avec K. Sol, G. Subsol, Y.Heuzé, J. Richtsmeier, J. Braga, F. Thackeray. A new 3D morphometric method based on a combinatorial encoding of 3D point confguration: application to skull anatomy for clinical research and physical antropology.
        Poster : 80th annual meeting of the American Association of physical antropologists (Minneapolis, USA, April 12-16, 2011). Résumé : American Journal of Physical Antropology 144 (S52) (2011), 280
        Liens thématiques : formes 3D.
      
      
      • [A1] Avec K. Sol, G. Subsol, J. Braga, J. Treil. Une nouvelle méthode de morphométrie 3D par codage combinatoire de confgurations de points 3D: application à l'anatomie du crâne.
        1836èmes Journées de la Societé d'Anthropologie de Paris (26-28 janvier 2011).
        Liens thématiques : formes 3D.
      
      

      haut de page

    • Thèse

      [T] Correspondance naturelle entre bases et réorientations des matroïdes orientés.
      Spécialité Informatique mention Mathématiques Discrètes (18 décembre 2002).
      Thèse de doctorat de l'Université Bordeaux 1, codirigée par Bruno Courcelle et Michel Las Vergnas.
      Télécharger : ps.zip (702 Ko) pdf.zip (1027 Ko). Liens thématiques : polynôme de Tutte , bijections actives.
      
      Résumé : cliquer ici. Résumé ludique d'un cas particulier (Récréation) : ps pdf
      
      Note. Les articles [J1], [J2] et [J3] reprennent respectivement les cas particuliers 6.2, 6.1 + 6.4, et 6.3 du chapitre 6, et apportent de nouveaux résultats. La série d'article [R1-3] n°1, n°2, n°4 reprend respectivement les chapitres 3, 2, 1 + 4, et en reformule ou en précise certains points. Le n°3 développe précisément une ébauche restée en suspens dans le chapitre 3. L'article [C2] est une vue générale assez détaillée de l'ensemble (sauf optimisation). Et l'article [C4] est un condensé succint et récent décrivant l'essentiel de l'ensemble.
      

  haut de page

  ---

  
  

• Divers

  • Présentations des matroïdes et matroïdes orientés

    • Un Petit récapitulatif sur les matroïdes et matroïdes orientés (court mais précis, 23 pages) : ps pdf
      
      
    • Un exposé sur l'Axiomatisation logique des arrangements de pseudodroites (et des dessins de graphes) introduisant les matroïdes orientés de rangs 3 (et 4) : ps pdf.
      
      
    • Deux exposés Les matroïdes et matroïdes orientés, objets combinatoires, géométriques et algébriques (résultats variés sans approfondissement) :
      exposé 1 (matroïdes et sommaire) ps pdf, exposé 2 (matroïdes orientés) ps pdf.
      
      
    • Une Récréation, jeu sur les arrangements de pseudodroites ne nécessitant aucune connaissance préalable : ps pdf
      
      
    • Un lien sur les matroïdes orientés : homepage of oriented matroids.

    recherches sur ces thèmes

    haut de page

  • Ressources d'enseignement

    • Enseignement assisté par ordinateur (sur le serveur WIMS) : exercices aléatoires, solutions adaptées, expliquées et illustrées.

      Module sur la Théorie des jeux
      
      Module sur les Processus stochastiques discrets

      Télécharger les codes (WIMS + Pari TEX HTML) : ici.
      
      
      
    • Polycopié Introduction à la cryptographie (cours de 40 pages, et 4 exercices corrigés).

      Résumé. La cryptographie (art de crypter des messages), et son ennemie la cryptanalyse (art de déchiffrer des messages codés), sont des disciplines scientifiques omniprésentes aujourd'hui dans la société, aussi bien civile que militaire, commerciale ou politique.
      Ce cours d'introduction présente les algorithmes de cryptographie couramment utilisés à la fois :
      - d'un point de vue culturel, à travers l'histoire et l'actualité,
      - d'un point de vue théorique, par des résultats mathématiques surtout en théorie des nombres, mais aussi en probabilités et en complexité,
      - d'un point de vue pratique, par leur mise en place informatique, accompagnée des protocoles indispensables (identification, authentification...).
      Le but est de donner ici un aperçu de la grande variété de problèmes et de pratiques relatifs à la cryptographie, quitte à ce que la plupart des notions ne soient pas approfondies.
      

      Télécharger : ps pdf.
      

haut de page