Matematické Fórum

vytautas · 02. 11. 2015 19:54

zdravím

vedel by mi niekto pomôcť, ako dokázať nasledujúce tvrdenie ?

Dokažte, že věta O Dlouhém a Širokém je nejlepší možná v následujícím smyslu:

$\forall k,l \in \mathbb{N}$ existuje čiastočne usporiadaná množina $P=(X,\le)$ s $n$ prvky splňující $n=kl$ , $\alpha (P)=k$ a $\omega (P) = l$ (Tzn. nalezněte takovou částočně uspořádanou množinu pre libovolné $k,l \in \mathbb{N}$ )

veta o dlhom a širokom: Nech $P=(X, \le)$ je čiastočne usporiadaná množina, $\alpha (P)$ je najdlhší antireťazec v P a $\omega (P)$ je najdlhší reťazec v P, potom $\alpha(P)\omega(P) \ge |X|$

ďakujem za každú radu.

Andrejka3 · 02. 11. 2015 20:28

↑ vytautas:
Ahoj.
Nevím, jestli to není úplně mimo, ale co takhle k nezávislých řetězců délky l ?

vytautas

hmm, to znie rozumne. Nejaký nápad ako to formálnejšie dokázať ? ďakujem

edit. neviem, ako mám chápať niečo ako "nezávislý reťazec". Mám nezávislú množinu (antireťazec/antichain) a reťazce (chain).

Ak by som si zobral $l$ antireťazcov s dĺžkou $k$ a "vybudoval" z nich množinu, stále nemám zaručené, že tam bude existovať reťazec dĺžky $l$ , či ?

Andrejka3

k=5, l=4:

Zřejmé, že neexistuje řetězec větší délky, ani antiřetězec větší...

vytautas · 02. 11. 2015 21:14

↑ Andrejka3:

aha, jasné, teraz to už vidím . čo sa týka formálnosti dôkazu ? :) nejaký hint ?

Andrejka3 · 02. 11. 2015 21:44

↑ vytautas:
Jak moc formální? Dívej, co se mi stane, když chci být formálnější:
Máme množinu $A=\{a^{i}_j;i\in\boldsymbol{l},\:j\in\boldsymbol{k}\}$ , kde $\boldsymbol{k}=\{1,2,\ldots, k\}$ .
Uspořádání $\mathrm{id}_A\cup\mathrm{T}\{(a^{i}_j,a^{i+1}_j);i\in\{1,\ldots,l-1\},\:j\in\boldsymbol{k}\}$ , kde T je tranzitivní uzávěr. Teď příklad maximálního řetězce a že má každý stejně prvků a max antiř a že má každý stejně prvků.
Prostě to vypadá hrozně, přitom obrázek je jasný.
To si už napíšeš sám...

vytautas · 02. 11. 2015 21:56

↑ Andrejka3:

už som to ako tak spísal.

ďakujem krásne, za ochotu hlavne, veľmi mi to pomohlo :)

Matematické Fórum

#1 02. 11. 2015 19:54

veta o dlhom a širokom

#2 02. 11. 2015 20:28

Re: veta o dlhom a širokom

#3 02. 11. 2015 20:53 — Editoval vytautas (02. 11. 2015 20:59)

Re: veta o dlhom a širokom

#4 02. 11. 2015 21:04 — Editoval Andrejka3 (02. 11. 2015 21:05)

Re: veta o dlhom a širokom

#5 02. 11. 2015 21:14

Re: veta o dlhom a širokom

#6 02. 11. 2015 21:44

Re: veta o dlhom a širokom

#7 02. 11. 2015 21:56

Re: veta o dlhom a širokom

Zápatí