Matematické Fórum

Andrejka3

Dobrý den.
Podobnost tvrzení okolo existencí minimálních (disjunktních) rozkladů konečných uspořádaných množin na řetězce, resp. antiřetězce mě navedla k některým nejasným otázkám.

Buď $P=(X,\preceq)$ uspořádaná konečná množina. Buď $\mathcal{A}=(A_1,\dots, A_{\omega (P)})$ její (minimální) rozklad na antiřetězce. Uspořádejme antiřetězce z $\mathcal{A}$ podle mohutnosti a označme $N_i$ počet antiřetězců z rozkladu, jež mají mohutnost $i$ , kde stačí vzít $i = 1,\dots , \alpha(P)$ .
Dostaneme posloupnost $N_1,\dots ,N_{\alpha (P)}$ , tak že $\sum_{i=1}^{\alpha (P)} N_i =\omega(P)$

1) Je $N_{\alpha (P)} \geq 1$ ?
Vyřešeno v ↑ Andrejka3:, odpověď

Autor skryl část textu. Zobrazit/skrýt!

2) Jak moc dobře tato posloupnost charakterizuje uspořádanou množinu? Tak například, kolik neizomorfních uspořádaných množin má posloupnost (1,2)?

3) Existuje uspořádaná množina, která má aspoň dva různé minimální rozklady dávající různé posloupnosti?
Vyřešeno v ↑ Andrejka3:, odpověď

Autor skryl část textu. Zobrazit/skrýt!

Otázky 4,5,6 v dalších dvou příspěvcích.

Analogicky pro rozklad na řetězce. Jsou to triviální otázky, nebo kolem toho existuje teorie? (Když tak se to dá přesunout do sekce VŠ).

Značení, definice, věty:
rozkladem množiny mám na mysli dusjunktní systém jejích neprázdných podmnožin, který ji pokrývá.
alfa, omega:

Autor skryl část textu. Zobrazit/skrýt!

Věty o rozkladech (některé nejsou přímo převzaté, ale dělala jsem důkazy)
na antiřetězce:

Autor skryl část textu. Zobrazit/skrýt!

na řetězce:

Autor skryl část textu. Zobrazit/skrýt!

Andrejka3

↑ Andrejka3:
Nevěděla jsem, kdy a jestli vůbec nějakou otázku vyřeším.
ad 1,3:

Autor skryl část textu. Zobrazit/skrýt!

Je znám algoritmus pro konstrukci rozkladu P do antiřetězců:
Zkonstruujeme $X_1,\dots ,X_t \subset X$ pomocí algoritmu:
$X_1:=\{x \in X;\; x \text{ minimální}\}$
$\text{Ať jsou }X_1,\dots ,X_l \text{ definovány. Pak}$
$X'_l:=X \setminus \bigcup_{i=1}^l X_i\:. \qquad X'_l \begin{cases}=\emptyset & \text{ položíme }t=l\text{ a ukončíme konstrukci.}\\ \neq \emptyset & X_{l+1}:=\{x' \in X'_l;\;x' \text{ minimální v }(X'_l,\preceq |_{\text{\tiny rest}})\} \end{cases}$

4) Takto dostaneme minimální rozklad (právě $\omega (P)$ antiřetězců). Je v tomto rozkladu nutně antiřetězec s mohutností $\alpha (P)$ ?
Vyřešeno v ↑ Andrejka3:, odpověď:

Autor skryl část textu. Zobrazit/skrýt!

5) Existuje algoritmus pro nalezení minimálního rozkladu na řetězce? Edit: něco lepšího než projít všechny možnosti.

Andrejka3

↑ Andrejka3:
ad 4:

Autor skryl část textu. Zobrazit/skrýt!

6) Pro každou poset, konečnou existuje minimální rozklad na antiřetězce, který obsahuje antiřetězec mohutnosti $\alpha (P)$ .
Vyřešeno v ↑ Andrejka3:, odpověď:

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 16. 01. 2013 20:35

↑ Andrejka3:
Ahoj, ad 5) Ano, ale asi Ti jde o nějaký algoritmus, který neprochází všechny možnosti, že?

Andrejka3 · 16. 01. 2013 20:52

↑ check_drummer:
Ahoj, ano. Měla jsem to specifikovat. Ale pokud máš nějaký míň brutální než udělej všechny možné rozklady do $\alpha (P)$ množin, budu za něj ráda.
Je to zvláštní. Když máme Hasse diagram, je jednoduché použít ten algoritmus na rozklad do antiřetězců, protože minimální prvky se hledají snadno.
A myslíš si něco o 6)?

check_drummer · 16. 01. 2013 22:15

↑ Andrejka3:
Ad 6) zatím nevím. :-)
Ad 5) A co třeba hladový algoritmus? Začni s nějakým minimálním prvkem a prodlužuj řetězec libovolně dokud to lze. Tím získáš řetězec. Stejným způsobem tvoř další řetězce, dokud je to možné. Ani jsem se ale nepokoušel dokázat správnost ani najít protipříklad.

check_drummer · 16. 01. 2013 22:34

↑ Andrejka3:
Jen takový nápad:
Pokud mám nějaký maximální antiřetězec B a v nějakém minimálním rozkladu na antiřetězce se bude vyskytovat B (resp. jeho prvky) v aniřetězcích B1,..,Bk, pak pokud vezmu B1 a jako Ci (i=2,..,k) označím ty prvky z B1, které jsou porovnatelné s Bi. pak bych mohl v B1 zaměnit prvky Ci a Bi (pokud se nějaký prvek vyskytuje ve více Ci, pak ho zařadím jen do jednoho Bi). Přesněji - zaměnit prvky zanmená vyměnit je mezi jimi odpovídajícími antiřetězci. Po této záměně tedy bude B1 obsahovat všechna Bi, tj. celý B.
Otázka je, zda je to postup korektní.

Andrejka3

↑ check_drummer:
Zajímavý nápad!
Zkoušela jsem si ověřit, jestli rozumím tomu postupu.

Existuje jediný 3 prvkový antiřetězec. Ten je obsažen v červeném a modrém antiřetězci - B_1 a B_2.
C_2 = modrá kulička nahoře. Tu obarvím na červeno a ty spodní dvě na modro.

Skvělé je, že takto opravdu získám opět antiřetězce.
Vždy musí dojít k netriviální výměně, jinak by ty dva antiřetězce šly sjednotit do jednoho, že? To by byl spor s minimalitou rozkladu.
Edit: Budu o tom přemýšlet. Jsem moc ráda, žes o tom přemýšlel.

Myslím, že to je dobře. :)

check_drummer · 16. 01. 2013 23:29

↑ Andrejka3:
Ještě je potřeba to doladit - ve Tvém případě bys také mohla začít s dvěma červenými prvky jako B1 a pak bys už neměla je za co vyměnit s tím modrým (B2) vpravo dole (tentokrát bychom sestavovali maximální antiřetězec v červené barvě). Ale to prostě vyřešíme tak, že je-li Ci prázdná, tak prostě Bi přesuneme do B1 bez výměny. Spor s minimalitou rozkladu to není, protože minimalita rozkladu a minimalita délky konkrétního antiřetězce jsou dvě různé věci.

Nerozumím Tvé otázce:
"Proč ale musí k sobě přijít ty prvky onoho maximálního antiřetězce...?"

Andrejka3 · 16. 01. 2013 23:41

↑ check_drummer:
Jo, to jsem editovala pryč. Musím si to promyslet, jsem pomalá.

Andrejka3

Ad 6)

Autor skryl část textu. Zobrazit/skrýt!

Teď už zbývá jen slušný algoritmus na rozklad do řetězců a dokázat analogická tvrzení pro "anti objekty". Předpokládám, že to vyjde stejně - ale kdo ví. Pro úplnost to asi dodělám.

↑ check_drummer: Hladový algoritmus neznám. Tyhle věci neovládám (ale vyhledat si to můžu..). Díky za nápady!

