Propriete B
- Propriete B
-
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, S7); 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
Portail des mathématiques
Catégorie : Théorie des jeux
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Propriete B de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
PROPRIÉTÉ — Si l’on veut bien entendre la leçon de multiples exemples, le sentiment d’appropriation serait général – il est attesté depuis l’époque paléolithique par les gravures effectuées sur les armes d’os – et toujours vivace. Pourtant, les données de la … Encyclopédie Universelle
Propriete — Propriété En philosophie, la propriété d une classe ou d un individu se réfère à un attribut qu il est possible de prédiquer de celle ci ou celui ci. Le terme propriété, du latin juridique proprietas « propriété, caractère propre,… … Wikipédia en Français
proprieté — Proprieté. s. f. Le droit, le titre par lequel une chose appartient en propre à quelqu un. Il joüit du revenu de cette maison, mais un autre en a la proprieté. l usufruit se réünit à la proprieté par le decez de l usufruitier. contester la… … Dictionnaire de l'Académie française
proprieté — et appartenance d un chacun, Proprietas. Proprieté de quelque chose acquise par prescription, Vsus et authoritas. Quand on a la proprieté à l usufruict, Plena proprietas. Expliquer la proprieté de quelque chose, Describere. Toutes choses qui… … Thresor de la langue françoyse
propriété — PROPRIÉTÉ: Une des bases de la société. Plus sacrée que la religion … Dictionnaire des idées reçues
Propriété — Pour les articles homonymes, voir Propriété (homonymie). En philosophie scolastique médiévale, la propriété d une classe ou d un individu se réfère à un attribut qu il est possible de prédiquer de celle ci ou celui ci. Le terme propriété, du… … Wikipédia en Français
propriété — (pro pri é té) s. f. 1° Ce qui est le propre d une chose. L égalité des rayons est une propriété du cercle. • On voit d une première vue, que l arithmétique fournit des propriétés sans nombre, et chaque science de même, PASC. Disproport. de l … Dictionnaire de la Langue Française d'Émile Littré
PROPRIÉTÉ — s. f. Le droit par lequel une chose appartient en propre à quelqu un. Il jouit du revenu de cette maison, mais un autre en a la propriété. L usufruit se réunit à la propriété par le décès de l usufruitier. J ai la possession, la jouissance de… … Dictionnaire de l'Academie Francaise, 7eme edition (1835)
PROPRIÉTÉ — n. f. Droit par lequel une chose appartient en propre à quelqu’un. Il jouit du revenu de cette maison, mais un autre en a la propriété. L’usufruit se réunit à la propriété par le décès de l’usufruitier. J’ai la possession, la jouissance de cette… … Dictionnaire de l'Academie Francaise, 8eme edition (1935)
Propriété — BABEUF (François Noël, dit Graccus) Bio express : Révolutionnaire français (1760 1797) «La propriété est odieuse dans son principe et meurtrière dans ses effets.» Source : La Tribune du peuple Mot(s) clé(s) : Propriété… … Dictionnaire des citations politiques
