Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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ěď



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ěď

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:
Věty o rozkladech (některé nejsou přímo převzaté, ale dělala jsem důkazy)
na antiřetězce:
na řetězce:


What does a drowning number theorist say?
'log log log log ...'

Offline

  • (téma jako vyřešené označil(a) Andrejka3)

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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


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ěď:
5) Existuje algoritmus pro nalezení minimálního rozkladu na řetězce? Edit: něco lepšího než projít všechny možnosti.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ Andrejka3:
ad 4:



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ěď:


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#4 16. 01. 2013 20:35

check_drummer
Příspěvky: 3557
Reputace:   91 
 

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

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


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#5 16. 01. 2013 20:52

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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)?


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#6 16. 01. 2013 22:15

check_drummer
Příspěvky: 3557
Reputace:   91 
 

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

↑ 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.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#7 16. 01. 2013 22:34

check_drummer
Příspěvky: 3557
Reputace:   91 
 

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

↑ 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í.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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. :)


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#9 16. 01. 2013 23:29

check_drummer
Příspěvky: 3557
Reputace:   91 
 

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

↑ 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...?"


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#10 16. 01. 2013 23:41

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

Ad 6)


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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#12 18. 01. 2013 16:51

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

Ř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é.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#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)

check_drummer
Příspěvky: 3557
Reputace:   91 
 

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

↑ 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ů...


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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.


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í:


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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é.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson