La théorie du design combinatoire est une partie des mathématiques combinatoires ; elle traite de l'existence, de la construction et des propriétés de systèmes d'ensembles finis dont les arrangements satisfont certains concepts d'équilibre et/ou de symétrie. Ces concepts sont assez imprécis pour qu'une large gamme d'objets puisse être considérée comme relevant de ces notions. Parfois, cela peut concerner la taille des intersections comme dans les plans en blocs, d'autres fois on est intéressé par la disposition des entrées dans un tableau comme dans les grilles de sudoku.
La théorie du design combinatoire peut être appliquée au domaine des plans d'expériences. Une partie de la théorie du design combinatoire trouve son origine dans les travaux du statisticien Ronald Fisher sur la planification des expériences biologiques. Les applications modernes concernent un large éventail de domaines, notamment; la géométrie finie, programmation de tournois, les loteries, la chimie mathématique, la biomathématique, la conception et analyse d'algorithmes, les réseaux informatiques, vérification de propriétés de groupes et cryptographie.
Exemple introductif vignette| Le plan de Fano. Étant donné un certain nombre n de personnes, on se demande s'il est possible de les affecter à des ensembles de telle manière que chaque personne figure dans au moins un ensemble, chaque paire de personnes figure dans exactement un ensemble, deux ensembles quelconques ont exactement une personne en commun, et de plus aucun ensemble ne contient toutes les personnes, ni toutes les personnes sauf une, ni exactement une personne?
La réponse à la question dépend du nombre n de personnes impliquées. Pour que le problème ait une solution, n doit être de la forme n = q 2 + q + 1, mais il n'est pas certain que cette condition soit suffisante : il n'est pas simple de prouver qu'une solution existe si q est la puissance d'un nombre premier. On conjecture que ce sont les seules solutions. Il a en outre été démontré que s'il existe une solution pour q congruent à 1 ou 2 mod 4, alors q est une somme de deux carrés parfaits. Ce dernier résultat, la version faible du théorème de Bruck-Ryser-Chowla, est prouvé par une combinaison de méthodes constructives basées sur des corps finis et une application de propriétés de formes quadratiques.
Lorsqu'une telle structure existe, elle est appelée un plan projectif fini; cet exemple illustre aussi la façon dont géométrie finie et la combinatoire interagissent. Quand q = 2, le plan projectif est appelé le plan de Fano.
Histoire Le design combinatoire remonte à l'Antiquité, avec le carré de Luo Shu qui est un des premiers carrés magiques. L'une des premières applications des designs combinatoires que l'on peut dater se trouve en Inde dans le livre Brhat Samhita (la "Grande collection") écrit par le mathématicien Varahamihira vers 587 après J.-C., dans le but de créer des parfums en utilisant 4 substances sélectionnées parmi 16 substances différentes à l'aide d'un carré magique.
Le design combinatoire s'est développé parallèlement à la croissance générale de la combinatoire au , par exemple avec les carrés latins au et les systèmes de Steiner au . Le design combinatoire a également été populaire dans les mathématiques récréatives, comme le problème des écolières de Kirkman (1850), et dans des problèmes pratiques, comme la programmation des tournois toutes rondes (dont la solution est publiée dans les années 1880). Au , des designs ont été utilisés à les plans d'expériences, notamment les carrés latins, la géométrie finie et les schémas d'association, ouvrant le domaine des statistiques algébriques.
Une vue d'ensemble des plans en blocs partiellement équilibrés a été donné en 1965 par R. Guérin.. Un cours sur les plans d'expériences est celui de Philippe Besse à l'Insa de Toulouse..
Designs combinatoires fondamentaux
Le domaine principal des designs combinatoire comprend les plans en blocs incomplets équilibrés (abrégé en BIBD), les matrices Hadamard et les designs de Hadamard, les plans en blocs incomplets équilibrés symétriques, les carrés latins, les plans BIBD résolubles, les ensembles de différences et le design par paires équilibrés (abrégé en PBD). D'autres designs combinatoires sont liées ou ont été développées à partir de l'étude de ces designs fondamentales.
Un plan en blocs incomplet équilibré (abrégé en BIBD pour balanced incomplete block design), généralement appelé simplement plan en blocs, est une collection B de b sous-ensembles (appelés blocs) d'un ensemble fini X de v éléments tels que tout élément de X est contenu dans le même nombre r de blocs, chaque bloc ayant le même nombre k d'éléments, et chaque paire d'éléments distincts apparait ensemble dans le même nombre λ de blocs. Les BIBD sont également connus sous le nom 2-plans et sont souvent appelés plans de type 2-(v, k, λ). Par exemple, lorsque λ = 1 et b = v, on retrouve un plan projectif : X est alors l'ensemble de points du plan et les blocs sont les lignes. Un plan en blocs incomplet symétrique équilibré (abrégé en SBIBD pour symmetric balanced incomplete block design) est un plan en blocs dans lequel v = b (le nombre de points est égal au nombre de blocs). Ils constituent la sous-classe des BIBD la plus importante et la mieux étudiée. Les plans projectifs, les biplans et les 2-designs de Hadamard sont tous des SBIBD. Ils présentent un intérêt particulier car ils sont les exemples extrémaux de l'inégalité de Fisher (qui stipule que b ≥ v). Un plan en blocs incomplet équilibré résoluble est un plan en blocs incomplet équilibré dont les blocs peuvent être partitionnés en ensembles, appelés classes parallèles, dont chacun constitue une partition de l'ensemble de points du BIBD. L'ensemble des classes parallèles est appelé une résolution du plan. Une solution au célèbre problème des 15 écolières de Kirkman est la résolution d'un plan en blocs incomplet équilibré avec les paramètres v = 15, k = 3 et λ = 1. Un rectangle latin est une matrice de dimension r × n, avec r ≤ n , qui a comme entrées les nombres 1, 2, 3,..., n (ou tout autre ensemble de n symboles distincts) et telle que les nombres figurant dans chaque ligne et dans chaque sont tous distincts. Un carré latin est un rectangle latin avec r = n. Si r < n, alors il est possible d'ajouter n - r lignes à un rectangle latin pour former un carré latin, en utilisant le théorème des mariages de Hall.
Deux carrés latins d'ordre n sont dits orthogonaux si l'ensemble des couples composés des entrées aux mêmes places dans les deux carrés a n 2 membres distincts (tous les couples possibles se produisent). Un ensemble de carrés latins de même taille forme un ensemble de carrés latins mutuellement orthogonaux (abrégé en MOLS) si chaque paire de carrés latins de l'ensemble est orthogonale. Il peut y avoir au plus n - 1 carrés dans un ensemble de MOLS d'ordre n. Un ensemble de n - 1 MOLS d'ordre n peut être utilisé pour construire un plan projectif d'ordre n (et réciproquement).
Un ensemble de différences de type (v, k, λ) est un sous-ensemble D de k éléments d'un groupe G d'ordre v, tel que chaque élément de G autre que l'identité peut s'écrire d'exactement λ façons comme produit d'éléments de D (l'opération dans G est notée multiplicativement)Qund le groupe G iest noté additivement, la propriété s'exprime sous la forme d1–d2 ,doù le nom d'ensemble de différences. .
Si D est un ensemble de différences et g est dans G, alors g D = { gd : d dans D } est également un ensemble de différences, appelé une translation de D. L'ensemble de toutes les translations d'un ensemble de différences D forme un plan en blocs symétrique. Dans un tel plan en blocs, il y a v éléments et v blocs. Chaque bloc se compose de k points, chaque point est contenu dans k blocs. Deux blocs quelconques ont exactement λ éléments en commun et deux points quelconques apparaissent ensemble dans λ blocs. Ce plan en blocs incomplet symétrique équilibré est appelé le développement de D.
Dans le cas particulier où λ = 1, l'ensemble de différences est un plan projectif. Un exemple d'ensemble de différences de paramètres (7,3,1) définie dans le groupe abélien (noté additivement) est formé par le sous-ensemble {1,2,4}. Le développement de cet ensemble de différences donne le plan Fano. Étant donné que tout ensemble de différences produit un SBIBD, l'ensemble de paramètres doit satisfaire le théorème de Bruck-Ryser-Chowla, mais tous les SBIBD ne produisent pas un ensemble de différences.
Une matrice de Hadamard d'ordre m est une matrice carrée H dont les entrées sont ± 1 telles 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 une forme standard dans laquelle les entrées de la première ligne et de la première colonne sont toutes égales à +1. Si l'ordre m > 2, alors m doit être un multiple de 4.
Si, dans une matrice de Hadamard d'ordre 4a en forme standard, on supprime la première ligne et la première colonne et on convertit chaque -1 à 0, la matrice 0–1 obtenue est la matrice d'incidence d'un design symétrique de paramètres 2- (4a - 1, 2a - 1, a -1) appelé 2-design de Hadamard. Cette construction est réversible, et la matrice d'incidence d'un 2-design symétrique avec ces paramètres peut être utilisée pour construire une matrice de Hadamard d'ordre 4a. Quand a = 2, on obtient encore le plan de Fano, sous la forme d'un 2-design de Hadamard.
Un design équilibré par paire (abrégé en PBD pour pairwise balanced design) est un ensemble X avec une famille de sous-ensembles de X (pas nécessairement de même taille ni nécessairement distincts) tels que toute paire d'éléments distincts de X est contenue exactement dans λ > 0 sous-ensembles. L'ensemble X peut être l'un de ces sous-ensembles, et si tous les sous-ensembles sont des copies de X, le PBD est dit trivial. La taille de X est v et le nombre de sous-ensembles dans la famille (compté avec multiplicité) est b.
L'inégalité de Fisher s'applique aux PBD: pour tout PBD non trivial, on a v ≤ b.
Ce résultat généralise également le célèbre théorème de De Bruijn-Erdős : pour un PBD avec λ = 1 n'ayant pas de blocs de taille 1 ou v, on a v ≤ b, avec égalité si et seulement si le PBD est un plan projectif ou un quasi-pinceau.
Autres designs combinatoires Le Handbook of Combinatorial Designs contient 65 chapitres consacrés chacun à un design combinatoire autre que ceux déjà donnés ci-dessus. Voici un extrait de cette liste :
Un design ternaire équilibré (abrégé en BTD pour balanced ternary design) de paramètres (V, B ; ρ1, ρ2, R ; K, Λ) est un arrangement de V éléments en B multiensembles (blocs), chacun de cardinalité K (K ≤ V), satisfaisant:
Chaque élément apparaît R = ρ1 + 2 ρ2 fois au total, avec multiplicité 1 dans exactement ρ1 blocs et multiplicité 2 dans exactement ρ2 blocs. Chaque paire d'éléments distincts apparaît Λ fois (compté avec la multiplicité); autrement dit, si mvb est la multiplicité de l'élément v dans le bloc b, alors pour chaque paire d'éléments distincts v et w, on a .
Par exemple, l'un des deux seuls BTD de paramètres (4,8; 2,3,8; 4,6) non isomorphes est, avec les blocs représentés en colonnes :
{| class="wikitable" |1 |1 |1 |2 |2 |3 |1 |1 |- |1 |1 |1 |2 |2 |3 |2 |2 |- |2 |3 |4 |3 |4 |4 |3 |3 |- |2 |3 |4 |3 |4 |4 |4 |4
La matrice d'incidence d'un BTD (où les entrées sont les multiplicités des éléments dans les blocs) peut être utilisée pour former un code correcteur d'erreurs ternaire de façon analogue à la formation de codes binaires à partir des matrices d'incidence des BIBD.
Un design de tournoi équilibré d'ordre n (abrégé en BTD (n) pour balanced tournament design) est un tableau rectangulaire de n lignes et 2n -1 colonnes contenant des paires non ordonnées distinctes d'un ensemble V à 2n éléments, tel que
chaque élément de V apparaît exactement une fois dans chaque colonne, et