Plan en blocs

É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

${\displaystyle bk=vr,}$

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

${\displaystyle \lambda (v-1)=r(k-1),}$

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, un 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é b ≥ v.

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.

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

${\displaystyle \lambda (v-1)=k(k-1).}$

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 :

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 b ≥ v + 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].

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 ₀, R ₁ ,. . ., R _n . Une paire d'éléments de la relation R_i est dite i-associée. De plus on a les conditions suivantes :

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$ ; c'est la relation d'identité .
• On définit demande que Si R est dans S, alors R* doit être est dans S, où ${\displaystyle R^{*}:=\{(x,y)|(y,x)\in R\}}$;
• Si ${\displaystyle (x,y)\in R_{k}}$, le nombre de ${\displaystyle z\in X}$ tel que ${\displaystyle (x,z)\in R_{i}}$ et ${\displaystyle (z,y)\in R_{j}}$ est une constante ${\displaystyle p_{ij}^{k}}$ qui est fonction de i, j, k mais pas du choix particulier de x et y .

Un schéma d'association est commutatif si ${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$ 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 ≤ i ≤ n, 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].

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].

• Géométrie d'incidence
• Système de Steiner
• Design combinatoire
• Journal of Combinatorial Designs

• Michael Aschbacher, « On collineation groups of symmetric block designs », Journal of Combinatorial Theory, Series A, vol. 11, n^o 3,‎ 1971, p. 272–281 (DOI 10.1016/0097-3165(71)90054-9)
• (en) E. F. Assmus et J. D. Key, Designs and Their Codes, Cambridge, Cambridge University Press, 1992, 352 p. (ISBN 0-521-41361-3).
• Thomas Beth, Dieter Jungnickel et Hanfried Lenz, Design Theory, Cambridge, Cambridge University Press, 1999, 2^e éd. (1^re éd. 1986), 1100 p. (ISBN 978-0-521-44432-3, lire en ligne).
• (de) Albrecht Beutelspacher, Einführung in die endliche Geometrie : I. Blockpläne, Mannheim/Wien/Zürich, B.I. Wissenschaftsverlag, 1982, 247 p. (ISBN 3-411-01632-9)
• Raj Chandra Bose, « A Note on Fisher's Inequality for Balanced Incomplete Block Designs », Annals of Mathematical Statistics,‎ 1949, p. 619-620.
• Raj Chandra Bose et T. Shimamoto, « Classification and analysis of partially balanced incomplete block designs with two associate classes », Journal of the American Statistical Association, vol. 47, n^o 258,‎ 1952, p. 151–184 (DOI 10.1080/01621459.1952.10501161).

• P. J. Cameron et J. H van Lint, Designs, Graphs, Codes and their Links, Cambridge University Press, 1991, 252 p. (ISBN 0-521-42385-6, présentation en ligne).
• Charles J. Colbourn et Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Chapman & Hall / CRC, 2007, 2^e éd., 1016 p. (ISBN 978-1-58488-506-1 et 1-58488-506-8, présentation en ligne).
• R. A. Fisher, « An examination of the different possible solutions of a problem in incomplete blocks », Annals of Eugenics, vol. 10,‎ 1940, p. 52-75 (DOI 10.1111/j.1469-1809.1940.tb02237.x)
• Roger Guérin, « Vue d'ensemble sur les plans en blocs incomplets équilibrés et partiellement équilibrés », Revue de l'Institut International de Statistique, vol. 33, n^o 1,‎ 1965, p. 24-58 (ISSN 0373-1138, DOI 10.2307/1401306, JSTOR 1401306, zbMATH 0137.37404)
• (en) Marshall Hall, Jr., Combinatorial Theory, New York/Chichester/Brisbane (Australia) etc., Wiley-Interscience, 1986, 2^e éd., 440 p. (ISBN 0-471-09138-3). 
• Daniel R. Hughes et Fred C. Piper, Design theory, Cambridge University Press, 1985 (ISBN 0-521-25754-9, présentation en ligne). 
• Petteri Kaski et Patric Östergård, « There Are Exactly Five Biplanes with k = 11 », Journal of Combinatorial Designs, vol. 16, n^o 2,‎ 2008, p. 117–127 (DOI 10.1002/jcd.20145, MR 2384014)
• E. S. Lander, Symmetric Designs : An Algebraic Approach, Cambridge University Press, 1983
• (en) C.C. Lindner et C.A. Rodger, Design Theory, Boca Raton, CRC Press, 1997, 198 p. (ISBN 0-8493-3986-3)
• Damaraju Raghavarao, Constructions and Combinatorial Problems in Design of Experiments, New York, Dover (réimpression avec corrections de l'édition de 1971 chez Wiley, 1988
• Damaraju Raghavarao et L.V. Padgett, Block Designs : Analysis, Combinatorics and Applications, World Scientific, 2005
• Kenneth H. Rosen (éditeur), Handbook of Discrete and Combinatorial Mathematics, Boca Raton/London/New York, CRC Press, 2000, 1232 p. (ISBN 0-8493-0149-1).
• Herbert John Ryser, Combinatorial Mathematics (Carus Monograph n° 14), Mathematical Association of America, 1963, « Chapter 8: Combinatorial Designs »
• Chester J. Salwach et Joseph A. Mezzaroba, « The four biplanes with k = 9 », Journal of Combinatorial Theory, Series A, vol. 24, n^o 2,‎ 1978, p. 141–145 (DOI 10.1016/0097-3165(78)90002-X)
• Vasanti N. Bhat et Sharadchandra Shankar Shrikhande, « Non-isomorphic solutions of some balanced incomplete block designs I », Journal of Combinatorial Theory, vol. 9,‎ 1970, p. 174-191 (lire en ligne)
• Douglas R. Stinson, Combinatorial Designs : Constructions and Analysis, New York, Springer, 2003, 300 p. (ISBN 0-387-95487-2, lire en ligne)
• Anne Penfold Street et Deborah J. Street, Combinatorics of Experimental Design, Clarendon, Oxford University Press, 1987, xiv + 400 (ISBN 0-19-853256-3)
• (en) Tosiro Tsuzuku (trad. du japonais), Finite Groups and Finite Geometries, Cambridge, Cambridge University Press, coll. « Cambridge Tracts in Mathematics » (n^o 78), 1982, 328 p. (ISBN 0-521-22242-7)
• Jacobus Hendricus Van Lint et Richard Michael Wilson, A Course in Combinatorics, Cambridge University Press, 1992, 188 p. (ISBN 0-521-42260-4).