En mathématiques combinatoires, un plan en blocs est un ensemble (dont les éléments sont appelés des points) muni d'une famille de parties appelées des blocs, satisfaisant des propriétés issues nombreux domaines, notamment celui des plans d'expériences, de la géométrie finie, de la chimie physique, des tests de logiciels, de la cryptographie et de la géométrie algébrique. De nombreuses variantes de ces plans ont été examinées, mais les plus étudiés sont les plans en blocs incomplets équilibrés, abrégé en BIBD pour balanced incomplete block designs, ou parfois 2-plans, qui sont historiquement liés à des problèmes statistiques dans des plans d'expériences....
Un plan en blocs dans lequel tous les blocs ont la même taille est dit uniforme. Les plans décrits dans cette page sont tous uniformes. Les plans équilibrés par paires sont des exemples de plans en blocs qui ne sont pas nécessairement uniformes.
La notion de plan en blocs est équivalente à celle d'hypergraphe, où les blocs sont alors appelés les arêtes, et les points les sommets de l'hypergraphe.
Définition d'un plan en blocs incomplet équilibré (ou 2-plan) vignette|La configuration de l'hexagramme de Pascal présente points et blocs, blocs contenant un point, bloc contenant 2 points distincts, mais ce n'est pas un plan en blocs équilibré car il n'est pas uniforme (un bloc contient 6 points, les autres 3). Étant donné un ensemble fini (dont les éléments sont appelés points) et des entiers , on définit un plan en blocs incomplet équilibré ou 2-plan (ou BIBD) comme une famille de parties à éléments de , appelées les blocs, telles que tout point de appartient à blocs, et que toute paire de points distincts et de est incluse dans blocs.
Le terme famille dans la définition ci-dessus peut être remplacé par ensemble s'il n'y a pas de répétition de blocs. Les plans sans blocs répétés sont dits simples.
L'entier (le nombre de points, c'est-à-dire le nombre d'éléments de ) , l'entier (le nombre de blocs), et les entiers sont les paramètres du plan. Pour éviter les cas dégénérés, on suppose également que , de sorte qu'aucun bloc ne contient tous les éléments de l'ensemble (c'est le sens du terme incomplet dans le nom de ces plans). La table suivante résume les paramètres : {| class="wikitable" | |nombre de points (éléments de )
|nombre de blocs
|nombre de blocs contenant un point donné
|nombre de points dans un bloc
|nombre de blocs contenant 2 (ou plus généralement t pour un t-plan) points distincts donnés |} Le plan est appelé un 2-plan de paramètres , ou un 2-plan, ou encore un 2-plan de paramètres . Les paramètres ne sont pas tous indépendants : , et déterminent et , et les combinaisons de , et ne sont pas toutes possibles. Les deux relations de base reliant ces paramètres sont
que l'on obtient en comptant de deux façons le nombre de couples où est un bloc et un point de ce bloc, et
,
que l'on obtient en fixant un point et en comptant de deux façons le nombre de couples où est un point distinct de et un bloc qui les contient. Les paramètres et sont donc déterminés en fonction de par puis .
Ces conditions ne sont pas suffisantes ; par exemple, un plan de paramètres n'existe pas, bien que et soient entiersCe résultat a été démontré par Tarry en 1900 : il n'existe pas de paire de carrés latins orthogonaux d'ordre six. Le 2-design avec ces paramètres est équivalent à l'existence de cinq carrés latins d'ordre six deux à deux orthogonaux..
L'ordre d'un 2-plan est par définition le nombre . Le 2-plan complémentaire est obtenu en remplaçant chaque bloc par son complémentaire dans l'ensemble des points . C'est également un 2-plan avec les paramètres , , , , . Un 2-plan et son complémentaire ont le même ordre.
Un théorème fondamental, l'inégalité de Fisher, du nom du statisticien Ronald Fisher, est que dans tout 2-plan, on a l'inégalité , donc .
Exemples
L'unique 2-plan de paramètres possède 10 blocs () et chaque point appartient à 5 blocs ().. On peut le représenter par la matrice d'incidence suivante où le terme de la ligne et de la colonne vaut 1 ssi le point appartient au bloc : {| class="wikitable" |+ ! ! ! ! ! ! !
|1 |1 |1 |0 |0 |0
|1 |1 |0 |1 |0 |0
|1 |0 |1 |0 |1 |0
|1 |0 |0 |1 |0 |1
|1 |0 |0 |0 |1 |1
|0 |1 |1 |0 |0 |1
|0 |1 |0 |1 |1 |0
|0 |1 |0 |0 |1 |1
|0 |0 |1 |1 |1 |0
|0 |0 |1 |1 |0 |1 |} La somme des termes de chaque colonne est égale à , la somme des termes de chaque ligne est égale à , et le fait que se traduit par le fait que la somme de deux colonnes contient exactement deux termes égaux à 2.
L'unique 2-plan de paramètres possède 7 blocs, chaque point appartenant à 3 blocs. Sa matrice d'incidence est : {| class="wikitable" |+ ! ! ! ! ! ! ! !
|1 |1 |0 |1 |0 |0 |0
|1 |0 |1 |0 |0 |0 |1
|1 |0 |0 |0 |1 |1 |0
|0 |1 |1 |0 |1 |0 |0
|0 |1 |0 |0 |0 |1 |1
|0 |0 |1 |1 |0 |1 |0
|0 |0 |0 |1 |1 |0 |1 |} La somme des termes de chaque colonne est égale à , la somme des termes de chaque ligne est égale à , et le fait que se traduit par le fait que la somme de deux colonnes contient exactement un terme égal à 2. Si les points sont vus comme les points d'un plan de Fano, alors les blocs en sont les droites. droite|vignette|200x200px|Plan affine fini d'ordre , possédant points et droites de points chacune. Par chaque point passent droites. Il existe quatre 2-plans non isomorphes de paramètres , chacun possédant 14 blocs, et chaque point appartenant à 7 blocs. En utilisant les symboles de 0 à 7 pour représenter les points, un exemple est donné par les blocs suivants : 0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.
Le plan affine fini d'ordre est un 2-plan de paramètres .
vignette|326x326px|Deux des 13 cartes du jeu « cherche et trouve » dont il faut retrouver les 2 symboles communs.
Plan en bloc dual Comme pour la notion d'hypergraphe, on peut considérer le plan en blocs dual obtenu en échangeant les points et les blocs (donc en transposant la matrice d'incidence). Les nombres de points et de blocs s'échangent, et les nombre de points par bloc et nombre de blocs par point s'échangent aussi. Le nombre de blocs contenant deux points donnés devient alors le nombre constant de points communs à deux blocs.
Cette dernière propriété est à l'origine de la conception de jeux d'observation où l'on doit retrouver rapidement symboles communs dessinés sur deux cartes.
Le jeu dobble en est un exemple avec . S'il était complet le jeu comporterait cartes utilisant symboles, chaque carte comportant symboles par cartes et chaque symbole se retrouvant sur cartes.
Le jeu « cherche et trouve » est un exemple avec . Il comporte cartes utilisant symboles, chaque carte comportant symboles, et chaque symbole se retrouvant sur cartes. Il est construit sur le dual d'un 2-plan de paramètres , vérifiant bien .
Plans en blocs symétriques Un 2-plan qui a le même nombre de points et de blocs est dit symétrique. C'est le cas de l'égalité dans l'inégalité de FisherIls ont également été appelés « design projectifs » (projective designs) ou « designs carrés » (square designs) dans le but de remplacer l'adjectif « symétrique » "symmetric", puisque dans ces designs, rien n’est symétrique au sensusuel du terme). L'usage de projective est dû à P.Dembowski (Finite Geometries, Springer, 1968), en analogie avec l'exemple le plus courant, les plans projectifs, alors que square est dû à P. Cameron (Designs, Graphs, Codes and their Links, Cambridge, 1991) est illustre l'implication v = b dans la matrice d'incidence. Ni l'un ni l'auyre de ces termes a été adopté, et ces designs continuent à être appelés symétrique.. Les plans symétriques ont le plus petit nombre de blocs parmi les 2-plans d'un nombre de points donné.
Dans un 2-plan symétrique, on a les égalités et , et deux blocs distincts ont points en commun, il est donc son propre dual.. Un théorème de Ryser dit que l'inverse est également vrai : Si est un ensemble à éléments et est un ensemble de parties à éléments de (les "blocs") tels que deux blocs distincts ont exactement points en commun, alors est un plan en blocs symétrique..
Les paramètres d'un plan symétrique satisfont à la relation :
, soit .
D'après le théorème de Bruck-Ryser-Chowla, une condition d'existence supplémentaire, nécessaire mais non suffisante sauf pour , est que. :
si est pair, soit un carré parfait si est impair, l'équation ait une solution non nulle en nombres entiers.
Voici des exemples importants de 2-plans symétriques.
Plans projectifs Les plans projectifs finis sont des 2-plans symétriques de paramètre et d'ordre . Pour ces plans, la relation des plans symétriques devient :
Comme , l'ordre d'un plan projectif est et, à partir de la relation ci-dessus, on obtient qu'il y a points dans un plan projectif d'ordre .
Comme un plan projectif est un 2-plan symétrique, on a . Le nombre est le nombre de droites du plan projectif. Il ne peut pas y avoir de droites répétées puisque , donc un plan projectif est un simple 2-plan dans lequel le nombre de droites et le nombre de points sont égaux. Pour un plan projectif, est le nombre de points de chaque droite. De même, est le nombre de droites contenant un point donné.
Pour on obtient un plan projectif d'ordre 2, appelé aussi plan de Fano, avec points et 7 droites. Dans le plan de Fano, chaque droite contient points et chaque point appartient à droites.
On sait que des plans projectifs existent pour tous les ordres qui sont des nombres premiers ou des puissances de nombres premiers. Ils forment la seule famille infinie connue de plans en blocs symétriques ayant une valeur donnée..
Par exemple, le jeu dobble vu ci-dessus est construit sur le plan projectif d'ordre 7.
Biplans
Un biplan ou une géométrie biplane est un 2-plan symétrique avec ; ainsi chaque paire de points est incluse dans deux blocs ("droites"), et deux droites se coupent en deux points.. Ces biplans sont similaires aux plans projectifs finis, sauf que deux points déterminent deux droites et deux droites déterminent deux points. Dans un biplan d'ordre les blocs possèdent points ; il y a donc points. vignette|Biplan d'ordre 1 ; 4 points , 4 "droites" , par deux points passent deux "droites", deux "droites" se coupent en deux points. Les 18 exemples connus. de biplans sont énumérés ci-dessous :
Le biplan d'ordre 0 (biplan trivial) : c'est le 2-plan de paramètres ; il est composé de deux points, de deux droites, chacune contenant deux points. Géométriquement, c'est le digone. Le biplan d'ordre 1 : c'est le 2-plan de paramètres ; il est composé de quatre points et quatre droites chacune contenant trois points. Géométriquement, les points sont les sommets et les blocs sont les faces d'un tétraèdre. Le biplan d'ordre 2 est le complémentaire du plan de Fano : il a 7 points et 7 droites de taille 4 ; c'est un 2-plan de paramètres (7, 4, 2), où les droites sont les complémentaires des droites à 3 points du plan de Fano.. Sa matrice d'incidence est :
0001111110001101110010110110110110010110101010101 La somme de chaque colonne ou ligne est égale à , et le fait que se traduit par le fait que la somme de deux colonnes ou de deux lignes contient exactement deux termes égaux à 2. Le biplan d'ordre 3 a 11 points et 11 droites de taille 5 ; c'est le 2-plan de paramètres (11, 5, 2) ; il est également connu comme biplan de Paley du nom de Raymond Paley ; il est associé au graphe de Paley d'ordre 11, qui est construit en utilisant le corps à 11 éléments, et c'est le 2-plan de Hadamard associé à une matrice de Hadamard de taille 12 (voir paragraphe suivant).
Algébriquement cela correspond au plongement exceptionnel du groupe spécial linéaire projectif PSL(2, 5) dans le groupe PSL(2,11).
Il existe trois biplans d'ordre 4, ayant 16 points et 16 droites de taille 6, soit des 2-plans de type (16, 6, 2). L'un est connu comme la configuration de Kummer. Ces trois plans sont également des designs de Menon.