Ugrás a tartalomhoz

Halmazrendszerek kombinatorikus tulajdonságainak listája

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

E lapon betűrendben találhatóak bizonyos kombinatorikus szempontból fontos halmazrendszer- és halmazcsalád-osztályok (esetleg hipergráf-osztályok) definíciói.[m 1]

…–

[szerkesztés]
  • …-metszőrendszer: olyan metszőrendszer, amelyre igaz, hogy bármely két taghalmaz metszetének elemszáma nagyobb mint … (… egy számosság.); például 4-metszőrendszer.
  • …-uniform halmazrendszer: olyan uniform halmazrendszer, amelynek minden tagja … elemszámú (… egész szám), például 65-uniform rendszer.
  • Δ-rendszer: A halmazrendszer tagjainak páronkénti metszete az összes párra azonos.
  • csillag: olyan hipergráf, amelynek van egy minden élre illeszkedő csúcsa.
  • halmazgyűrű: olyan halmazcsalád, amely zárt az unió- és metszetképzés műveletére (az elnevezés félrevezető, mert a struktúra az unió- és metszetművelettel általában valójában "csak" félgyűrűt alkot).[2]
  • halmaztest v. halmazalgebra: olyan nem üres halmazrendszer v. -család, amely zárt az unió és a komplementerképzés műveletére
  • halom (clutter): ld. Sperner-rendszer.
  • ideál: olyan nemüres halmazcsalád v. rendszer, amely (véges) unió-zárt, és tetszőleges taghalmaza összes részhalmazát is tartalmazza.[3] Ld. még valódi ideál.
  • λ-rendszer v. Fubini-rendszer: olyan halmazcsalád, amely nem üres, zárt a komplementumképzésre (avagy a különbségképzésre) és a páronként diszjunkt megszámlálható unióra.
  • leszálló rendszer: zárt a részhalmazképzésre, azaz tagjai részhalmazai is mind tagok. Ebből következően egy leszálló rendszer tartalmazza az üres halmazt.
  • linearitás: egy hipergráf lineáris, ha bármely két (különböző!) (hiper)éle - akárcsak az euklideszi egyenesek - legfeljebb 1 pontban metszi egymást.
  • matroid: Nem üres, a részhalmazképzésre zárt (avagy leszálló) hipergráf, melyre még az is teljesül, hogy tartóhalmazának bármely részhalmazában lévő legbővebb tagjai mind azonos elemszámúak (az elemszám csak a megválasztott részhalmaztól függ, bár részhalmazonként különbözhet).
  • metszőrendszerI.:[4] Olyan halmazcsalád, melyre igaz, hogy a tartóhalmaz bármely eleme előáll néhány (véges sok) különböző tag metszeteként.
  • metszőrendszerII.:[5] Olyan halmazrendszer, amely bármely két tagjának metszete nem üres.
  • páronként diszjunkt rendszer: Olyan halmazrendszer v. -család, amely bármely két tagjának metszete üres.
  • π-rendszer: olyan halmazrendszer v. -család, amely metszet-zárt (véges sok taghalmaz metszete is a családban van).
  • (i,j)-regularitás: Egy hipergráf (i,j)-reguláris, ha minden csúcsára i (hiper)él illeszkedik, és minden (hiper)éle j csúcsot tartalmaz.
  • Sperner-rendszer / halom / antilánc: Olyan halmazrendszer v. -család, amely egy tagja sem tartalmaz egy másik tagot sem részhalmazként.
  • szeparáló rendszer:
    1. Olyan Ω halmaz feletti halmazcsalád, amelyre igaz, hogy a tartóhalmaz bármely két eleméhez található egy taghalmaz, amely az egyik elemet tartalmazza, de a másikat nem.
    2. Olyan hipergráf, amelynek duálisa Sperner-rendszer; vagy, ami ezzel ekvivalens, amelynek bármely v (hiper)csúcsára igaz, hogy az őt tartalmazó (hiper)élek metszete {v}.
  • szigma-algebra (σ-algebra): nemüres, metszet-zárt és megszámlálhatóunió-zárt halmazcsalád.
  • szigma-gyűrű: metszet-zárt és megszámlálhatóunió-zárt halmazcsalád.
  • szűrő vagy filter: Olyan nemüres halmacsalád vagy -rendszer, amely nem tartalmazza az üres halmazt, (véges) metszet-zárt (π-rendszer) és zárt a részhalmazképzésre (egy tagja összes részhalmazait is tartalmazza, kivéve az üreset).
  • uniform halmazrendszer: Olyan halmazrendszer v. -család, amelynek minden taghalmaza azonos számosságú. Lásd még …–uniform halmazrendszer.
  • valódi ideál: egy Ω halmaz feletti olyan halmazcsalád vagy -rendszer, amely ideál (azaz nem üres, végesunió-zárt és zárt a részhalmazképzésre); továbbá nem tartalmazza az Ω tartóhalmazt.

Hivatkozások

[szerkesztés]

Megjegyzések

[szerkesztés]
  1. Amely definíciók többféle változatban is előfordulnak a szakirodalomban, ott hivatkozást adunk az illető változat egy előfordulására.

Források

[szerkesztés]
  1. Az „antilánc” kifejezésnek van egy általánosabb, a rendezett struktúrák elméletéhez kapcsolódó másik jelentése is
  2. Ring of sets Archiválva 2007. szeptember 30-i dátummal a Wayback Machine-ben – Planetmath.org.; v. 2007. augusztus 22. 12:48.
  3. Hajnal-Hamburger: Halmazelmélet, Nemzeti Tankönyvkiadó 1994; 3. kiad. 155. o.
  4. Róka Sándor: Független metszőrendszerek. Acta Academiae Paedagogicae Nyíregyháziensis (Matematikai-informatikai közlemények), XII. köt., 17-20. o.
  5. Bohman – Frieze – Martin – Ruszinko – On Randomly Generated Intersecting Hypergraphs II