Propriété B

En mathématiques, dans la théorie des jeux, un ensemble peut posséder la propriété B.

Concrètement, en prenant un jeu fini X, une collection C de sous-jeux de X de taille n; X possède la propriété B ssi on peut séparer X en deux sous-jeux distincts Y et Z, tels que chaque jeu de C corresponde à la fois à Y et à Z. Le plus petit nombre de jeux de taille n qui n'ont pas la propriété B est noté m(n).

Valeur de m(n)

On sait que m(1) = 1, m(2) = 3, et m(3) = 7; la valeur de m(4) est inconnue, mais probablement comprise entre 21 et 23 (Seymour, Toft, Manning).

• m(1) : pour n = 1, le jeu X = {1}, et C = {{1}}. Alors C n'a pas la propriété B : m(1) = 1.

• m(2) : pour n = 2, le jeu X = {1, 2, 3} et C = {{1, 2}, {1, 3}, {2, 3}}. Alors C n'a pas la propriété B, donc m(2) ≤ 3. D'autre part, C' = {{1, 2}, {1, 3}} la possède (jeu Y = {1} et Z = {2, 3}), donc m(2) ≥ 3. On a 3 ≤ m(2) ≤ 3, donc m(2) = 3.

• m(3) : pour n = 3, le jeu X = {1, 2, 3, 4, 5, 6, 7}, et C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} (système de Steiner, S₇); C n'a pas la propriété B (donc m(3) ≤ 7), mais si un seul des éléments de C est omis, alors il pourrait être considéré comme Y et le jeu restant C' aurait la propriété B (donc m(3) ≥ 7). On a 7 ≤ m(3) ≤7, donc m(3) = 7.

Références

• Seymour, Une note sur les problèmes combinatoires d'Erdös et de Hajnal, Bull. London Math. Soc. 2:8 (174), 681-682
• Toft, On colour-critical hypergraphs, in Infinite and Finite Sets, ed. A. Hajnal et al, North Holland Publishing Co., 1975, 1445-1457
• G. M. Manning, Some results on the m(4) problem of Erdös and Hajnal, Electron. Research Announcements of the American Mathematical Society, 1(1995) 112-113