Concept

Système de Steiner

Résumé
En mathématiques, et plus particulièrement en combinatoire, un système de Steiner (nommé ainsi d'après Jakob Steiner) est un type de design combinatoire. Plus précisément, un système de Steiner de paramètres t, k, n, noté S(t,k,n), est constitué d'un ensemble S à n éléments, et d'un ensemble de sous-ensembles de S à k éléments (appelés blocs), ayant la propriété que tout sous-ensemble de S à t éléments est contenu dans un bloc et un seul (cette définition moderne généralise celle de Steiner, demandant en plus que k = t + 1). Un S(2,3,n) est appelé un système de Steiner de triplets , un S(3,4,n) est un système de Steiner de quadruplets, et ainsi de suite. Jusqu’en 2014, on ne connaissait aucun système de Steiner pour t > 5, mais leur existence a été alors démontrée, bien que de manière non constructive. Un plan projectif fini d'ordre q, les blocs étant ses droites, est un , puisqu'il a points, que chaque droite contient points, et que chaque paire de points appartient à une droite et une seule. Un plan affine d'ordre q est un S(2, q, q2), les droites étant les blocs. Un plan affine d'ordre q peut être obtenu à partir d'un plan projectif de même ordre en en retirant un bloc et tous les points de ce bloc (autrement dit, en choisissant et en supprimant une droite à l'infini). Des choix de blocs différents peuvent amener à des plans affines non isomorphes. Un S(2,3,n) s'appelle un système de Steiner de triplets (les blocs étant appelés des triplets) ; on voit souvent l'abréviation STS(n). Le nombre de triplets est n(n−1)/6. Une condition nécessaire et suffisante d'existence d'un S(2,3,n) est que n 1 ou 3 (mod 6). Le plan projectif d'ordre 2 (le plan de Fano) est un STS(7), et le plan affine d'ordre 3 est un STS(9). À isomorphisme près, il n'y a qu'un STS(7) et un STS(9), mais il y a deux STS(13), 80 STS(15), et 11 084 874 829 STS(19). Partant d'un système de Steiner de triplets, on peut définir une multiplication sur l'ensemble S en posant aa = a pour tous les a de S, et ab = c si {a,b,c} est un triplet.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.