Hypergraphe autotransversal
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Un hypergraphe autotransversal (self-blocking en anglais) est un hypergraphe qui est égal à l'ensemble de ses arêtes transversales minimales.
Par exemple, un ensemble de mots est un hypergraphe autotransversal s'il a les propriétés suivantes :
- chaque paire de mots a au moins une lettre en commun ;
- chaque mot est minimal (si on lui ôte une lettre la première propriété n'est plus vérifiée) ;
- si on pioche une lettre dans chaque mot l'ensemble obtenu doit contenir un mot du groupe.
On peut remarquer que ce groupe de mots est un hypergraphe intersectant non bicolorable.
Voici deux autotransversaux qui sont 3-uniformes :
- (eau, réa, êta, rua, tua, rue, tue, rut, rat, ter) (ordre 5) ;
- (eau, rat, tua, set, sur, sût, rut, ras, sua, tas) (ordre 6).
Voici encore un exemple :
- (riens, site, tire, nets, tirs, ras, tas, tan, êta, ait, rat, ais, aïe, réa, ase, nia) (ordre 7).
- bien plus dur: le plan projectif (ordre 7):(eau, sel, pie, ais, pal, pus, lui). c'est le seul plan projectif qui soit autotransversal.
Références[modifier | modifier le code]
- Olivier Flandre, Quelques problèmes concernant les hypergraphes autotransversaux; généralisation des treillis continus, Thèse de doctorat de l'université de Perpignan, 1992, cote INIST T 87022.
