Plan en blocs

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques combinatoires, un plan en blocs est un ensemble, muni d'une famille de sous-ensembles (avec des répétitions possibles) dont les membres satisfont un ensemble de propriétés considérées dans une application particulière. Les applications proviennent de nombreux domaines, notamment les plans d'expériences, la géométrie finie, la chimie physique, les tests de logiciels, la cryptographie et la géométrie algébrique. De nombreuses variantes ont été examinées, mais les plus étudiées 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 la plans d'expériences[1],[2].

Un plan en blocs dans laquelle tous les blocs ont la même taille est appelé uniforme. Les plans décrits dans cette pages sont tous uniformes. Les plans équilibrées par paires sont des exemples de plans en blocs qui ne sont pas nécessairement uniformes.

Définition d'un plan en blocs incomplet équilibré (ou 2-plan)[modifier | modifier le code]

Étant donné un ensemble fini X (dont les éléments sont appelés points ) et des entiers k, r, λ ≥ 1, on définit un plan en blocs incomplet équilibré ou 2-plan (ou BIBD) B comme une famille de sous-ensembles à k éléments de X, appelés les blocs, et qui vérifient que élément x de X appartient à r blocs, et que toute paire de points distincts x et y de X est contenue 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 répétés. Les plans sans blocs répétés sont appelés simples .

L'entier v (le nombre de points, c'est-à-dire le nombre d'éléments de X) , l'entier b (le nombre de blocs), et les entiers k, r et λ sont les paramètres du plan. Pour éviter des exemples dégénérés, on suppose également que v > k, 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 suivant résume les paramètres :

v points, nombre d'éléments de X
b nombre de blocs
r nombre de blocs contenant un point
k nombre de points dans un bloc
λ nombre de blocs contenant 2 (ou plus généralement t) points distincts

Le plan est appelée un plan de paramètres ( v, k, λ ) , ou 2-( v, k, λ ) plan, ou aussi de paramètres ( v, b, r, k, λ ). Les paramètres ne sont pas tous indépendants : v, k et λ déterminent b et r, et toutes les combinaisons de v, k et λ ne sont pas possibles. Les deux équations de base reliant ces paramètres sont

que l'on obtient en comptant le nombre de paires ( B, p ) où B est un bloc et p est un point dans ce bloc, et

que l'on obtient en comptant le nombre de triplets ( p, q, B ) où p et q sont des points distincts et B est un bloc qui les contient tous les deux, et en divisant ce nombre par v .

Ces conditions ne sont pas suffisantes ; par exemple, une plan de paramètres (43,7,1) n'existe pas[3].

L' ordre d'un 2-plan est par définition le nombre n = rλ . Le complément d'un 2-plan est obtenu en remplaçant chaque bloc par son complémentaire dans l'ensemble de points X. C'est aussi un 2-plan avec les paramètres v ′ = v, b ′ = b, r ′ = b - r, k ′ = v - k, λ ′ = λ + b - 2 r . Un 2-plan et son complément 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é bv.

Exemples[modifier | modifier le code]

L'unique plan de paramètres (6,3,2) possède 10 blocs ( b = 10) et chaque élément est répété 5 fois ( r = 5)[4]. En utilisant les symboles de 0 à 5 pour représenter les points, les blocs sont les triplets suivants:

012    013    024    035    045    125    134    145    234    235.

Il y a quatre plan non isomorphes de paramètres (8,4,3) possède 14 blocs avec chaque élément répété 7 fois. En utilisant les symboles de 0 à 5 pour représenter les points, les blocs sont les 4-tuples suivants[4] :

0123    0124    0156    0257    0345    0367    0467    1267    1346    1357    1457    2347    2356    2456.

L'unique plan de paramètres (7,3,1) a 7 blocs avec chaque élément répété 3 fois. Sur les symboles 0 à 6, les blocs sont les triplets suivants[4] :

013    026    045    124    156    235    346.
Si les points sont vus comme des points sur un plan de Fano, alors les blocs en sont les droites.

Plans en blocs symétriques[modifier | modifier le code]

Un 2-plan qui a le même nombre de points et de blocs est appelé un plan symétrique. C'est le cas de l'égalité dans l'inégalité de Fisher[5]. Les plans symétriques ont le plus petit nombre de blocs parmi 2-plans d'un nombre de points donné.

