Halmazrendszerek geometriája/Illeszkedési síkok

Nem-elfajuló hipergráf

Definíció:

---

Egy (U,E) hipergráfot nem-elfajulónak mondunk, ha szerkezete nem üres, és az üres halmazt sem tartalmazza; ellenkező esetben (azaz ha üres, vagy tartalmazza élként az üres halmazt) elfajulónak mondjuk.

Egy elfajuló hipergráfot félig elfajulónak mondunk, ha nem üres, és teljesen elfajulónak, ha üres.

Az egyetlen érdekes kérdés ezzel kapcsolatban, hogy egy véges U halmaz felett hány hipergráf elfajuló, illetve nem-elfajuló.

Egy véges, n-elemű U halmaz felett $2^{2^n}$ db. hipergráf értelmezhető, minthogy ennyi eleme van a ℘(U) hatványhalmaz hatványhalmazának. Ha ℘(U)-ból eltávolítjuk az üres halmazt, amely az eleme, akkor elemeinek száma eggyel csökken, és egy |℘(U)|-1 = 2ⁿ-1 -elemű U' halmazt kapunk. Az U feletti, üres halmazt elemként nem tartalmazó hipergráfok épp az U' részhalmazai. Ezek száma így $2^{2^n-1}=\frac{2^{2^n}}{2}=0.5\cdot 2^{2^n}=0.5\cdot 2^{2^{|U|}}$. Tehát ennyi ∅-t nem tartalmazó hipergráf van egy n-elemű halmaz felett.

Sajnos - ha mondhatjuk ezt - ezek közt még lehet elfajuló, és van is pontosan egy, amelyik üres. Hiszen ℘(U') részhalmazai, azaz ℘(℘(U)) elemei csak elemként nem tartalmazhatják ∅-t, de lehet(nek) üres(ek), hiszen ∅∈℘(℘(U)). De csak ez az egy elem lehet üres, azaz kimondhatjuk a következő tételt:

Tétel:

---

Az U feletti elfajuló és nem-elfajuló hipergráfok száma egyenlő, mégpedig

$2^{2^{|U|}-1}-1=\frac{2^{2^{|U|}}-2}{2}$,

Az elfajulók közül 1 a teljesen elfajuló hipergráfok száma, a maradék félig elfajulóké pedig

$2^{2^{|U|}-1}=0.5\cdot 2^{2^{|U|}}$.

Bizonyítás:

---

A bizonyítást ld. a tétel kimondását megelőző bekezdésekben.

⍰ Gyakorló feladat: Keressünk bijektív (kölcsönösen egyértelmű) leképezést egy adott halmaz feletti nem-elfajuló és az elfajuló hipergráfok halmaza között, majd gondoljuk meg, hogy egy ilyen megfeleltetés létezéséből hogyan következik a tétel!

Illeszkedési sík

Definíció:

---

Egy nem-elfajuló hipergráfot illeszkedési síknak nevezünk, ha

1. Tartóhalmaza tartalmaz legalább három elemet;
2. Bármely élének van legalább két pontja.

Az illeszkedési síkok csúcsait pontoknak is szokás nevezni.

Jegyzetek

Lap teteje