Edit: Byla bych klidnější, kdyby někdo potvrdil správnost těch vět na začátku. Ještě to je pro mě novinka a asi bych dostala infarkt, kdybych tam po pár měsících našla chybu.

Andrejka3 · 18. 01. 2013 16:51

Řešení 6) ještě nabídlo další záhadu, ale to už možná zacházím moc daleko.
Kdyby někoho ještě něco napadlo, nebo měl otázky, prosím, neváhejte napsat. Jinak, na hlavní otázky mám odpovědi, takže téma označím jako vyřešené.

check_drummer

↑ Andrejka3:
Hladový alg. bere co nejvíc může a moc neplánuje. :-) Takže poté co zvolím libovolný maximální řetězec, tak ho odstraním a dále vyberu další řetězec stejným způsobem, tak pokračuju dokud nenajdu celý rozklad.

Ale vidím, že máš protipříklad... Možná by tedy bylo vhodné volit takový řetězec, na který je "napojeno" co nejméně dalších prvků...

Andrejka3

↑ check_drummer: Díky za milé vysvětlení :)

K těm posets, které nemají minimální rozklad s "největším (anti)řetězcem". Vlastně jsem to pozorování už učinila, ale nenapsala ho.

Umluva / omluva: Zaměňuji mezi sebou nosnou množinu X a název struktury P, jak mi to přijde pod ruku.
Edit: nějaké úvahy. Vyplynula z nich charakterizace množin, jež nemají mini. rozklad s max objektem.

Autor skryl část textu. Zobrazit/skrýt!

Buď $P=(X ,\preceq)$ poset, konečná. Označme $\mathcal{S}_A$ systém všech antiřetězců s mohutností $\alpha(P)$ . Platí:

analogicky, ctrl+c, ctrl+v
Buď $P=(X ,\preceq)$ poset, konečná. Označme $\mathcal{S}_C$ systém všech řetězců s mohutností $\omega(P)$ . Platí:

Andrejka3

↑ Andrejka3:
Jaké podstruktury musí nutně mít posets, které nemají minimální rozklad do antiřetězců s antiřet. s moh. $\alpha (P)$ ?
1) $\omega (P)>1$ .
2)Volme $A_0$ antiřetězec, $|A_0|= \alpha (P)$ .
3) Dle charakterizace v předchozím příspěvku existuje $C$ řetězec, $|C| = \omega (P): C \cap A_0= \emptyset$ .
Označme $c_1 = \min C$ , $c_{\omega (P)}=\max C$ .
$A_0 \cup \{c_i\}$ není antiřetězec, tedy existuje $a_1,a_2 \in A_0:\; (a_i,c_i) \text{ jsou porovnatelné. }$
Jistě musí být $c_1<a_1$ a $a_2 < c_{\omega(P)}$ .
Kdyby $a_1=a_2$ , z maximality $C$ musí být $\omega (P) \geq 3$ . Nyní můžeme postupovat po bezprostředních následnících řetězce. Tak pro $c_2$ plyne, že nemůže být $a_1\prec c_2$ , byl by to spor s maximalitou řetězce. Musí být buďto $c_2 \prec a_1$ anebo jsou neporovnatelné. Kdyby ovšem $c_2 \prec a_1$ , můžeme stejně argumentovat pro $c_3$ . Takhle se lze dostat až k $c_{\omega(P)-1}$ , kde ovšem již nemáme jinou možnost než aby byly $c_{\omega (P)-1},a_1$ neporovnatelné. Souhrnně, $1\leq i_m:=\max \{i;\;c_i \prec a_1\} <\omega (P)-1$ .
Stejně lze postupovat zvrchu dolů, takže dostaneme $2<i_M:=\min \{i;\;c_i \prec a_1\} \leq \omega (P)$ . Je $i_m<i_M$ a tak (opět z maximality řetězce) rovněž existuje něco mezitím, $i_m< j<i_M$ . Pak $c_j$ je neporovnatelné s $a_1$ . Do P pak lze vnořit struktura