Dans un plan symétrique, il y a les égalités r = k et b = v, et dans les 2-plans symétrique, deux blocs distincts ont points λ en commun[6]. Un théorème de Ryser dit que l'inverse est également vraie.: Si X est un ensemble de v éléments et B est un ensemble de v sous-ensembles de k éléments (les "blocs") tels que deux blocs distincts ont exactement λ points en commun, alors (X, B ) est un plan en blocs symétrique[7].

Les paramètres d'un plan symétrique vérifient l'équation

Ceci impose de fortes restrictions sur v, de sorte que le nombre de points est loin d'être arbitraire. Le théorème de Bruck-Ryser-Chowla donne des conditions nécessaires, mais pas suffisantes, pour l'existence d'un plan symétrique en fonction de ces paramètres.

Voici des exemples importants de 2-plans symétriques :

Plans projectifs[modifier | modifier le code]

Les plans projectifs finis sont des 2-plans symétriques de paramètre λ = 1 et d'ordre n > 1. Pour ces plans, l'équation des plans symétriques devient:

Comme k = r , on peut définir l' ordre d'un plan projectif comme n = k − 1 et, à partir de l'équation ci-dessus, on obtient que v = (n + 1)n + 1 = n 2 + n + 1 points dans un plan projectif d'ordre n .

Comme un plan projectif est un plan symétrique, on a b = v, ce qui signifie qu'on a également b = n 2 + n + 1. Le nombre b est le nombre de droites du plan projectif. Il ne peut pas y avoir de lignes répétées puisque λ = 1, donc un plan projectif est un simple plan à 2 dans lequel le nombre de lignes et le nombre de points sont toujours les mêmes. Pour un plan projectif, k est le nombre de points sur chaque ligne et il est égal à n   + 1. De même, r = n   +   1 est le nombre de lignes avec lesquelles un point donné est incident.

Pour n = 2 on obtient un plan projectif d'ordre 2, aussi appelé plan de Fano, avec v = 4 + 2 + 1 = 7 points et 7 droites. Dans le plan de Fano, chaque droite contient n +1 = 3 points et chaque point appartient à n + 1 = 3 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 de blocs symétriques ayant une valeur λ constante[8].

Biplans[modifier | modifier le code]

Un biplan ou une géométrie biplane est un 2-plan symétrique avec λ = 2 ; ainsi chaque ensemble de deux points est contenu dans deux blocs ("droites"), et deux droites se coupent en deux points[8]. 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 n les blocs possèdent k = n + 2 points; il a en tout v = 1 + (n + 2) (n + 1) / 2 points (puisque r = k ).

Les 18 exemples connus[9] de biplans sont énumérés ci-dessous.

  • Biplan trivial : le biplan d'ordre 0 a 2 points (et des droites de taille 2) ; c'est un 2-plan de paramètres (2,2,2)); il est composé de deux points, de deux blocs, chacun contenant des deux points. Géométriquement, c'est le digone.
  • Le biplan d'ordre 1 a 4 points et des droites de taille 3 ; c'est un 2-(4,3,2) plan; c'est le plan complet avec v = 4 et k = 3. 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ément du plan de Fano : il a 7 points et des droites de taille 4; c'est un 2-plan de paramètres (7,4,2), où les lignes sont les compléments des droites à 3 points du plan de Fano[10].
  • Le biplan d'ordre 3 a 11 points (et des droites de taille 5; c'est un plan de paramètres 2-(11,5,2)), il est également connu comme le biplan de Paley après 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-design de Hadamard associé à la matrice Hadamard de taille 12.
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 (et de 16 points, de droites de taille 6; des plans de type 2- (16,6,2)). L'un est connu comme la configuration de Kummer . Ces trois plans sont également des design de Menon .
  • Il y a quatre biplans d'ordre 7 (et 37 points, droites de taille 9; des 2-plans de type (37,9,2))[11].
  • Il y a cinq biplans d'ordre 9 (et 56 points, droites de taille 11; 2-plans de type (56,11,2))[12].
  • Deux biplans sont connus d'ordre 11 (et 79 points, droites de taille 13; de type 2-(79,13,2))[13].

Des biplan d'ordre 5, 6, 8 et 10 n'existent pas, comme le montre le théorème de Bruck-Ryser-Chowla .

Design de Hadamard[modifier | modifier le code]

Une matrice de Hadamard H d'ordre m est une matrice carrée d'ordre dont les entrées sont égales à 1 ou -1 et telle que HH = m I m, où H est la transposée de H et Im est la matrice d'identité d'ordre m. Une matrice Hadamard peut être mise sous forme standard, c'est-à-dire convertie en une matrice Hadamard équivalente, où les entrées de la première ligne et de la première colonne sont toutes égales à+1. Si l'ordre m   est plus grand que   2, alors m doit être un multiple de 4, donc de la forme 4a pour un entier positif a.

