5. Extremális halmazrendszerek

Question 1

Általános probléma:

Answer 1

Adott $n$ elemű alaphalmaznak hány, adott $Φ$ tulajdonságú részhalmaza adható meg legfeljebb?

Question 2

Extremális halmazrendszerek

Answer 2

Az extremális szó latin eredetű, jelentése “szélsőséges, túlzó, rendkívül nagy”. Véges halmazok tanulmányozásánál gyakran merül fel alábbi típusú kérdés:

Adott $n$ elemű alaphalmaznak hány, adott $Φ$ tulajdonságú részhalmaza adható meg legfeljebb? (általános probléma)

Az extremális halmazrendszerek és a Sperner-tulajdonság olyan kombinatorikus fogalmak, amelyek a részhalmazok számát és tulajdonságait vizsgálják.

Question 3

Sperner I:

Answer 3

Ha $S$ tetszőleges nemüres halmaz, $|S| = n$ , $A_i ⊆ S$ tetszőleges részhalmazok $(i=1,…,m)$ amelyekre teljesül, hogy $A_i \nsubseteq A_j$ ha $i \neq j$, akkor $m ≤ \binom{n}{\frac{n}{2}}$ és a becslés éles. ($A_i \nsubseteq A_j$, $i \neq j$ a Sperner tulajdonság).

Question 4

Partíciós problémák

Answer 4

Definíció: Az $n \in \N$ szám egy k-részre történő felosztása (partíciója)

$n = a_1 + … + a_k$

ahol $a_1 \geq … \geq a_k \geq 1$ természetes számok.

Rögzített $n,k \in \N$ természetes számok esetén jelölje $P(n,k)$ az $n$ szám $k$ részre történő felosztásainak számát, míg $P(n)$ jelölje az $n$ szám összes felosztásainak számát, azaz legyen

$P(n) := \sum_{k=1}^{n}P(n,k)$

Ha az n természetes számot egy n-elemű halmaznak tekintünk, aminek elemeni megkülönbözhetetlenek, akkor az előző egyenlőség egy pontosan k elemű nemüres partíciónak felel meg, ahol a partíció elemeinek sorrendje nem lényeges.

Állítás: $P(n,k) \geq \frac{1}{k!}\binom{n-1}{k-1}$

A partíciós probléma az extremális halmazrendszerek témakörben egy olyan probléma, amelyben egy adott halmazt vagy számhalmazt kell felosztani részhalmazokra bizonyos szabályok vagy tulajdonságok szerint.

Hasonló feltételek vagy korlátok lehetnek:
- Részhalmazok diszjunktak legyenek, azaz ne legyenek közös elemek.
- Minden részhalmaz adott méretű legyen, vagy meghatározott tulajdonsággal rendelkezzen.
- A részhalmazok összege, mérete vagy egyéb tulajdonságai előre meghatározott értékekkel egyenlők legyenek.