Kdyby $a_1 \neq a_2$ , pak musí poset obsahovat strukturu

Tady je problém s barevnými čarami. O nich nic nevím. Pokud tam je aspoň jedna, pak lze převést na případ první. Pokud není ani jedna, nutno řešit zvlášť:
$i_m:=\max\{i;\;c_i \prec a_1\}$ , $i_M:=\min \{i;\; a_2 \prec c_i\}$ . Z nezávislosti $A$ plyne $i_m<i_M$ , tedy do P lze vnořit

Přidám jen ještě, že $\omega (P)>2$ je nutná podmínka pro to, aby poset neměla min rozklad s max antiř. To je intuitivní.
Ke spokojenosti chybí vyvrátit domněnku o vnoření M_3 a N_5 nějakým protipříkladem.
Závěr: Poset nemá min. rozklad do antiř. obsahující alfa antiřet, pak aspoň jedna z dvou struktur (bez barevných čar) do ní lze vnořit.
Edit: Update.
Edit: Úplně stejnou věc dostanu pro rozklady na řetězce, protože z těch charakterizačních tvrzení jsem použila pouze existenci dvojice A,C antiř a řet s mohutností alpha, resp omega takové, že mají prázdný průnik. Jak využít tvrzení v celém znění, to nevím.

Andrejka3

Myslím, že docela zajímavý update ohledně podstruktur v předchozím příspěvku.

Hlavní výsledek je charakterizace posets, které nemají rozklad do minim. antiřetězců s \alpha(P)-prvkovym antiřetězcem a jeji analogie pro retezce.

Podstruktury, které jsem dostala a které musí obsahovat každá taková poset (neexistence min rozk do anti. s alfa antir.) jsou moc titěrné. Kromě toho je to jen nutná podmínka, takže to je chabé.

Matematické Fórum

#1 15. 01. 2013 15:15 — Editoval Andrejka3 (17. 01. 2013 12:42)

Rozklady uspořádaných množin na (anti)řetězce.

#2 15. 01. 2013 21:38 — Editoval Andrejka3 (18. 01. 2013 16:48)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#3 15. 01. 2013 22:33 — Editoval Andrejka3 (17. 01. 2013 12:46)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#4 16. 01. 2013 20:35

Re: Rozklady uspořádaných množin na (anti)řetězce.

#5 16. 01. 2013 20:52

Re: Rozklady uspořádaných množin na (anti)řetězce.

#6 16. 01. 2013 22:15

Re: Rozklady uspořádaných množin na (anti)řetězce.

#7 16. 01. 2013 22:34

Re: Rozklady uspořádaných množin na (anti)řetězce.

#8 16. 01. 2013 23:12 — Editoval Andrejka3 (16. 01. 2013 23:25)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#9 16. 01. 2013 23:29

Re: Rozklady uspořádaných množin na (anti)řetězce.

#10 16. 01. 2013 23:41

Re: Rozklady uspořádaných množin na (anti)řetězce.

#11 17. 01. 2013 12:03 — Editoval Andrejka3 (18. 01. 2013 16:43)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#12 18. 01. 2013 16:51

Re: Rozklady uspořádaných množin na (anti)řetězce.

#13 18. 01. 2013 20:00 Příspěvek uživatele check_drummer byl skryt uživatelem check_drummer. Důvod: Už vidím reakci.

#14 18. 01. 2013 20:04 — Editoval check_drummer (18. 01. 2013 20:11)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#15 21. 01. 2013 10:54 — Editoval Andrejka3 (21. 01. 2013 11:29)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#16 21. 01. 2013 11:59 — Editoval Andrejka3 (23. 01. 2013 13:06)

Re: Rozklady uspořádaných množin na (anti)řetězce.

#17 22. 01. 2013 13:36 — Editoval Andrejka3 (22. 01. 2013 14:35)

Re: Rozklady uspořádaných množin na (anti)řetězce.

Zápatí