Une matrice de Hadamard de dimension 4a normalisée peut être transformée en supprimant la première ligne et la première colonne et remplaçant chaque -1 par 0. La matrice M à coefficients 0 et 1 est la matrice d'incidence d'un 2-design symétrique de paramètres 2- (4a − 1, 2a − 1, a −  1) appelé 2-design de Hadamard[14]. Il contient blocs / points; chacun contient et est contenu dans points / blocs. Chaque paire de points est contenue dans exactement blocs.

Cette construction est réversible, et la matrice d'incidence d'un 2-plan symétrique, avec ces paramètres peut être utilisée pour former une matrice de Hadamard de taille 4a.

2-plans résolubles[modifier | modifier le code]

Un 2-plan résoluble est un 2-plan dont les blocs peuvent être partitionnés en sous-ensembles (appelés classes parallèles ), chacun constituant une partition de l'ensemble de points du 2-plan. L'ensemble des classes parallèles est appelé une résolution du plan.

Si un plan résoluble de type 2- ( v, k, λ) a c classes parallèles, alors bv + c − 1[15].

Par conséquent, un plan symétrique ne peut pas avoir une résolution qui a plus d'une classe parallèle[16].

Les archétypes de 2-plans résolubles sont les plans affines finis. Une solution au fameux problème des15 écolières est une résolution de type 2- (15,3,1)[17].

Plans partiellement équilibrés[modifier | modifier le code]

Un schéma d'association à n classes se compose d'un ensemble X de taille v et d'une partition S de X × X en n + 1 relations binaires, R 0, R 1 ,. . ., R n . Une paire d'éléments de la relation Ri est dite i-associée. De plus on a les conditions suivantes :

  •  ; c'est la relation d'identité .
  • On définit demande que Si R est dans S, alors R* doit être est dans S,;
  • Si , le nombre de tel que et est une constante qui est fonction de i, j, k mais pas du choix particulier de x et y .

Un schéma d'association est commutatif si pour tout i, j et k . La plupart des auteurs assument cette propriété.

Un plan en blocs incomplet partiellement équilibré avec n classes associées est un plan en blocs basé sur un ensemble X à v éléments avec b blocs de même taille k , chaque élément apparaissant dans r blocs, et tel qu'il existe un schéma d'association avec n classes définies sur X où, si les éléments x et y sont i-associés, 1 ≤ in, alors ils sont simultanément dans exactement λ i blocs .

Un tel plan détermine un schéma d'association, mais l'inverse est faux[18].

Exemple[modifier | modifier le code]

Soit A(3) le schéma d'association suivant avec trois classes associées sur l'ensemble X = {1,2,3,4,5,6}. Dans la table ci-dessous, l'entrée ( i, j ) est égale à s si les éléments i et j sont en relation dans Rs .

1 2 3 4 5 6
1  0   1   1   2   3   3 
2  1   0   1   3   2   3 
3  1   1   0   3   3   2 
4  2   3   3   0   1   1 
5  3   2   3   1   0   1 
6  3   3   2   1   1   0 

Les blocs d'un plan en blocs incomplet partiellement équilibré basé sur A(3) sont:

 124    134     235   456 
  125   136    236    456 

Les paramètres de ce plan en blocs incomplet partiellement équilibré de 3 classes sont : v = 6, b = 8, k= 3, r= 4 et λ1 = λ2 = 2 et λ3= 1. De plus, pour le schéma d'association, on a n0 = n2 = 1 et n1 = n3 = 2[19].

Propriétés[modifier | modifier le code]

Les paramètres d'un plan en blocs incomplet partiellement équilibré de m classes (PBIBD ( m )) satisfont les relations suivantes[20] :

Un plan en blocs incomplet partiellement équilibré d'une seule classe (un PBIBD(1)) est un BIBD et un plan en blocs incomplet partiellement équilibré de 2 classes (un PBIBD(2)) dans lesquelles λ 1 = λ 2 est un BIBD[21].

Deux PBIBD de classe associée[modifier | modifier le code]

Les plans en blocs incomplet partiellement équilibrés à 2 classes (PBIBD(2)) ont été les plus étudiés car ils sont les plus simples et les plus utiles des PBIBD[22]. La classification de Bose et Shimamoto[23] de 1952 les répartit en six types :

  1. groupe divisible;
  2. triangulaire;
  3. type carré latin;
  4. cyclique;
  5. type de géométrie partielle;
  6. divers.

