Halmazrendszer
Η halmazrendszer V felett, ha Η a P(V) egy részhalmaza, azaz Η a V részhalmazainak egy halmaza.
Hipergráf:
Η hipergráf (V felett) egy hármas: (V, E, I), ahol I egy illeszkedési reláció V és E között (azaz I a V×E egy részhalmaza). V elemei a halmazrendszer csúcsai, E elemei a Η halmazrendszer élei).
Fokszám, fok
Η halmazrendszer V felett, és legyen x egy csúcs (x az alaphalmaz egy eleme). x foka az x-et tartalmazó élek száma, jelölés dΗ(x).
k-uniform halmazrendszer, hipergráf
Η halmazrendzer/hipergráf k-uniform, ha bármely éle k elemű.
Steiner-rendszer
S halmazrendszer Steiner-rendszer, ha 3-uniform halmazrendszer, továbbá alaphalmaza bármely két különböző pontját pontosan egy halmazrendszerbeli él/hármas tartalmazza.
Skolem-párosítás
Skolem-párosítás {1, 2, ... , 2n} párosítása úgy, hogy a párokban lévő számpárok távolsága rendre 1, 2, ... , k legyen.
t-részes teljes gráf
A Ka1, a2, ... , at az a gráf, amelyre V= A1 U A2 U ... U At, ahol az Ai-k páronként diszjunktak és |Ai| = ai. Továbbá E(G) = {{x,y}: x és y különböző Ai-k elemei} A Ka1, a2, ... , at gráfokat t-részes teljes gráfoknak nevezzük.
Sperner-rendszer
Az S halmazrendszer Sperner-rendszer, ha bármely ke;t különböző éle között nincs tartalmazás.
f-vektor, halmazrendszeré
Legyen Η egy halmazrendszer egy n-elemű alaphalmaz felett. Ekkor Η f-vektora az (f0, f1, ... , fn) vektor, amely fi komponense megmondja, hogy hány i elemű él szerepel Η-ban.
Lánc, részbenrendezett halmazban
Legyen (P, <) részbenrendezett halmaz. Ekkor P egy L részhalmaza lánc, ha L bármely két eleme összehasonlítható.
Részbenrendezett halmaz
Egy (P, <) részbenrendezett halmaz, ha a P halmazon a reláció reflexív, antiszimmetrikus és tranzitív.
Antilánc, részbenrendezett halmazban
Legyen $(P, \le)$ részenrendezett halmaz. Ekkor $A\subset P$ antilánc, ha $A$ elemi páronként nem összehasonlítható.
Szimmetrikus lánc (P(V),tartalmazás)-ban
P(V) egy L={L1, L2, ... , Lt} lánc részhalmaza szimmetrikus lánc, ha van olyan i, hogy |L1|=i, |L2|=i+1, ... , |Lt| = |V|-i.
Perfekt gráf
Egy G gráf perfekt, ha minden F feszített részére (csak csúcs elhagyással nyerhető részgráfjaira) ω(F) = chi(F).
Összehasonlítási gráf, részbenrendezett halmazé
Legyen (P, <) részben rendezett halmaz. A P részbenrendezett halmaz összehasonlítási gráfja az a GP egyszerű gráf, ahol V(G) = P, továbbá két különböző csúcs x és y akkor és csak akkor van összekötve, ha összehasonlítható.
Metszet gráf, intervallumrendszeré
Vegyünk egy e egyenest. Legyen I intervallumok (összefüggő ponthalmazok) egy rendszere. Legyen ezen intervallumrendszernek a metszet gráfja, az az MI egyszerű gráf, amely csúcsai I elemei és két csúcs akkor és csak akkör összekötött, ha metszik egymást.
Metsző halmaz rendszer
Η metsző halmazrendszer, ha bármely két különböző élük metszi egymást.
Napraforgó vagy Δ-rendszer
H1, ... , Hs egy s szirmú napraforgó (vagy Δ-rendszer), ha bármely i és j különböző indexek esetén Hi e;s Hj megegyezik az összes halmaz metszetével. Az összes Hi metszetét napraforgó tányérjának nevezzük.
Nyom, halmazrendszeré
Η halmazrendszer V felett, A egy csúcshalmaz. Ekkor legyen TrA (Η) = {R: egy E él és A metszete}, a Η halmazrendszer A-ra vet nyoma.
Telített ponthalmaz, egy halmazrendszerre néze
Ha TrA(Η) = P(Η) akkor azt mondjuk, hogy A telített.
Vapnyik-Cservonyenkisz-dimenzió, halmazrendszeré
Egy Η halmazrendszer Vapnyik-Cservonyenkisz-dimenzióján azt a maximális számot értjük, amelyer van ilyen elemszámú telített csúcshalmaz. Jelölése dimVCs(Η).
Lefelé zárt halmazrendszer
Η lefelé zárt halmazrendszer, ha minden E élének minden R részhalmaza is egyben él.
Árnyék, halmazrendszeré
Legyen Η egy k-uniform halmazrendszer. Ekkor Ekkor Η árnyéka pontosan azon halmazokat tartalmazza, amelyek Η egy éléből egy csúcs elhagyásával megkapható. Azaz az árnyék egy k-1-uniform halmazrendszer.
Lefogó ponthalmaz, halmazrendszeré
Egy Η halmazrendszer L ponthalmazát lefogó ponthalmaznak nevezzük, ha minden él metszi L-et.
Párosítás vagy független élhalmaz
Egy Η halmazrendszer M élhalmazát párosításnak vagy független élhalmazoknak nevezzük, ha elemei páronként diszjunktak.
Tört-lefogás
Egy Η halmazrendszer (ωv)v csúcs súlyozása tört-lefogás, ha minden csúcs súlya nemnegatív, és tetszőleges élre az ebbe eső csúcsok súlyainak összege legalább 1. Egy tört-lefogás mérete az összes csúcs súlyainak összege.
Tört-párosítás
Egy Η halmazrendszer $(ωE)E él súlyozása tört-párosítás, ha minden él súlya nemnegatív, és tetszőleges csúcsra ez ezen átmenő élek súlyainak összege legfeljebb 1. Egy tört-párosítás, mérete az összes csúcs súlyainak összege.
&tau*(Η)
Legyen Η halmazrendszer. &tau*(Η) a legkisebb méret a tört-lefogások között.
&nu*(Η)
Legyen Η halmazrendszer. &nu*(Η) a legnagyobb méret a tört-párosítások között.
Automorfizmus, halmazrendszeré
Legyen Η egy halmazrendszer a V alaphalmaz felett. V egy π permutációja Η automorfizmusa, ha E akor és csak akkor él, ha π(E) él.
Mohó algoritmus "kicsi" lefogó ponthalmaz keresésére
&tau -kritikus halmazrendszer
Egy &Eta halmazrendszer &tau -kritikus, élet elhagyva &tau értéke változik/csökken/eggyel csökken. &tau(Η - E) = &tau(&Eta) -1, minden E élre.
Kőnig-tulajdonság, Kőnig-tulajdonság ú halmazrendszer
Egy Η halmazrendszer Kőnig-tulajdonságú, ha &nu(Η) = &tau(Η).
Totálisan unimoduláris mátrix
Egy mátrix totálisan unimoduláris mátrix, ha minden négyzetes részmátrixának determinánsa 0, 1, vagy (-1).
Totálisan unimoduláris halmazrendszer
Egy Η halmazrendszer totálisan unimoduláris, ha pont-él illeszkedési mátrixa unimoduláris.
Kör, halmazrendszerben
Legyen Η egy halmazrendszer. Egy kör egy C: v0, E1, v1, ... , vk-1, Ek, vk=v0 sorozat, ahol a vi (i=0,1,2,...,k-1) csúcsok különbözőek és vi-1, vi az Ei él elemei. V(C) = {v0, v1, ... , vk-1. k a kör hossza.
Szelid kör
Egy C kör szelid, ha minden Ei éle V(C)-ből pontosan vi-1 és vi csúcsokat tartalmazza.
Hiper-páros halmazrendszer
Egy Η halmazrendszer hiper-páros, ha minden szelid köre páratlan hosszú.
Vágás egy irányított gráfban
A G irányított gráf pontjainak két nem-üres osztalyba sorolása úgy, hogy a keresztélek ugyanabba az irányba haladjanak. Egy C irányított vágás induló oldala legyen A(C) (a keresztélek kezdőpontjait tartalmazó osztály), érkező oldala Z(C) (a keresztélek végpontjait tartalmazó osztály).
Kereszteződő vágáspár egy irányított gráfban
C és C' irányított vágások kereszteződőek, ha A(C)-A(C'), A(C)-Z(C'), Z(C)-A(C'), Z(C)-Z(C') négy darab halmazpár mindegyikének metszete nem-üres.
Normális halmazrendszer
Egy Η halmazrendszer normális, ha bármely részhalmazrendszere (belőle élethagyással kapható halmazrendszerek) Kőnig-tulajdonságúak.
Csúcs fokszáma/foka egy hipergráfban
Egy hipergráf v csúcsának fokszáma/foka a rá illeszkedő élek száma.
Jó élszínezés
Egy hipergráf jó elszínezése k színnel egy c: Η -> P = {1,2,..., k} színezési leképezés, amelyre a szomszédos/közös csúcsra illeszkedő élek különböző színt kapnak.
Szép hipergráf
A Η hipergráf szép, ha Δ(R) = chie(R) minden R részhalmazrendszerre.
Szép+ hipergráf
A Η hipergráf szép+, ha Δ(T) =chie(T), a Η minden N-súlyozott példányára.
Jó hipergráf
A Η hipergráf jó, ha minden R részhalmazrendszerére Δ(R) &nu(R) <= |R|.
Jó+ hipergrgráf
A Η hipergráf jó+, ha Δ(T) &nu(T) <= |T|, a Η minden N-súlyozott példányára.
Jó színezés
Egy Η halmazrendszer jó színezése k színnel, c: V -> P = {1, 2,..., k}, ha bármely E élre nem lesz monokromatikus él, azaz minden él tartalmaz két különböző színű csúcsot.
Független eseménypár
Legyen (Ω, A, P) valószínűségszámítási tér. Az E és F események akkor és csak akkor függetlenek, ha E és F együttes bekövetkezésének valószínűsége P(E)P(F).
Esemény függetlensége egy eseményrendszertől
Egy E esemény független az (Fi) események (i egy I indexhalmaz egy eleme) egy rendszerétől, ha tetszőleges T eseményre, amely az Fi-k, illetve ezek komplementerei metszeteként áll elő teljesül, hogy E és T együttes bekövetkezésének valószínűsége P(E)P(T).
Független eseményrendszer
Legyen (Ei: i az I indexhalmaz eleme} események egy rendszere. Ez független eseményrendszer, ha minden I-beli i-re véve az Fi eseményt vagy ennek komplementerét és az így kapott események metszetét vesszük, akkor a metszet valószínúsége megegyezik a metszet tagok valószínúségeinke szorzatával.
Eseményrendszer függőségi gráfja
Legyen (Ev)v V-beli események egy rendszere. G egy egyszerű gráf a V halmazon (csúcsokat és eseményeket azonosítottnak vesszük). Azt mondjuk, hogy G az eseményrendszer függőségi gráfja, ha minden v csúcs esetén Ev független {Eu: u és v nem szomszédos} rendszertől.
Kromatikus szám, halmazrendszeré
Legyen Η halmazrendszer. Η kromatikus száma az a legkisebb k érték, amelyre már van jó színezése Η-nek k színnel.
Sík kromatikus száma
A sík két pontját kössük össze, ha egységtávolságra vannak egymástól. A sík pontjain (kontinuum sok csúcs) így kapott gráf kromatikus száma a sík kromatikus száma.
Tér kromatikus száma
Rd két pontját kössük össze, ha egységtávolságra vannak egymástól. Rd pontjain (kontinuum sok csúcs) így kapott gráf kromatikus száma a d-dimenxiós tér kromatikus száma.
Egy kompakt halmaz Borsuk-paramétere
Legyen K egy korlátos zárt alakzat. Ezt szeretnénk feldarabolni az eredetinél kisebb átmérőjű részekre. B(K) a minimális számú darab, amivel a feladat megoldható. Ezt a paramétert nevezzük egy kompakt halmaz Borsuk-paraméterének.
Legyen B(d) a d-dimenziós K alakzat között a maximális paraméter.
Ramsey-számok
Háromszög-bontás A teljes gráf éleinek háromszögekre particionálása, háromszög-parkettázása.
<KKk
A természetes számok k-asainak egy rendezése: A k-eleműhalmazokat rendezzük, majd a rendezett sorok közt antilexikografikus sorrend szerint döntünk viszonyukról.
Si,j, shift/eltolás operátor
Legyen Η egy halmazrendszer a természetes számok halmaza felett. Legyen i< j két természetes szám. Legyen E egy él.
Először Si,j(E)-t definiáljuk: Általában Si,j(E) megmarad a E halmaznak. Kivétel, ha j eleme, míg i nem eleme az E élnek. Amikor is Si,j(E) = E-{j} U {i}.
Si,j a <KKk rendezésben előre probálja vinni a k-elemű éleket.
Legyen Η egy k-uniform halmazrendszer. Ha egy E élre Si,j(E) nem él (speciálisan a shift megváltoztatja az élt, akkor cseréljük le E-t Si,j(E)-re (E tovább már nem él. Más esetben E megmarad élnek.
&tau(Η)
A lefogó ponthalmazok minimális méretét &tau(Η)-val jelöljük.
&nu(Η)
A független élhalmazok maximális méretét &nu(Η)-val jelöljük.
&taumohó(Η)
A mohó lefogó algoritmus kiszámolt lefogó ponthalmaz mérete.
s(Η)
Η halmazrendszer esetén legyen s(Η) a legkisebb élméret Η-ben.
S{Η}
Η halmazrendszer esetén legyen S(Η) a legnagyobb élméret.
VG halmazrendszer
Legyen G egy irányított gráf. VG az a halmazrendszer, amely alaphalmaza E(G) és éleit a vágásai élhalmazai adják.
CG
Legyen G egy irányított gráf. Legyen CG az a halmazrendszer, amely alaphelmaza E(G) és éleit az irányított körök élhalmazai adják.
Δ(Η)
A Η hipergráf maximális fokszáma.
chie(Η)
Az a minimális k, amelyre Η-nak létezik jó élszínezése k színnel.
FG
Legyen G egy gráf. FG legyen az a halmazrendszer, amely U ponthalmazát G független ponthalmazai adják, míg élei azonsítottak G csúcsaival: az x csúcsnak az Ex él felel meg, ahol ahol Ex pontosan azokat a pontokat/G-beli független ponthalmazokat tartalmazza, amelyeknek x eleme.
Frankl-Wilson gráf
Legyenp prímszám. Legyen $GFW(v, p) a következő egyszerű gráf. Csúcsai egy v-elemű V halmaz összes p2-1-elemű részhalmaza. Két csúcs (V ke;t részhalmaza) akkor és akkor szomszédos, ha metszetük elemszáma p-vel osztva (-1)-et ad maradékul.