Hypergraphes : théorie de Sperner.

Les hypergraphes généralisent la notion de graphe en définissant sur un ensemble fixé V des hyperarêtes qui contiennent autant de sommets que l'on veut, contrairement aux arêtes classiques qui ne joignent que deux sommets. Un livre de référence est celui de Berge intitulé "Hypergraphes" (les premières définitions sont données au début de son chapître 1). Du point de vue, théorique les hypergraphes permettent de généraliser certains théorèmes de graphes, voire de factoriser plusieurs théorèmes de graphes en un seul théorème d'hypergraphes. Du point de vue pratique, ils sont parfois préférés aux graphes car modélisant mieux certains types de contraintes.

Les hypergraphes sont des objets très généraux : ce sont des familles de parties. Plusieurs directions ont été explorées en spécifiant certaines propriétés de ces familles de parties (parfois sans référence directe à des problèmes de graphes). Plutôt que de parler d'hypergraphes, les auteurs préférent alors mentionner les théories plus spécifiques correspondant aux propriétés étudiées, par exemple : la théorie de Sperner (étude des familles de parties par rapport à la relation d'inclusion qui est une relation d'ordre) ou la théorie des Matroïdes (étude des familles de parties closes pour la notion de sous-partie et pouvant se "compléter" les unes les autres).

L'objectif ici est de donner un survol de la théorie de Sperner, avec des illustrations des liens avec la théorie des graphes. Les questions qui suivent peuvent donner quelques pistes :

• Un hypergraphe simple est un hypergraphe qui ne contient pas deux hyperarêtes telles que l'une est incluse dans l'autre. Etant donné V avec n sommets, quel est le nombre maximum d'hyperarêtes d'un hypergraphe simple sur V ? La réponse est le coefficient binomial n/2 pris parmi n. Ce théorème démontré par Sperner en 1928 est souvent considéré comme fondateur d'un champ de la combinatoire baptisé théorie de Sperner. Noter que le théorème de Sperner ainsi que tous les théorèmes qui lui sont reliés sont souvent exprimés sans faire référence aux hypergraphes et en utilisant plutôt des notions de structures ordonnées (par exemple chaînes ou antichaînes pour l'ordre d'inclusion sur les parties).
• En très bref la théorie de Sperner est l'étude de familles de parties d'un ensemble fixé V vérifiant des propriétés exprimables en terme d'intersections, unions ou inclusions. Outre le théorème de Sperner (qui a de multiples démonstrations), on peut citer le théorème de Erdös-Ko-Rado (qui trouve des applications en probabilités comme le théorème de Liggett), le théorème de Fortuin, Kasteleyn, Ginibre (donnant lieu à l'inégalité FKG qui a permis de démontrer la conjecture XYZ), les solutions combinatoires au problème de Littlewood-Offord (soit n réels x_i de valeurs absolues au moins 1, parmi les 2ⁿ sommes de la forme Σ s_ix_i avec s_i= ± 1, combien au maximum y en a-t-il de valeur absolue au plus 1 ?) ... Vous pouvez présenter une sélection de certains de ces résultats.

Quelques références (pas exhaustif).

• Combinatorics of finite sets, livre de I. Anderson, Oxford University Press (1989). Un excellent livre sur la théorie de Sperner.
• Hypergraphes, livre de C. Berge, Gauthier-Villars (1987). Ce livre a un peu vieilli mais garde un intérêt historique.

Retour à la page des sujets.