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 Portail des mathématiques
Ce document provient de « Propri%C3%A9t%C3%A9 B ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”