Propriété B

Cet article est une ébauche concernant les mathématiques.

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^[1].

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) \leq 3$ . D'autre part, $C^{'} = {{1, 2}, {1, 3}}$ la possède (jeu $Y = {1}$ et $Z = {2, 3}$ ), donc $m (2) \geq 3$ . On a $3 \leq m (2) \leq 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_{7}$ ); $C$ n'a pas la propriété B (donc $m (3) \leq 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) \geq 7$ ). On a $7 \leq m (3) \leq 7$ , donc $m (3) = 7$ .

Notes et références

↑ (Seymour, Toft, Manning)

Voir aussi

Bibliographie

(en) Paul D. Seymour, « A note on a combinatorial problem of Erdős and Hajnal », Journal of the London Mathematical Society, vol. s2:8, n^o 4,‎ octobre 1974, p. 681-682 (DOI 10.1112/jlms/s2-8.4.681).
(en) Bjarne Toft, « On colour-critical hypergraphs », Infinite and Finite Sets, A. Hajnal et al, North Holland Publishing Co.,‎ 1975, p. 1445-1457.
(en) Gregory M. Manning, « Some results on the m(4) problem of Erdös and Hajnal », Electronic Research Announcements, vol. 1,‎ 1995, p. 112-113.

Portail des mathématiques

[1] (Seymour, Toft, Manning)

[1]