Fogalomtár

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 K_{a1, a2, ... , at} az a gráf, amelyre V= A₁ U A₂ U ... U A_t, ahol az A_i-k páronként diszjunktak és |A_i| = a_i. Továbbá E(G) = {{x,y}: x és y különböző A_i-k elemei} A K_{a1, 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 (f₀, f₁, ... , f_n) vektor, amely f_i 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={L₁, L₂, ... , L_t} lánc részhalmaza szimmetrikus lánc, ha van olyan i, hogy |L₁|=i, |L₂|=i+1, ... , |L_t| = |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 G_P 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 M_I 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

H₁, ... , H_s egy s szirmú napraforgó (vagy Δ-rendszer), ha bármely i és j különböző indexek esetén H_i e;s H^j megegyezik az összes halmaz metszetével. Az összes H_i metszetét napraforgó tányérjának nevezzük.

Nyom, halmazrendszeré

Η halmazrendszer V felett, A egy csúcshalmaz. Ekkor legyen Tr_A (Η) = {R: egy E él és A metszete}, a Η halmazrendszer A-ra vet nyoma.

Telített ponthalmaz, egy halmazrendszerre néze

Ha Tr_A(Η) = 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 dim_VCs(Η).

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

• Kiindulás: Legyen Η_aktuális=Η, L=0, M=V
• Amíg Η_aktuális-nak éle van ismételjük a következő fázist:
  • Kiválasztás: Legyen v a Η_aktuális egy legnagyobb fokú csúcsa. v-t adjuk L-hez.
  • Csonkítás: Η_aktuális-ból hagyjuk el v-t tartalmazó éleket.

&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: v₀, E₁, v₁, ... , v_k-1, E_k, v_k=v₀ sorozat, ahol a v_i (i=0,1,2,...,k-1) csúcsok különbözőek és v_i-1, v_i az E_i él elemei. V(C) = {v₀, v₁, ... , v_k-1. k a kör hossza.

Szelid kör

Egy C kör szelid, ha minden E_i éle V(C)-ből pontosan v_i-1 és v_i 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) = chi_e(R) minden R részhalmazrendszerre.

Szép⁺ hipergráf

A Η hipergráf szép⁺, ha Δ(T) =chi_e(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 (F_i) események (i egy I indexhalmaz egy eleme) egy rendszerétől, ha tetszőleges T eseményre, amely az F_i-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 (E_i: i az I indexhalmaz eleme} események egy rendszere. Ez független eseményrendszer, ha minden I-beli i-re véve az F_i 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 (E_v)_{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 E_v független {E_u: 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

R^d két pontját kössük össze, ha egységtávolságra vannak egymástól. R^d 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

• R(k) az a minimális n szám, amelyre tetszőleges f: E(K_n) -> {piros, kék} csúcsszínezése esetén garantáltan lesz $k$ elemű monokromatikus csúcshalmazunk $(K_n az n pontú teljes gráf. Egy csúcsalmaz monokromatikus, ha az összes benne haladó él ugyanazt a színt kapja)
• R(p,k) az a minimális n szám, amelyre tetszőleges f: E(K_n) -> {piros, kék} élszínezése esetén lesz $p$ elemű piros vagy $k$ elemű kék halmazunk.

Háromszög-bontás A teljes gráf éleinek háromszögekre particionálása, háromszög-parkettázása.

<_KK^k

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.

S_i,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 S_i,j(E)-t definiáljuk: Általában S_i,j(E) megmarad a E halmaznak. Kivétel, ha j eleme, míg i nem eleme az E élnek. Amikor is S_i,j(E) = E-{j} U {i}.

S_i,j a <_KK^k rendezésben előre probálja vinni a k-elemű éleket.

Legyen Η egy k-uniform halmazrendszer. Ha egy E élre S_i,j(E) nem él (speciálisan a shift megváltoztatja az élt, akkor cseréljük le E-t S_i,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.

&tau_mohó(Η)

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.

V_G halmazrendszer

Legyen G egy irányított gráf. V_G az a halmazrendszer, amely alaphalmaza E(G) és éleit a vágásai élhalmazai adják.

C_G

Legyen G egy irányított gráf. Legyen C_G 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.

chi_e(Η)

Az a minimális k, amelyre Η-nak létezik jó élszínezése k színnel.

F_G

Legyen G egy gráf. F_G 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 E_x él felel meg, ahol ahol E_x pontosan azokat a pontokat/G-beli független ponthalmazokat tartalmazza, amelyeknek x eleme.

Frankl-Wilson gráf

Legyenp prímszám. Legyen $G_FW(v, p) a következő egyszerű gráf. Csúcsai egy v-elemű V halmaz összes p²-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.