ARITH


Evénements

Groupes de travail

Intranet (restricted)

JCALM 2008

Les Journées Combinatoire et Algorithmes du Littoral Méditerranéen ont eu lieu les 13 et 14 octobre 2008 au LIRMM (Montpellier).

On this page... (hide)

  1. 1. Thème
  2. 2. Mots clefs
  3. 3. Résumé
  4. 4. Programme
  5. 5. Organisation

1.  Thème

Les stables transversaux

2.  Mots clefs

Graph domination, Perfect matching, Independent Systems of Representatives, Hall's matching theorem, Sperner's lemma, Simplicial homology.

3.  Résumé

Le thème principal de ces journées CALM est la recherche d'un ensemble stable S (i.e. un ensemble de sommets deux à deux non reliés par une arête) dans un graphe G. Une contrainte supplémentaire étant que l'ensemble des sommets V de G est partitionné en sous-ensembles V1,...,Vk et que le stable S considéré doit intersecter chaque Vi en exactement un point.

On dit alors que S est un stable transversal de G partitionné en V1,...,Vk.

Ce problème est sans grande surprise NP-complet. En effet, il est aisé d'exprimer des problèmes classiques tels que 3-SAT (les partitions sont les clauses, et les arêtes relient chaque littéral à sa négation), ou encore la coloration par liste, etc

Le but de ces JCALM est de présenter des outils qui permettent d'obtenir des conditions suffisantes à l'existence d'un stable transversal.

Ces outils sont de deux types:

  • Certains, les plus puissants, de nature topologique s'expriment de la façon suivante : si pour tout choix d'un sous-ensemble de k parties Vi, la valeur d'un certain invariant {{$\eta$}}, restreint au graphe induit par cette union de Vi est au moins k, alors un stable transversal existe. La fonction {{$\eta$}} s'exprime en terme de connexité du complexe des stables de G.
  • D'autres, de nature combinatoire, s'expriment en termes de domination de graphes. Par exemple si la restriction de G à l'union de k sous-ensembles Vi a pour nombre de domination totale au moins 2k, alors un stable transversal existe.

Les principales publications concernant la recherche de stables tranversaux sont dues à Ron Aharoni, Eli Berger, Penny Haxell, Ron Holzman et Roy Meshulam. Un survey de leurs résultats sera proposé ici.

4.  Programme

  • lundi 13 octobre (salle 50, bâtiment 1)
    • 10h00 - 11h00 : Stéphan Thomassé - Independent Sets of Representative and their applications.
    • 11h30 - 12h30 : Penny Haxell - The combinatorial proof of Hall's theorem for hypergraphs.
    • 14h00 - 15h00 : Ron Aharoni - The topological theorem and the Sperner proof. Introduction to the {{$\eta$}} function.
    • 15h30 - 16h30 : Thierry Monteil - The Meshulam game and its corollaries.
  • mardi 14 octobre (salle 28 le matin, salle 31 l'après-midi, bâtiment 2)
    • 9h30 - 10h30 : Ron Holzman - Independence/Domination duality.
    • 11h00 - 12h00 : Penny Haxell - Colorability and strong colorability.
    • 14h00 - 15h00 : Ron Aharoni - General complexes and matroids.

5.  Organisation

  • Contacts
  • Lieu
  • Présentation des JCALM et journées précédentes
  • Participant-e-s
    • Orateurs invités
      • Ron Aharoni
      • Penny Haxell
      • Ron Holzman
    • Bordeaux
      • Frédéric Mazoit
      • Michael Rao
    • Lyon
      • Maurice Pouzet
    • Marseille
      • Victor Chepoi
      • Yann Vaxès
      • Thomas Fernique
      • Emmanuel Godard
    • Montpellier
      • Annie Lacasse
      • Christian Mercat
      • Xavier Provençal
      • Thierry Monteil
      • Stephan Thomassé
      • Valérie Berthé
      • Emeric Gioan
      • Stéphane Bessy
      • Daniel Gonçalves
      • Philippe Janssen
      • Christophe Paul
      • Geneviève Simonet
      • Marie-Catherine Vilarem
      • Alexandre Pinlou
      • Jean Daligault
      • Philippe Gambette
      • Anthony Perez
      • Eric Bourreau
    • Nice
      • Marie Aste
      • Nathann Cohen
      • Frederic Giroire
      • Frederic Havet
      • Dorian Marauzic
      • Nicolas Nisse
      • Shmuel Saks
      • Ignasi Sau-Valls
    • Paris
      • Omid Amini
      • Pierre Charbit
      • David Auger
Cette page fait partie du groupe JCALM2008
Page last modified on 11 October 2012 à 19h48