Applications[modifier | modifier le code]

Le sujet mathématique des plans en blocs est né dans le cadre statistique des plans d'expériences. Ces plans ont été particulièrement utiles dans les applications de la technique d'analyse de variance. Cela reste un domaine important pour l'utilisation des plans en blocs.

Alors que les origines du sujet reposent sur des applications biologiques (tout comme certaines terminologies existantes), les plans sont utilisés dans de nombreuses applications où des comparaisons systématiques sont effectuées, comme dans les tests de logiciels .

La matrice d'incidence des plans en blocs fournit une source naturelle de codes en blocs intéressants qui sont utilisés comme codes correcteurs. Les lignes de leurs matrices d'incidence sont également utilisées comme symboles sous une forme de modulation en position d'impulsion[24].

Application statistique[modifier | modifier le code]

Supposons que des chercheurs sur le cancer de la peau souhaitent tester trois écrans solaires différents. Ils appliquent deux écrans solaires différents sur les mains d'une personne test. Après un rayonnement ultra-violet, ils enregistrent l'irritation de la peau en termes de coups de soleil. Le nombre de traitements est de 3 (les écrans solaires) et la taille des blocs est de 2 (mains par personne).

A plan en bloc correspondant peut être généré par des outils logiciels, et est indiquée dans le tableau suivant:

Plots Bloc Traitement
101 1 3
102 1 2
201 2 1
202 2 3
301 3 2
302 3 1

Le chercheur choisit les paramètres v = 3, k = 2 et λ = 1 pour le plan en blocs qui sont ensuite insérés le logiciel. Les paramètres restants b et r sont déterminés automatiquement.

En utilisant les relations de base, on voit qu'il faut b = 3 blocs, c'est-à-dire 3 personnes testées afin d'obtenir un plan en bloc incomplet équilibré. On note les blocs par A, B et C, et on obtient le plan en blocs

A = {2, 3}, B = {1, 3} et C = {1, 2}.

Une matrice d'incidence correspondante est spécifiée dans le tableau suivant:

Traitement Bloc A Bloc B Bloc C
1 0 1 1
2 1 0 1
3 1 1 0

Chaque traitement apparaît dans 2 blocs, donc r = 2 .

Un seul bloc (le bloc C ) contient les traitements 1 et 2 simultanément et il en va de même pour les paires de traitements (1,3) et (2,3). Par conséquent, λ = 1 .

Il est impossible d'utiliser un plan en blocs complet (où tous les traitements figurent dans chaque bloc) dans cet exemple car il y a 3 écrans solaires à tester, mais seulement 2 mains sur chaque personne.

Articles liés[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Colbourn et Dinitz 2007, p. 17−19
  2. Stinson 2003, p. 1
  3. Démontré par Tarry en 1900 qui montre qu'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.
  4. a b et c Colbourn et Dinitz 2007, p. 27
  5. Ils 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.
  6. Stinson 2003, p. 23, Theorem 2.2
  7. Ryser 1963, p. 102–104.
  8. a et b Hughes et Piper 1985, p. 109.
  9. Marshall_Hall,_Jr. 1986, p. 320-335
  10. Assmus et Key 1992, p. 55
  11. Salwach et Mezzaroba 1978
  12. Kaski et Östergård 2008
  13. Aschbacher 1971, p. 279–281
  14. Stinson 2003, p. 74, Theorem 4.5
  15. Hughes et Piper 1985, p. 156, Theorem 5.4
  16. Hughes et Piper 1985, p. 158, Corollary 5.5
  17. Beth, Jungnickel et Lenz 1999, p. 40, Example 5.8
  18. Street et Street 1987, p. 237
  19. Street et Street 1987, p. 238
  20. Street et Street 1987, p. 240, Lemma 4
  21. Colbourn et Dinitz 2007, p. 562, Remark 42.3 (4)
  22. Street et Street 1987, p. 242
  23. Raghavarao 1988, p. 127
  24. Noshad et Brandt-Pearce, « Expurgated PPM Using Symmetric Balanced Incomplete Block Designs », IEEE Communications Letters, vol. 16, no 7,‎ , p. 968–971 (DOI 10.1109/LCOMM.2012.042512.120457, Bibcode 2012arXiv1203.5378N, arXiv 1203.5378)

Bibliographie[modifier | modifier le code]