\documentclass{report}
\usepackage{slovak,graphics,amsmath}
%\usepackage[psamsfonts]{amssymb}
\usepackage[psamsfonts]{amssymb}

%%%% vety, etc.
\newtheorem{teorema}{Teoréma}
\newtheorem{tvrdenie}[teorema]{Tvrdenie}
\newtheorem{veta}[teorema]{Veta}

\newenvironment{priklad}[1][Príklad]{\smallskip \noindent {\bf #1} }{\smallskip \par}
\newenvironment{lema}[1][Lema]{\begin{priklad}[#1] \itshape}{\end{priklad} \itshape}
\newenvironment{zaver}{\begin{lema}[Záver]}{\end{lema}}
\newenvironment{dosledok}{\begin{lema}[Dôsledok]}{\end{lema}}

\newcommand{\qed}{$\Box$}
\newenvironment{proof}{\par\noindent {\it Dôkaz. }}{\qed \medskip}

%%%%% matematicke znacky
\newcommand{\jj}{\vee}
\newcommand{\mm}{\wedge}
\newcommand{\JJ}{\bigvee}
\newcommand{\MM}{\bigwedge}

\DeclareMathOperator{\eq}{=}

\newcommand{\amp}{\ \& \ }
\newcommand{\then}{\ \Longrightarrow \ }
\newcommand{\when}{\ \Longleftarrow \ }
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\potential}{\mathcal{P}}
\newcommand{\nsd}{\mathrm{nsd}}
\newcommand{\nsn}{\mathrm{nsn}}

\pagestyle{headings}

\begin{document}

\title{Kombinatorické štruktúry}
\author{Martin Škoviera}

\maketitle
\tableofcontents
%\begin{titlepage}
%\begin{center}
%{\bf \Huge Kombinatorické štruktúry}

%\bigskip
%Martin Škoviera, FMFI UK

%\addvspace{5cm}
%{\bf  \today}
%\end{center}
%\addvspace{10cm}
%\end{titlepage}

%% original strana 1

\chapter{Usporiadané množiny}
\section{Základné pojmy}

\emph{Čiastočne usporiadaná množina} (skrátene čum, angl. poset) $(P, \leq)$ je množina s binárnou
reláciou $\le$ taká, že $\forall x,y,z \in P$:
\begin{enumerate}
\item $x \le x$ reflexívnosť
\item $x \le y \amp y \le z \then x \le z$ tranzitívnosť
\item $x \le y \amp y \le x \then x=y$ antisymetria
\end{enumerate}

\begin{priklad}
\begin{enumerate}
\item $(\mathbb{N}, \le)$ obyčajné lineárne usporiadanie
\item $(\potential(X), \subseteq)$
\item $(\mathbb{N}, \mid)$ napríklad $3\mid6$ ale $3\nmid7$.
\item $\{0,1\}^n$ $n$-rozmerná kocka so zvyčajným usporiadaním.
\item Množina $X$ a $\mathcal{D}(X)$ množina všetkých jej rozkladov. 
	$\sigma, \tau \in \mathcal{D}(X)$: $\sigma \le \tau$, ak $\sigma$ je zjemnením $\tau$.
\item $\mathrm{Eq}(X)$	množina všetkých ekvivalencií na $X$ s $\subseteq$. 
	$\mathrm{Eq}(X) \subseteq \potential(X \times X)$ a usporiadanie je zdedené.
\end{enumerate}
\end{priklad}

Nasleduje zopár ľahkých pojmov, ktoré sa do definície čumu nevošli.

\begin{itemize}
\item Ak $(P, \le)$ je čum a $Q \subseteq P$, tak na $Q$ máme \emph{zdedené usporiadanie} $\le_Q$.
\item Ak $a \le b$ alebo $b \le a$, tak prvky $a,b$ voláme \emph{porovnateľné}, inak
\emph{neporovnateľné}.
\item Ostrú nerovnosť definujeme ako $a < b \iff a \le b \amp a \ne b$.
\item Maximálne, minimálne, najväčšie, najmenšie prvky definujeme ako zvyčajne. Najmenší prvok značíme $0$
a najväčší $1$ (ak existujú). Všetky minimálne (resp. maximálne) prvky sú neporovnateľné. Najmenší
(resp. najväčší) je porovnateľný so všetkými prvkami.
\item Ak $a \le b$, tak $[a,b] = \{ x \in P\ |\ a \le x \le b \}$ voláme \emph{interval} čumu.
\item Ak $A \subseteq P$ a v $A$ sú každé dva prvky porovnateľné, tak $A$ je \emph{reťazec}. $A$ je
\emph{antireťazec}, ak žiadne dva prvky nie sú porovnateľné.
\item Hovoríme, že $b$ \emph{pokrýva} $a$, značíme $a \lessdot b$, ak $a < x \le b \then x=b$, t.j. ak
$[a,b]=\{a,b\}$. Prvky pokrývajúce $0$ voláme \emph{atómy} a prvky pokryté $1$ \emph{koatómy}.
%% original strana 2
\item \emph{Dualita} čumov: Ak $P$ je čum, tak $P^*$ označuje tú istú množinu s duálnou reláciou
$\le^* \ =\ \ge$. Samozrejme $P^{**} = P$. Duálne pojmy:
\begin{center}
\begin{tabular}{l|l}
$\le$ & $\ge$ \\
min & max \\
najmenší & najväčší \\
0 & 1 \\
atóm & koatóm \\
\end{tabular}
\end{center}

\item \emph{Dĺžka reťazca $C$} = \# prvkov  - 1 = \# znakov nerovnosti $\lessdot$
\item \emph{Výška prvku $h(a)$} = dĺžka najdlhšieho reťazca ukončeného prvkom $a$.
\item \emph{Nezjemniteľný reťazec} je taký, že medzi žiadne dva prvky nemožno vložiť tretí.
Ekvivalentne povedané, každý prvok (okrem posledného) je pokrytý nasledujúcim.

\item Existujú relácie podobajúce sa na usporiadanie, ale ním nie sú. Napríklad $Q$ množina delení
intervalu $\langle 0,1 \rangle$ ako v určitom intergráli. Pre $D_1, D_2, \in Q$ položíme $D_1 \unlhd D_2 \iff
||D_1|| \le ||D_2||$, kde $||\cdot||$ je norma delenia. Táto relácia je reflexívna a tranzitívna, ale
nie je antisymetrická. Táketo čosi sa volá \emph{kváziusporiadanie}. Ak $(P, \unlhd)$ je
kváziusporiadanie a zavedieme na ňom ekvivalenciu $x \sim y \iff x \unlhd y \amp y \unlhd x$, tak
dostávame čum na $P/\sim$.
\end{itemize}

Hovoríme, že $(P, \le)$ spĺňa \emph{podmienku klesajúcich reťazcov} (DCC), ak neexistuje nekonečná ostro
klesajúca postupnosť $a_1 > a_2 > \dots$ (Ekvivalentne povedané, ak každá neostro klesajúca
postupnosť $a_1 \ge a_2 \ge \dots$ sa \emph{stabilizuje}, t.j. ak existuje $n$ také, že
$a_n=a_{n+1}=\dots$) Duálne definujeme \emph{podmienku rastúcich reťazcov} (ACC).

\begin{tvrdenie}
Nech $P$ je čum. Nasledujúce podmienky sú ekvivalentné:
\indent
\begin{enumerate}
\item Každá neprázdna $Q \subseteq P$ má minimálny (maximálny) prvok.
\item $P$ spĺňa DCC (ACC).
\end{enumerate}
\end{tvrdenie}

\section{Zväzy}

Nech $(P, \le)$ je čum. Ak $a,b \in P$, tak ich horným ohraničením je každý prvok taký, že $c \ge
a$ a $c \ge b$. Najmenšie horné ohraničenie, ak existuje, sa nazýva \emph{spojením} prvkov $a,b$,
označuje sa $a \jj b$, alebo tiež \emph{suprémom} $\sup(a,b)$. Teda $a \jj b$ je taký
prvok $d$, že:
\begin{enumerate}
\item $d \ge a$, $d \ge b$
\item ak nejaký prvok $k$ spĺňa 1., tak $k \ge d$.
\end{enumerate}
%% original strana 3
Duálne definujeme \emph{priesek} $a \mm b$ ako najväčšie dolné ohraničenie prvkov $a,b$; tiež ho
nazývame \emph{infimum} a označujeme $\inf(a,b)$. Analogicky definujeme tieto pojmy pre
ľubovoľnú podmnožinu $Q \subseteq P$, značíme $\inf M = \MM M$ a $\sup M = \JJ M$; nemusia však
vo všeobecnosti existovať.

\begin{priklad}
\begin{enumerate}
\item $(\potential(X), \subseteq)$, $\mm = \cap$, $\jj = \cup$ a každá podmnožina
$\potential(X)$ má suprémum aj infimum.
\item $(\N, \mid)$, usporiadanie deliteľnosťou $\mm = \nsd$, $\jj = \nsn$
\item $\{0,1\}^n$, $\mm = \min$, $\jj = \max$
\end{enumerate}
\end{priklad}

Ak $(P, \le)$ je usporiadaná množina, v ktorej pre každú dvojicu $a,b \in P$ existuje $a \jj b$, tak
$P$ nazývame \emph{$\jj$-polozväz} (horný, spojovací polozväz). Analogicky definujeme
\emph{$\mm$-polozväz} (dolný, priesekový polozväz) (angl. semilattice).

\begin{teorema}
Nech $(P, \le)$ je $\jj$-polozväz. Potom platia identity:
\begin{enumerate}
\item $a \jj a = a$  (idempotencia)
\item $a \jj b = b \jj a$  (komutatívnosť)
\item $(a \jj b) \jj c = a \jj (b \jj c)$ (asociatívnosť)
\item $a \le b \iff a \jj b = b$
\end{enumerate}
Obrátene, nech $(M, \circ)$ je grupoid s vlastnosťami 1--3. Ak položíme $a \preceq b \iff a \circ b =
b$, tak $(M, \preceq)$ je usporiadaná množina, ktorá je vzhľadom na $\preceq$ horným polozväzom s
operáciou spojenia $\sup(a,b)=a \circ b$. 
(Analogická veta platí pre $\mm$-polozväzy.)
\end{teorema}

\begin{proof}
V prvej časti teorémy sa 1 až 4 overí priamo. Nech $(M, \circ)$ je grupoid s vlastnosťami 1--3 a položme 
$a \preceq b \iff_\mathrm{def} a \circ b = b$. Potom:
\begin{enumerate}
\item Idempotencia zaručuje reflexívnosť.
\item Nech $a \preceq b$ a $ b \preceq a$. Potom $a \circ b = b$ a $b \circ a = b$. Z komutatívnosti
máme $a = b \circ a = a \circ b = b$.
\item Nech $a \preceq b$ a $ b \preceq c$, chceme dokázať $a \preceq c$. Vieme $a \circ b = b$, $b
\circ c = c$, preto $a \circ c = a \circ (b \circ c) = (a \circ b) \circ c = b \circ c = c$. Teda $a
\preceq c$.
\item
Treba ešte ukázať, že vzhľadom na $\preceq$ je $\sup(a,b)=a \circ b$. Predovšetkým, $a \circ b$ je
horným ohraničením pre $a$ aj $b$, lebo:
$$ 
\begin{array}{lclclclcl}
a \circ (a \circ b) &=& (a \circ a) \circ b &=& a \circ b &&& \then & a \preceq a \circ b \\
b \circ (a \circ b) &=& (a \circ b) \circ b &=& a \circ (b \circ b) &=& a \circ b & \then & b
\preceq a \circ b \\
\end{array}
$$
%% original strana 4
Ešte treba ukázať, že $a \circ b$ je najmenšie horné ohraničenie. Nech $d$ je horným ohraničením $a$
aj $b$, čiže $a \preceq d$, $b \preceq d$. Ukážeme, že $a \circ b \preceq d$. Naozaj, máme $a \circ
d = d$, takže $(a \circ b) \circ d = a \circ (b \circ d) = a \circ d = d$. Teda $a \circ b \preceq
d$.
\end{enumerate}
\end{proof}

Dokázali sme, že existuje 1--1 korešpondecia medzi hornými polozväzmi a komutatívnymi pologrupami, v
ktorých každý prvok je idempotentný.

\medskip

\emph{Zväz} (angl. lattice) je usporiadaná množina $(P, \le)$, v ktorej každá dvojica prvkov má aj
priesek $\mm$ aj spojenie $\jj$. Ak v zväze naviac každá podmnožina $A \subseteq P$ má
$\MM A$ aj $\JJ A$, tak sa nazýva \emph{úplný} zväz. Pritom definujeme, ako sa to tradične
robí, $\MM \emptyset = \JJ P = 1$ (najväčší prvok) a $\MM P = \JJ \emptyset = 0$
(najmenší prvok).


\begin{teorema}
Nech $(P, \le)$ je zväz. Potom platia identity:
\begin{displaymath}
\begin{array}{clcllcl}
1. 	& a \jj a &=& a 	& a \mm a &=& a \\
2. 	& a \jj b &=& b \jj a	& a \mm b &=& b \mm a \\
3. 	& (a \jj b) \jj c &=& a \jj (b \jj c)	& (a \mm b) \mm c &=& a \mm (b \mm c) \\
4. 	& (a \jj b) \mm b &=& b	& (a \mm b) \jj b &=& b \mm (b \mm c) \\
5.	&  a \le b &\iff& a \jj b = b &\iff& a \mm b = a. &\\
\end{array}
\end{displaymath}
Obrátene, nech $(P; \jj, \mm)$ je algebra splňajúca identity 1--4. Potom definovaním $a \le
b \iff a \jj b = b$ vzniká usporiadaná množina, ktorá je zväzom, pričom $sup(a,b)=a \jj b$ a
$\inf(a,b) = a \mm b$.
\end{teorema}
\begin{proof}
Ľavú časť 1--3 a 5 sme ukázali v Teoréme 2, pravá vyplýva z duality.  4: $a
\jj b \ge b$, preto $(a \jj b) \mm b = b$; pravá časť je duálna.  Obrátene, ak máme
1--4, tak dôkazom Teóremy 2 dostávame usporiadanie, ktoré je horným polozväzom.
Ukázali sme totiž, že $a \jj b = \sup(a,b)$. Ostáva dokázať, že $a \mm b = \inf(a,b)$.
To urobíme takto. Najprv ukážeme, že $a \jj b = b \iff a \mm b = a$. \uv{$\then$}:
Nech $a \jj b = b$. Potom $a \mm b = a \mm (a \jj b) = (a \jj b) \mm a = (b
\jj a) \mm a = a$. \uv{$\when$}: Duálne.
Teda nerovnosť definovaná pomocu $\mm$ je tá istá ako nerovnosť
definovaná pomocou $\jj$ (ktorú sme prijali za základnú). Preto z toho, že $a \jj b =
\sup(a,b)$ a z princípu duality vyplýva, že $a \mm b = \inf(a,b)$.
\end{proof}

%% original strana 5

\begin{priklad}[Príklady zväzov]
\begin{enumerate}
\item $(\potential(X), \subseteq)$, úplný zväz
\item $(\N, \mid) = \mathcal T$, s operáciou deliteľnosti je úplný zväz
\item Zväz podgrúp, zväz normálnych podgrúp, zväz podpriestorov vektorového priestoru
(pre priestory nad konečnými poľami má kombinatorický význam).
\item Zväz rozkladov danej množiny, zväz ekvivalencií na danej množine (v akom sú vzťahu).
Má veľký význam pre kombinatoriku.
\item Príklad neuplného zväzu: Zväz otvorených množín na $\mathbb R$. (Otvorená množina je
disjuktným zjednotením otvorených intervalov, aj nekonečného počtu.) Prienik nekonečného
počtu otvorených množín nemusí byť otvorená.
\end{enumerate}
\end{priklad}

Na každý zväz sa môžeme dívať z dvojakého hľadiska: ako na množinu s reláciou $\le$, ale
aj ako na množinu s dvoma binárnymi operáciami. Táto dvojznačnosť má svoje dôsledky pre
porovnávanie zväzov pomocou morfizmov.

Morfizmus usporiadaných množín $(P, \le)$ a $(Q, \le)$ je \emph{izotónne zobrazenie}
$f: P \to Q$, teda také, že $a \le b$ v P implikuje $f(a) \le f(b)$. Ak zobrazenie
prevracia nerovnosti ($a \le b \then f(a) \ge f(b)$), tak sa nazýva \emph{antimónne}.
Ak $f$ je izotónna bijekcia, ešte nemusí byť izomorfizmus! \emph{Izomorfizmus} je
morfizmus taký, že aj $f^{-1}$ je morfizmus. No $f:(\N, \mid) \to (\N, \le)$, $x \mapsto
x$ je izotónna bijekcia, lebo $a\mid b \then a\le b$, no $f^{-1}$ nie je izotónne; teda
$f$ nie je izomorfizmus. Vo všeobecnosti, bijektívny morfizmus relačných štruktúr (takou
je aj usporiadaná množina) nemusí byť izomorfizmom.

No zväz (polozväz) je aj algebraický systém -- špeciálny prípad univerzálnej algebry -- s
dvoma binárnymi operáciami $\mm$ a $\jj$. Homomorfizmus zväzov $(P; \mm, \jj)$ a
$(Q; \mm, \jj)$ je zobrazenie $f:P \to Q$ také, že $f(x \mm y) = f(x) \mm f(y)$
a $f(x \jj y) = f(x) \jj f(y)$ , t.j. $f$ zachováva operácie. Na to, aby $f$  bolo
izomorfizmom zväzov, stačí povedať, aby zachovávalo operácie a bolo bijektívne. Naozaj,
nech $f$ je bijektívny homorfizmus. Potom $f(x \mm x) = f(x) \mm f(y)$ a $f^{-1}$
existuje. Ukážeme, že aj $f^{-1}$ zachováva operáciu $\mm$. Položme $f(x)=a$ a
$f(y)=b$, čiže $f^{-1}(a)=x$ a $f^{-1}(b)=y$. (Pre ľubovoľné $a,b$, také $x,y$ existujú.)
Potom z rovnosti:
\begin{eqnarray*}
f(x \mm y)  &=& f(x) \mm f(y) \quad \mathrm{dostávame} \\
f^{-1}(f(x \mm y))  &=& f^{-1}(f(x) \mm f(y)), \\
x \mm y  &=& f^{-1}(a \mm b), \\
f^{-1}(a) \mm f^{-1}(b) &=& f^{-1}(a \mm b). \\ 
\end{eqnarray*}

%% original strana 6

\begin{lema}[Záver]
Ak $(P; \mm, \jj, \le)$ a $(Q; \mm, \jj, \le)$ sú zväzy a $f:P \to Q$, tak nasledujúce
výroky sú ekivalentné:
\begin{enumerate}
\item $f$ je izomorfizmus.
\item $f$ je izotónna bijekcia taká, že aj $f^{-1}$ je izotónne zobrazenie.
\item $f$ je bijektívny homorfizmus vzhľadom na operácie $\mm$ a $\jj$.
\end{enumerate}
\end{lema}

Nech $(P; \mm, \jj)$ je zväz a nech $Q \subseteq P$. Potom $Q$ nazývame \emph{podzväzom} zväzu
$P$, ak $Q$ je zväz a pre ľubovoľné dva prvky $a,b \in Q$ platí $\inf_Q(a,b) = \inf_P(a,b)$ a
$\sup_Q(a,b) = \sup_P(a,b)$; teda výsledky operácií v zväze aj podzväze musia byť tie isté.

Može sa stať, že $Q \subseteq P$ s indukovaným usporiadaním dáva zväz, nie však podzväz zväzu $P$.
Napríklad:

%%%% obrazky zo strany 6
\begin{figure}
\begin{center}
\begin{tabular}{ccc}
\includegraphics{fig.1} & & \includegraphics{fig.2}
\end{tabular}
\end{center}
\caption{Zväzy $P$ a $Q$}
\end{figure}



\begin{tvrdenie}
V každom zväze $(P; \mm, \jj)$ ľubovoľná jednoprvková množina a prázdna množina tvoria podzväz.
Ak $a,b \in P$, tak interval $[a,b]$ je tiež podzväz. Prienik podzväzov je podzväz. \qed
\end{tvrdenie}

Nech $(P, \le_P)$ a $(Q, \le_Q)$ sú usporiadané množiny. Definujeme \emph{priamy súčin} ako
usporiadanú mnyožinu $(P \times Q, \le_{PQ})$, kde $(a,b) \le_{PQ} (c,d)$ práve vtedy, keď $a \le_P
c$ a $b \le_Q d$.

\begin{tvrdenie}
Ak $(P, \le_P)$ a $(Q, \le_Q)$ sú zväzy, tak aj $(P \times Q, \le_{PQ})$ je zväz. \qed
\end{tvrdenie}

\begin{dosledok}
Priamy súčin reťazcov je zväz.
\end{dosledok}
\begin{proof}
Každý reťazec je triviálne zväz. 
\end{proof}

%% original strana 7
Pri štúdiu kombinatorických štruktúr si často všímame zobrazenia $f,g:N \to R$, pričom
porovnávame zobrazenia pomocu obrazov, ignorujúc podstatu prvkov množiny $N$ (za ktoré berieme
napr. $N = \{0,1,\dots,n\}$ ak študujeme napr. variácie $k$-tej triedy). Na takéto zobrazenia je
niekedy výhodné sa dívať ako na \emph{multimnožiny}, kde každý prvok množiny $R$ sa môže opakovať
potrebný počet krát (toľkokrát, koľkokrát je obrazom). Takto  vzniká \emph{zväz multimnožín}
$\mathcal M(R)$ nad $R$. Pre dve multimnožiny $k=(b^{k_b}; b \in R)$ a $l=(b^{l_b}; b \in R)$ ($k_b,
l_b$ sú násobnosti prvku $b$ v $k$ resp. v $l$) položíme
\begin{eqnarray*}
k \mm l &=& (b^{\min(k_b,l_b)};\ b \in R), \\
k \jj l &=& (b^{\max(k_b,l_b)};\ b \in R). \\
\end{eqnarray*}
Je to úplný zväz.

\medskip \noindent
Platí:
\begin{enumerate}
\item Ak $|R|=n$ a $\N_0$ je množina nezáporných celých čísel lineárne usporiadaných podľa veľkosti,
tak $\mathcal M(R) \cong \underbrace{\N_0 \times \N_0 \times \dots \times \N_0}_{r}$
\begin{proof}
Zobrazenie $\varphi:\mathcal M(R) \to (\N_0)^r$, $k=(b^{k_b};\ b \in R) \mapsto (\dots,k_b,\dots)$
je hľadaný izomorfizmus.
\end{proof}

\item Ak $R$ je nekonečná spočítateľná množina, tak $\mathcal M(R) \cong (\N, \mid) = \mathcal T$,
kde vpravo je zväz prirodzených čísel usporiadaných deliteľnosťou.
\begin{proof}
Nech $R = \{r_1,r_2,\dots\}$. Potom každú multimnožinu vieme zapísať v tvare $k = r_1^{k_1} r_2^{k_2}
\dots$ Nech $p_1, p_2, \dots$ je postupnosť prvočísel v rastúcom poradí. Potom dostávame
izomorfizmus $\varphi: k=r_1^{k_1} r_2^{k_2}\dots \mapsto p_1^{k_1}p_2^{k_2} \dots$
\end{proof}

\item Nech $\mathcal C(n)$ je reťazec dĺžky $n$ (a teda mohutnosti $n+1$), t.j. $\mathcal C(n) =
\{0<1<2< \dots <n\}$. Skúmajme interval $[1,360]$ zväzu deliteľnosti $\mathcal T$. Keďže
$360=2^3 \cdot 3^2 \cdot 5$, ľahko sa nahliadne, že $[1,360] \cong \mathcal C(3) \times \mathcal C(2) \times \mathcal
C(1)$.

%%% obrazok zo strany 7

%% original strana 8
\item Zväz rozkladov $\mathcal D(n)$. Nech $\mathcal D(n)$ je napríklad množina všetkých rozkladov
$n$-prvkovej množiny $\{1,2,\dots,n\}$. Nech $\pi \in \mathcal D(n)$ a nech $(\pi)$ označuje reláciu
ekvivalencia odpovedajúcu $\pi$. Potom priesek a spojenie sa ľahko opíše. Potom pre ľubovoľné dva
prvky $a,b$
\begin{eqnarray*}
a(\pi \mm \sigma)b &\iff& a(\pi)b \mathrm{\ a\ } a(\sigma)b \\
a(\pi \jj \sigma)b &\iff& \exists \mathrm{\ postupnosť\ } a=u_1,u_2,\dots,u_t=b \mathrm{\ taká,\ že} \\
 & & \mathrm{pre\ každé\ } i\ \exists \tau \in \{\pi, \sigma\}: u_i(\tau)u_{i+1} \\
\end{eqnarray*}
Napr. pre $n=11$:
\begin{eqnarray*}
\pi &=&\left\{ \{1,2\}, \{3,4,5\}, \{6,7,8\}, \{9,10,11\} \right\}, \\
\sigma &=& \left\{ \{1,3,4\}, \{2,5\}, \{6,7,11\}, \{8\}, \{9,10\} \right\}. \\
\end{eqnarray*}
Potom
\begin{eqnarray*}
\pi \mm \sigma &=&\left\{ \{1\},\{2\},\{3,4\},\{5\},\{6,7\},\{8\}, \{9,10\},\{11\} \right\}, \\
\pi \jj \sigma &=& \left\{ \{1,2,3,4,5\}, \{6,7,8,9,10,11\} \right\}. \\
\end{eqnarray*}
Tieto zväzy sú v kombinatorike aj v teórii zväzov veľmi dôležité. Dlhé roky bol otvorený problém
štruktúry podzväzov  zväzu $\mathcal D(n)$. Whitman (1946) vyslovil hypotézu, že každý zväz možno
vložiť ako podzväz nejakého zväzu $\mathcal D(n)$. Túto hypotézu dokázali P. Pudlák a J. Tůma
(1977).
%%% obrazok zo strany 8 -- zvaz D(3)
\begin{figure}
\caption{$\mathcal D(3)$}
\end{figure}
S týmto zväzom sa čoskoro stretneme.

\item Usporiadaným analógom multimnožiny je \emph{multireťazec}. Ak $f:N \to R$ je zobrazenie, kde
$N$ je reťazec, povedzme $N=\{1,2, \dots,m, \dots\}$, $R$ je usporiadaná množina a $f$ je izotónne,
tak $f(N)$ je reťazec v $R$, presnejšie \emph{multireťazec}, ak zoberieme do úvahy aj usporiadanie v
$R$. Budú nás zaujímať konečné multireťazce $a=a_1a_2\dots a_k$, pričom sa dohodneme, že členy
budeme zapisovať v nerastúcom poriadku, teda $a_1 \ge a_2 \ge \dots \ge a_k$. Kvôli porovnávaniu
multireťazcovje vhodné zaviesť nový prvok do množiny $\widehat R = R \cup \{0\}$, s tým, že $0<b$ pre
každé $b \in R$. Multireťazec $a_1a_2\dots a_k$ potom môžeme reprezentovať nekonečným
vektorom $(a_1, a_2, \dots, a_{k+1}, \dots)$, kde $a_{k+1} = a_{k+2} = \dots = 0$.

Máme nasledujúce tvrdenie:
%% original strana 9
\begin{tvrdenie}
Množina všetkých konečných multireťazcov čiastočne usporiadanej množiny $R$ je usporiadaná reláciou
usporiadania po súradniciach ($a \le b \iff a_i \le b_i,\ i \in \N$). Ak je $R$ zväz (špeciálne, ak
je $R$ reťazec), tak táto usporiadaná množina tvorí zväz, ktorý je podzväzom súčinu
$\prod_{i=1}^{\infty} R_i$, kde $R_i=\widehat R$ pre každé $i$.
\end{tvrdenie}
\begin{proof}
Stačí overiť, že priesek a spojenie monotónne klesajúcich slov je tiež také slovo.
\end{proof}

Osobitne sú zaujímavé špeciálne prípady tvrdenia 6. Nech $R = \N$ a teda $\widehat R = \N_0$. Potom
vzniknutý zväz sa nazýva \emph{Youngovým} zväzom a označuje sa $\mathcal Y$. Jeho prvky sú nerastúce
reťazce prirodzených čísel, kde od istého miesta sú samé nuly. 

Je tu ešte jedna dôležitá interpretácia. Nech $n=n_1+n_2+\dots+n_k$ je partícia čísla $n$ na $k$
neusporiadaných kladných čísel, \emph{$k$-partícia}. Kedže sú neusporiadané, môžeme prepokladať, že
$n_1 \ge n_2 \ge \dots \ge n_k$. Potom $$ (n_1, n_2, \dots, n_k, 0, \dots) \leftrightarrow
n_1+n_2+\dots+n_k$$ definuje izomorfizmus Youngovho zväzu so zväzom všetkých neusporiadaných
partícií. Nulou tohto zväzu je prázdne slovo $0$.

%%%
\begin{figure}
\caption{Youngov zväz}
\end{figure}

\item Partície čísla $n$. Uvažujem zväz $\mathcal D(n)$ rozkladov $n$-prvkovej množiny
$\{1,2,\dots,n\}$. Potom každému rozkladu $\pi = A_1 \uplus A_2 \uplus \dots \uplus A_k$ prislúcha
partícia $z(\pi)$ čísla $n$: $z(\pi) = n_1+n_2+\dots+n_k$, kde $n_i=|A_i|$ pre $i=1,2,\dots,k$.
Relácia usporiadania na $\mathcal D(n)$ daná zjemnením rozkladu indukuje usporiadanie na množine
$\mathcal N(n)$ neusporiadaných partícií čísla $n$:
\begin{multline*}
\sum n_i \le \sum m_j \iff
\text{existujú\ } \pi, \sigma \in \mathcal D(n)\\ \text{také,\ že}\ \pi \le \sigma\ \text{a}
z(\pi)=\sum n_i \ \text{a} \ z(\sigma)=\sum m_j.
\end{multline*}
Dá sa nahliadnuť, že toto naozaj definuje reláciu usporiadania na $\mathcal N(n)$ a toto usporiadanie
je ekvivalentné s nasledujúcim:
\begin{multline*}
\sum_{i=1}^k n_i \lessdot \sum_{j=1}^{l} m_j \iff l=k-1 \ \text{a\ všetky}\ m_j\ \text{sú\ totožné\ s}\ n_i \\
\text{okrem\ jednej\ dvojice} \mathbf{\ ďalej\ nečitateľné}.
\end{multline*}

\begin{figure}
\caption{Diagram zväzu $\mathcal N(7)$ partícií čísla 7}
\end{figure}

Zobrazenie $z: \mathcal D(n) \to \mathcal N(n)$ je morfizmus usporiadaných množín.
Je aj morfizmus zväzov? (Nie, v príklade č. 4 vyššie $z(\pi) \gtrdot z(\sigma)$, takže
$z(\pi) \mm z(\sigma)=z(\sigma) > z(\pi \mm \sigma)$.) Vo všeobecnosti platí:

\begin{tvrdenie}
Nech $(P; \mm, \jj)$ a $(Q; \mm, \jj)$ sú zväzy. Potom každý homomorfizmus zväzov je aj
morfizmus usporiadania. Obrátene to neplatí. Platí však, že každý izomorfizmus
usporiadania je izomorfizmus. \qed
\end{tvrdenie}

\begin{priklad}
\begin{figure}[h]
\end{figure}
Zrejme $\varphi$ je morfizmus usporiadania, ale $\varphi(a \jj b) = 1 \neq m = a^{\prime}
\jj b^{\prime} = \varphi(a) \jj \varphi(b)$. $\varphi$ nie je ani $\jj$-homorfizmom ani
$\mm$-homorfizmom.
\end{priklad}

Na záver tejto časti dokážeme zaujímavé tvrdenie o úplných zväzoch.
%% original strana 11
\begin{teorema}[Knaster--Tarského o pevnom bode]
Nech $(P, \le)$ je úplný zväz a $\varphi: P \to P$ je izotónne zobrazenie. Potom $\varphi$
má pevný bod, t.j. existuje $x \in P$ také, že $\varphi(x)=x$.
\end{teorema}

\begin{proof}
Nech $M=\{x \in P; x\le \varphi(x)\}$. Zrejme $M\neq\emptyset$, lebo $0 \le \varphi(0)$. Nech
$c=\sup M$. Keďže pre každé $x \in M$ platí $x \le c$, z izotónnsoti vyplýva $x \le
\varphi(x) \le \varphi(c)$. Odtiaľ $c=\sup M \le \varphi(c)$. Teda 
$$c \le \varphi(c).$$
Aplikovanín $\varphi$ dostávame $\varphi(c) \le \varphi(\varphi(c))$, z čoho vyplýva, že
$\varphi(c) \in M$. No potom $\varphi(c) \le \sup M = c$, čiže
$$\varphi(c) \le c.$$
Z týchto nerovností máme $\varphi(c)=c$. 
\end{proof}

\begin{priklad}
Cantor-Bernsteinova teoréma: Nech $A,B$ sú množiny. Ak existujú injekcia $\varphi:A \to B$
a injekcia $\psi: B \to A$, tak exituje bijekcia $A \to B$. Idea dokôzu: Nech $X
\subseteq A$. Skonštujme postupne $$X \mapsto \varphi(X) \mapsto B-\varphi(X) \mapsto
\psi(B-\varphi(X)) \mapsto A-\psi(B-\varphi(X)).$$ Uvažujme zobrazenie $\Psi:
\potential(A) \to \potential(A)$, $$X \mapsto A-\psi(B-\varphi(X)).$$
Ľahko sa overí (s použitím známych inklúzií), že $\Psi$ je izotónne. Keďže
$\potential(A)$ je uplný zväz, $\Psi$ má pevný bod -- nejakú $C \subseteq A$. Pomocou
tejto množiny sa už ľahko nadefinuje bijekcia.
\end{priklad}

\end{enumerate}

\section{Distributívne zväzy}

Na úvod pripomenieme nasledovné tvrdenie.

\begin{tvrdenie}
Nech $(P, \le)$ je ľubovoľný zväz. Potom sú pravdivé tieto tvrdenia:
\begin{enumerate}
\item (izotónnosť $\jj$) $x\le y \then x\jj z \le y \jj z$ \newline
(izotónnosť $\mm$) $x\le y \then x \mm z \le y \mm z$ 
\item (všeobecná izotónnosť) $x \le z \amp z \le t \then x \mm z \le y \mm t$, podobne pre $\jj$
\item (distributívne nerovnosti) \newline $x \jj (y \mm z) \le (x\jj y) \mm (x \jj z)$
\newline $x \mm (y \jj z) \ge (x\mm y) \jj (x \mm z)$
\item (modulárna nerovnosť) $x \le z \then x\jj(y\mm z) \le (x\jj y)\mm z$
\end{enumerate}
\end{tvrdenie}

%% original strana 12

\begin{proof}
\begin{enumerate}

\item Izotónnosť $\mm$: Ak $x\le y$ a $z \in P$, tak $x\mm z\le x \le y$ a zároveň $x \mm
z \le z$. Teda $x\mm z$ je dolným ohraničením pre $\{y,z\}$. Odtiaľ $x\mm z \le y \mm z$.
Izotónnosť $\jj$ sa dokáže podobne.

\item Všeobecná izotónnosť sa dokáže dvojnásobným použitím 1.

\item Distributívnosť $\jj$: Zrejme $y \mm z$, takže z izotónnosti pre $\jj$ dostávame
$x\jj(y\mm z) \le x \jj z$. Analogicky $y \mm z \le z$, takže $x \jj (y \mm z) \le x \jj
z$. Teda $x \jj (y \mm z)$ je spoločným dolným ohraničením pre $\{x\jj y, x\jj z\}$,
odkiaľ $x \jj (y \mm z) \le (x \jj y) \mm (x \jj z)$. Distributívnosť $\mm$ podobne.

\item Modulárna nerovnosť: Z distributívnej nerovnosti a predpokladu $x \le z$ máme $x \jj (y \mm z) \le (x\jj y)
\mm (x \jj z) = (x\jj z) \mm z$.
\end{enumerate}
\end{proof}

Zväz sa nazýva \emph{distributívny}, ak v ňom namiesto distributívnych nerovností platí
rovnosť, teda ak pre každé $x,y,z$:
\begin{eqnarray*}
x \jj (y \mm z) &=& (x \jj y) \mm (x \jj z), \\
x \mm (y \jj z) &=& (x \mm y) \jj (x \mm z). \\
\end{eqnarray*}

Zväz sa nazýva \emph{modulárny} (Dedekindov), ak v ňom namiesto modulárnej nerovnosti
platí rovnosť, t.j. ak pre $x \le z$ platí $x\jj(y\mm z) = (x\jj y)\mm z$. Modulárnymi
zväzmi sa budeme zaoberať neskôr, teraz len distributívnymi.

Každá z distributívnych nerovností implikuje druhú. (Ak platí prvá, počítajme z pravej
strany druhú: $\underbrace{(x\mm y)}{t} \jj (x \mm z) = t \jj (x \mm z)$, použijeme druhú
rovnosť, využijeme bežné identity a máme.)

Naviac platia aj (konečné !) zovšeobecnené rovnosti
\begin{eqnarray*}
\left(\MM_i x_i\right) \jj \left(\MM_j y_j\right) &=& \MM_{i,j}(x_i \jj y_j), \\
\left(\JJ_i x_i\right) \mm \left(\JJ_j y_j\right) &=& \JJ_{i,j}(x_i \mm y_j). \\
\end{eqnarray*}
Keďže definujúce rovnosti sú navzájom duálne, tak duál distributívneho zväzu je distributívny.

\begin{priklad}[Príklady]
\begin{enumerate}
\item Zväzy rádu $\le 4$ sú  všetky distrinutívne. Medzi 5-prvkovými (je ich 5) sú dva
nedistributívne, jeden dokonca nemodulárny:
\begin{figure}[h]
%% obrazok zo strany 12
\end{figure}
\item $\{0,1\}^n = \potential(X)$ je distributívny.
\item Každý reťazec je distributívny zväz.
%% oroginal strana 13
\item Súčin distributívnych zväzov je distributívny (aj nekonečný súčin funguje).
\item Podzväz distributívneho zväzu je distributívny zväz. Vyplýva to z toho, že operácie
$\mm, \jj$ sú totožné s operácia v celom zväze.
\item Z ??? vyplýva, že Youngov zväz všetkých partícií (ako podzväz súčinu $\prod^\infty
\N_0$) a zväz $(\N, \nsd, \nsn)=\mathcal T$ (ako podzväz $\prod^\infty \N_0$) sú
distributívne.
\item Zväz ??? grupy $S_3$ permutácií 2-prvkovej množiny nie je distributívny.
\end{enumerate}
\end{priklad}

Prvok $p$ (?distributívneho) zväzu $L$ sa nazýva \emph{ireducibilný} (presnejšie \emph{$\jj$-ireducibilný}), ak pre
ľubovoľné $x,y \in L$ zo vzťahu $p=x\jj y$ vyplýva $p=x$ alebo $p=y$. Výraz $a=p_1 \jj p_2
\jj \dots \jj p_k$, v ktorom všetky $p_i$ sú ireducibilné sa nazýva \emph{rozkladom} prvku
$a$ na ireducibilné prvky. Rozklad je \emph{neskrátiteľný} (\emph{iredundantný}), ak $a
\neq p_1 \jj p_2 \jj \dots p_{i-1} \jj p_{i+1}\jj \dots \jj p_k$, pre každé $i$.
(Atómy a $0$ sú zjavne ireducibilné prvky.)

Je zrejmé, že v ľubovoľnom rozklade sú vštetky prvky neporovnateľné, teda tvoria
antireťazec. Našim cieľom je ukázať, že štruktúra zväzu je jednoznačne určená množinou
jeho ireducibilných prvkov.

\begin{lema}
Nech $p$ je ireducibilný prvok distribitívneho zväzu. Potom z nerovnosti $p \le a_1 \jj
\dots \jj a_k$ vyplýva, že existuje $i$ také, že $p \le a_i$.
\end{lema}

\begin{proof}
Nech $p \le \JJ_i a_i$. Potom $p=p\mm(\JJ_i a_i) = \JJ_i p \mm a_i$. Z ireducibility prvku
$p$ teraz vyplýva, že existuje $i$ také, že $p=p \mm a_i$, čiže $p \le a_i$.
\end{proof}

Prijmime teraz všeobecný a trvalý predpoklad o tom, že sa budeme zaoberať len
usporiadanými množinami spĺňajúcimi podmienku: 
\begin{center}
(F) \emph{Medzi ľubovoľnými dvoma prvkami je každý reťazec konečný.} 
\end{center}
(Všetky množiny kombinatorického pôvodu túto podmienku splňajú.)

Z tohto predpokladu nám hneď vyplýva, že element zväzu s $0$ má rozklad na ireducibilné
prvky, a teda aj iredudantný rozklad. Ak $\{p_1, p_2, \dots \}$ je nejaká množina atómov,
tak $p_1 < p_1 \jj p_2 < p_1 \jj p_2 \jj p_3$ tvoria rast[cu postupnosť -- to vyplýva z
faktu, že atómy sú ireducibilné z lemy. Ak toto aplikujeme na atómy intervalu dostávame,
že interval má konečný počet atómov, a teda, indukciou, je aj sám konečný.

%% original strana 14
\begin{teorema} Nech $L$ je  distributívny zväz (spĺňajúci podmienku (F)) a nech $P
\subseteq L$ množina jeho nenulových ireducibilných prvkov. Potom každý prvok $a$ má
jednoznačný iredundantný rozklad $a=p_1 \jj p_2 \jj \dots \jj p_k$ na ireducibilné prvky,
čo zapisujeme $P(a)=\{p_1, p_2, \dots, p_k\}$, pričom $P(0) = \emptyset$.
\end{teorema}

\begin{proof}
Existencia rozkladu je zrejmá (existuje $0$ a platí (F), čo zabezpečuje, že množina
všetkých ireducibilných prvkov $\neq 0$ pod $a \in L$; potom treba zobrať všetky také).
Jednoznačnosť: Nech $$a=p_1 \jj p_2 \jj \dots \jj p_k = q_1 \jj q_2 \jj \dots \jj q_\ell$$
sú dva jednoznačné rozklady. Pre každé $p_i$ máme $p_i \le q_1 \jj q_2 \jj \dots \jj
q_\ell$, odtiaľ $p_i \le q_j$ pre nejaké $j$. Keďže ireducibilné prvky sú neporovnateľné,
dostávame $p_i=q_j$. Zopakovaním tejto úvahy potrebný počet krát dostávame, že $k \le
\ell$ a analogicky aj $\ell \le k$. Teda $\ell = k$ a možiny $\{p_1, p_2, \dots, p_k\}$ a
$\{q_1, q_2, \dots, q_\ell\}$ sú totožné.
\end{proof}

Podmožina $I$ usporiadanej množiny $P$ je \emph{ideál}, ak pre $\forall x,y: x\in I \amp y
\le x \then y \in I$. \emph{Hlavný ideál} je ideál tvaru $\{x \in P; x\le a\}$, (a môže byť
aj mimo množiny $P$, z nejakej nadmnožiny).

Zjednotenie aj prienik ideálov sú ideály. Teda systém $\mathcal I(P)$ všetkých ideálov
množiny $P$ tvorí podzväz zväzu $\potential(P)$. Teda $\mathcal I(P)$ je distrinutívny
zväz. V ňom $0$ a hlavné ideály sú očividne iredicibilné prvky. Iný dôležitý podzväz je
zväz konečných hlavných ideálov $\mathcal I_f(P)$. Teraz ukážeme, že každý distributívny
zväz spĺňajúci podmienku (F) je tohto tvaru.

\begin{teorema}
Nech $L$ je distributívny zväz s $0$ (spĺňajúci (F)) a nech $P$ je množina všetkých jeho
iredibilných prvkov $\neq 0$. Potom $L \cong \mathcal I_f(P)$ a izomorfizmus je daný
vzťahom $\varphi: a \mapsto I(a) = \{x \in P; x \le a\}$, $a \in L$. Obrátene zväz
$\mathcal I_f(P)$ je distributívny a množina jeho ireducibilných prvkov je izomorfná s $P$.
Ak $L$ je konečný, tak $L \cong I(P)$.
\end{teorema}

\begin{proof}
Keďže každý prvok zväzu $L$ je určený ireducibilnými prvkami, ktoré majorizuje, zobrazenie
$\varphi: L \to \mathcal I_f(P)$ je injektívne. Na dôkaz surjektívnosti stačí ukázať, že
každý konečný ideál je hlavný. Nech $I = \{p_1, p_2, \dots, p_r$. Nech $b=p_1 \jj p_2 \jj
\dots, p_r$. Potom $b \in L$. Uvažujme hlavný ideál $I(b)$. Zrejme $I \subseteq I(b)$.

%% original strana 15
Obrátene, nech $p \in I(B)$. Je to ireducibilný prvok a $p \le b = p_1 \jj p_2 \jj \dots
\jj p_r$. Z lemy vyplýva, že $p=p_i \in I$. Teda $I(B) \subseteq I$, čiže $I=I(b)$. Teda
každý ideál je hlavný, odkiaľ vyplýva, že $\varphi$ je bijekcia.

Ak $a\le b$, $a,b \in L$, tak $I(a) \subseteq I(B)$. Obrátene $I(a) \subseteq I(b)$
implikuje $a=\sup I(a) \le \sup I(b) = b$ (???) izomorfizmus a teda izomorfizmus zväzov.
\end{proof}

\begin{lema}[Dôsledok]
Dva distributívne zväzy sú izomorfné, ak sú izomorfné usporiadané množiny ich ireducibilných prvkov.
\end{lema}

\begin{priklad}[Poznámka:]
Analogickú konštrukciu možno urobiť pomocou $\mm$-ireducibilných prvkov a duálneho pojmu
filtra. Keďže výsledky musia byť izomorfné, dostávame, že usporiadaná množina
$\mm$-ireducibilných prvkov musí byť v distributívnom zväze izomorfná s usporiadanou
množinou $\jj$-ireducibilných prvkov. 
\end{priklad}

V teoréme 11 sme zistili, že distributívny zväz $L$ s $0$ je izomorfný s $\mathcal
I_f(P)$, kde $P$ je množina jeho ireducibilných prvkov. Keďže usporiadanie v $\mathcal
I_f(P)$ je obyčajná inklúzia, dostávame, že každý distributívny zväz (s podmienkou (F),
ako obyčajne) je izomorfný s podzväzom booleovského podzväzu $\potential(X)$. Keďže
$\potential(X)$ je súčin reťazcov, dokázali sme

\begin{teorema}
Každý distributívny zväz s $0$ je izomorfný s nejakým podzväzom booleovksého zväzu
$\potential(X)$, a teda aj s podzväzom súčinu reťazcov. Obrátene, každý podzväz súčinu
reťazcov je distributívny. \qed
\end{teorema}

Charakterizačná teoréma 12, kladie takúto prirodzenú otázku:
Koľko je pre daný distributívny zväz $L$ nevyhnutné zobrať reťazcov $C_i$ na to, aby $L$
bol podzväzom súčinu $\prod_i C_i$?

Budeme predpokladať, že $C_i = \{0 < 1 < \dots < c_i\}$. Vnorenie $L \to \prod_{i=1}^d
C_i$ nazývame \emph{kódovaním zväzu}, číslo $d$ dimenziou zväzu.
Booleovský zväz $\potential(X)$ má kódovanie $\potential(X) \to \{0,1\}^X$ v súčine $|X|$
reťazcov. Je možné tento počet znížiť za cenu predĺženie reťazcov? Z nasledujúcej teorémy
vyplynie, že v tomto prípade nie.

%% original strana 16
\begin{teorema}
Nech $L$ je distributívny zväz s $0$ a nech $P$ je usporiadaná množina jeho nenulových
ireducibilných prvkov. Nech $P = \biguplus_i P_i$ je ľubovoľný rozklad usporiadanej
množiny $P$ na reťazce. Položme $C_i=\{0\} \cup P_i$, pre všetky $i$. Potom existuje
izomorfizmus $\varphi: L \to \prod_i C_i$ na podzväz zväzu $\prod_i C_i$.
\end{teorema}

\begin{proof}
Pre ľubovoľné $x \in L$ a index $i$ položme $$x_i = \sup \{z \in C_i; z \le x\}.$$

Na množine indexov zavedieme úplné usporiadanie a položíme
\begin{eqnarray*}
\varphi: L &\to& \prod_i C_i, \\
x &\mapsto& (x_i)_i.
\end{eqnarray*}
(Poznamenávame, že pre skoro všetky indexy (okrem konečného počtu) je $x_i=0$. To vyplýva z
podiemky (F), ktorá implikuje, že interval distributívneho zväzu má iba konečne veľa
atómov a teda je konečný.)

Zobrazenie $\varphi$ je injektívne, lebo keby $\varphi(x) = \varphi(y)$, tak $x_i=y_i$ pre
všetky $i$, a teda $I(x)=I(y)$, odkiaľ $x=y$.

Okrem toho, podľa lemy o ireducibilných prvkoch máme $(x\jj y)_i = \sup\{z \in C_i; z \le
x\jj y\} = \sup \{z \in C_i; z \le x\ \mathrm{alebo}\ z\le y  \} = x_i \jj y_i$. Podobne
$\mm$.
\end{proof}

Keďže podľa teorémy 13, každý rozklad množiny $P$ indukuje kódovanie, problém dimenzie
usporiadanej množiny sa redukuje na čisto kombinatorickú úlohu nájsť pre ľubovoľnú
usporiadanú množinu $P$ rozklad na minimálny počet $d(P)$ reťazcov. Číslo $d(P)$ sa nazýva
Dilworthovým číslom usporiadanej množiny. Je zrejmé, že
$$d(P) \ge \min_{A\ \mathrm{je\ antireťazec}} |A|.$$
V skutočnosti platí rovnosť -- to je jeden z fundamentálnych výsledkov kombinatoriky.

\begin{priklad}
$d(\potential(\{1,2,\dots,n\}))=n$, s využitím vyššie uvedenej nerovnosti.
\end{priklad}

%% original strana 17
\begin{teorema}[Dilworth, 1950]
Nech $P$ je konečná usporiadaná množina. Potom minimálny počet reťazcov, ktorých
zjednotením je $P$ sa rovná maximálnej mohutnosti antireťazca v $P$.
\end{teorema}

\begin{proof}
Ostáva nám dokázať, že ak v $P$ existuje antireťazec mohutnosti $n$, tak $P$ sa dá pokryť
$n$ reťazcacmi. Maximálnu mohutnosť antireťazca nazveme \emph{šírkou} usporiadanej
množiny $P$. 

Budeme postupovaťindukciou vzhľadom na $|P|$. Ak $|P|=1$, tak výsledok je triviálny.
Predpokladajme, že trvdenie platí pre $|P|<k$ a uvažujme množinu $|P|=k$. Môžeme
predpokldať, že šírka $n$ množiny $P$ je $>1$.

Zvoľme nejaký maximálny prvok $x \in P$ a k nemu zoberme minimálny prvok $y$ taký, že $y
\le x$. (Kedže $P$ je konečná, toto sa vždy dá.) Nech $Q = P - \{x,y\}$ s indukovaným
usporiadaním. Ak šírka množiny $Q$ je menšia ako $n$, tak podľa indukčného predpokladu sa
$Q$ dá rozložiť na menej ako $n$ reťazcov, čo spolu s reťazcom $\{x,y\}$ vytvára rozklad
na (nanajvýš) $n$ reťazcov.  Takže môžeme prepokladať, že $Q$ má šírku $n$.  Odtiaľ
vyplýva, že $y<x$.

V tejto situácii si vyberieme antireťazec $A = \{a_1,a_2,\dots,a_n\}$. Nech $H = \{z \in
P; \exists i: z \ge a_i \}$ (horná množina) a nech $D= \{z \in P; \exists i: z \le a_i\}$.
Potom $H \cup D = P$ (inak by existoval širší antireťazec), $D \cap D = A$ (očividné) a
keďže odtránením $\{x,y\}$ z $P$ sa šírka nezúžila, máme $x \in H - D$, zatiaľ čo $y \in
D-H$. Podľa indučného predpokladu existujú rozklady na $H=C_1^{\prime} \cup C_2^{\prime}
\dots \cup C_n^{\prime}$ a 
$D = C_1^{\prime\prime} \cup C_2^{\prime\prime} \dots \cup C_n^{\prime\prime}$.
Rozklady možeme očíslovať tak, že $a_i \in C_i{\prime} \cap C_i^{\prime\prime}$ pre
$i=1,2, \dots, n$. Potom $C_i = C_i{\prime} \cup C_i^{\prime\prime}$ je reťazec a
požadovaný rozklad je $P = C_1 \cup C_2 \cup \dots \cup C_n$.
\end{proof}

\begin{dosledok}
Ak $L$ je konečný distributívny zväz a $P$ je jeho množina nenulových ireducibilných
prvkov, tak $\dim(L) = d(P)$.
\end{dosledok}

Teraz prejdeme k ďalšiemu aspektu distributívnosti -- k poriadkovej (rangovej) funkcii.
Poriadková (rangová) funckia na zväze $L$ je funkcia $r: X \to \N_0$ spĺňajúca podmienky
\begin{enumerate}
\item $r(0)=0$,
\item ak $a \lessdot b$, tak $r(b)=r(a)+1$.
\end{enumerate}

\section{Modulárne a polomodulárne zväzy}






%%%%%%%%%

\chapter{Matroidy}
\section{Matroidové algoritmy}

\chapter{Kombinatorické konfigurácie}
\section{Konfigurácie}
\section{Zapĺňanie priehradok a urnové schémy}
\section{Latinské štvorce}
\section{Ortogonalita latinských štvorcov}

\section{$(v,k,\lambda)$-konfigurácie}
Daná je množina $X=\{x_1, x_2, \dots, x_v\}$. Systém $X_1,X_2,\dots,X_v$ jej podmonožín
množiny $X$ tvorí $(v,k,\lambda)$-konfiguráciu, ak
\begin{enumerate}
\item $|X_i|=k$ pre všetky $i$,
\item $|X_i \cap X_j|=\lambda$ pre všetky $i\neq j$,
\item $0 < \lambda < k < v-1.$
\end{enumerate}

Množiny $X_i$ sa nazývajú \emph{bloky}. Matica incidencie $(v,k,\lambda)$-konfigurácie je $0,1$-matica definovaná nasledovne
\begin{eqnarray*}
A &=& (a_{ij}), \quad i,j = 1,2,\dots,v, \\
a_{ij} &=&
\begin{cases}
 1 & x_j \in X_i, \\
 0 & \text{inak.} \\
\end{cases} \\
\end{eqnarray*}

Označme $I$ jednotkovú maticu rádu $v$, $J$ maticu pozostávajúcu zo samých jednotiek.
\begin{enumerate}
\item Pretože $|X_i|=k$ je $\sum_{j=1}^v a_{ij} = k$, odtiaľ
$$AJ=kJ.$$

\item Keďže 
$$c_{ij} = \sum_{q=1}^v a_{iq} a_{jq} = |X_i \cap X_j| = 
\begin{cases}
k & i=j \\
\lambda & i \neq j \\
\end{cases}
,$$

$$
AA^T = 
\begin{pmatrix}
k 	& \lambda 	& \dots 	& \lambda 	\\
\lambda & k 		& \dots 	& \lambda 	\\
\vdots 	&  		& \ddots  	& \vdots 	\\
\lambda & \lambda 	& \dots 	& k 		\\
\end{pmatrix}
=\lambda J + (k-\lambda)I
$$

%%%%%%%%%%%%%%

\item Matica $A$ je regulárna, lebo 

\begin{equation*}
\begin{split}
\det(AA^T) &= \det(A)^2 \\
&= \begin{vmatrix}
k 	& \lambda 	& \dots 	& \lambda 	\\
\lambda & k 		& \dots 	& \lambda 	\\
\vdots 	&  		& \ddots  	& \vdots 	\\
\lambda & \lambda 	& \dots 	& k 		\\
\end{vmatrix}\\
&=
\begin{vmatrix}
k 	& \lambda-k 	& \lambda-k	& \dots 	& \lambda-k 	\\
\lambda & k-\lambda	& 0		& \dots 	& 0 	\\
\vdots 	& 0 		& k-\lambda	& \ddots  	& \vdots 	\\
\lambda	& \vdots	& \ddots	& \ddots  	& 0 	\\
\lambda & 0 		& \dots		& 0 		& k-\lambda 	\\
\end{vmatrix}\\
&= 
\begin{vmatrix}
\lambda(v-1)+k 	& 0 		& \dots 	& 0 		& 0 		\\
\lambda 	& k-\lambda 	& \ddots 	& \vdots 	& 0		\\
\vdots		& 0		& \ddots	& 0		& \vdots	\\
\lambda 	& \vdots 	& \ddots 	& k-\lambda 	& 0 		\\
\lambda		& 0 		& \dots  	& 0 		& k-\lambda 	\\
\end{vmatrix}\\
&=[k+\lambda(v-1)](k-\lambda)^{v-1}
\end{split}
\end{equation*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Pre každú $(v,k,\lambda)$-konfiguráciu platí
$$k(k-1) = \lambda(v-1).$$

Vychádzame z rovnosti 
$$AA^T = \lambda J + (k-\lambda)I,$$ potom 
$$AA^TJ = \lambda J^2 + (k-\lambda)J = \lambda v J + (k-\lambda) J = (k+\lambda(v-1))J.$$
Pretože $0<\lambda<k$ je matica $A$ podľa predchádzajúcej vlastnosti regulárna a platí
$$A^{-1}J=\frac{1}{k}J.$$
Z toho dostávame
$$A^TJ = (k+\lambda(v-1))A^{-1}J = \frac{k+\lambda(v-1)}{k}J,$$
trasponovaním
\begin{eqnarray*}
(A^TJ)^T 	&=& \frac{k+\lambda(v-1)}{k}J^T, \\
JA 		&=& \frac{k+\lambda(v-1)}{k}J, \\
JAJ 		&=& \frac{v}{k}(k+\lambda(v-1))J. \\
\end{eqnarray*}

Vieme, že $AJ=kJ$, čiže $JAJ=kJ^2=vkJ$, porovnaním dostaneme
\begin{eqnarray*}
vkJ 		&=& \frac{v}{k}(k+\lambda(v-1))J, \\
k 		&=& \frac{k+\lambda(v-1)}{k}, \\
k^2-k 		&=& (\lambda(v-1)), \\
k(k-1) 		&=& (\lambda(v-1)). \\
\end{eqnarray*}


\end{enumerate}

\section{Uplné diferenčné množiny}

\section{Hadamardove matice a konfigurácie}
Štvorcová matica $H$ rádu $n$ sa nazýva \emph{Hadamardova}, ak
\begin{enumerate}
\item $a_{ij}=\pm 1$
\item $HH^T=nI$ ($I$ je jednotková matica)
\end{enumerate}

Jednoduché dôsledky definície: Ak $H_i, H_j$ sú riadkové vektory Hadamardovej matice, tak
pre ich skalárny súčin platí:
$$
(H_i,H_j) = 
\begin{cases}
n & i=j, \\
0 & i \neq j. \\
\end{cases}
$$
Čiže riadky sú na seba kolmé. Každá Hadamardova matica je regulárna, lebo
$\det(H)^2=\det(HH^T)=n^n$. Navyše Hadarmadove matice sú zrejme normálne, 
lebo $$H^TH = H^{-1}HH^TH = H^{-1}nIH=nIH^{-1}H=nI=HH^T.$$

Ak $H$ je Hadamardova, tak aj $(-1)H$ je Hadamardova. Preusporiadním riadkov 
a stĺpcov dostaneme opäť Hadamardovu maticu. Rovnako môžeme vynásobiť riadok alebo stĺpec
$(-1)$. Naozaj, je zrejmé, že vlastnosť 
$$
(H_i,H_j) = 
\begin{cases}
n & i=j, \\
0 & i \neq j, \\
\end{cases}
$$ 
je ekvivalentná podmienke 
$$\sum_{k=0}^n h_{ik}h_{jk}
\begin{cases}
n & i=j, \\
0 & i \neq j. \\
\end{cases}
$$
A táto rovnosť je invariantná voči uvedeným operáciám. Preto možno každú Hadamardovu
maticu uviesť do tvaru, v ktorom prvý riadok a prvý stĺpec obsahujú kladné jednotky
(normalizované).

\begin{veta}
Ak $n$ je rád Hadamardovej matice, tak $n=1,2$ alebo $n \equiv 0 \pmod 4$.
\end{veta}

\begin{proof}
Pre $n=1,2$ majú normalizované Hadamardove matice tvar:
$$
\begin{pmatrix} 1 \end{pmatrix} \qquad
\begin{pmatrix} 1&1 \\ 1 & -1 \\ \end{pmatrix}
$$

Nech je daná Hadamardova matica rádu $n \ge 3$, prepokladajmu ju normalizovanú. Stĺpce
prvých troch riadkov tejto matice majú jeden z nasledujúcich tvarov
$$
\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \qquad
\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix} \qquad
\begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix} \qquad
\begin{pmatrix} 1 \\ -1 \\ -1 \end{pmatrix}.
$$
Nech počet stĺpcov prvé typu je $x$, druhého $y$, tretieho $z$ a štvrtého $w$. Pretože ich
je spolu $n$, platí $x+y+z+w=n$. Nech v množine $I_j$  sú tie indexy stĺpcov našej matice,
ktorého sú typu $j$ ($j=1,2,3,4$). Teda máme $|I_1|=x, |I_2|=y, |I_3|=z, |I_4|=w$. Pretože
riadky $H_1,H_2$ sú na seba kolmé, máme $h_{11}h_{21} + h_{12}h_{22} + \dots + h_{1n}h_{2n}
= 0$. 

\begin{tabular}{ll}
Ak & $i \in I_1$, tak $h_{1i} \cdot h_{2i}=1 \cdot 1=1$, \\
   & $i \in I_2$, tak $h_{1i} \cdot h_{2i}=1 \cdot 1=1$, \\
   & $i \in I_3$, tak $h_{1i} \cdot h_{2i}=1 \cdot (-1)=-1$,  \\
   & $i \in I_4$, tak $h_{1i} \cdot h_{2i}=1 \cdot (-1)=1$. \\
\end{tabular}
\newline Odtiaľ $0 = (H_1,H_2) = \sum_{i=1}^n h_{1i}h_{2i} = \sum_{j=1}^4 \sum_{i \in I_j}
h_{1i}{2i} = x+y-z-w$. Analogicky z ortogonality $H_1$ a $H_3$ dostávame $x-y+z-w=0$, a ortogonality $H_2$ a
$H_3$ dostávame $x-y-z+w=0$.

Máme teda systém rovníc
\begin{eqnarray*}
x + y + z + w &=& n, \\
x + y - z - w &=& 0, \\
x - y + z - w &=& 0, \\
x - y - z + w &=& 0. \\
\end{eqnarray*}
Vyriešením dostávame $x=y=z=w=n/4$. Keďže $x,y,z,w$ sú celé čísla, je $n \equiv 0
\pmod 4$.
\end{proof}

Kroneckerovým súčinom matíc $A \otimes B$ matíc typu $n \times n$ a $m \times m$ rozumieme
maticu typu $mn \times mn$ typu
$$
\begin{pmatrix}
a_{11}B & a_{12} B & \cdots & a_{1n} B \\
a_{21}B & a_{22} B & \cdots & a_{2n} B \\
\vdots  & \vdots   & \ddots & \vdots \\
a_{n1}B & a_{n2} B & \cdots & a_{nn} B \\
\end{pmatrix}.
$$
Ľahko sa možno presvedčiť, že tatko definovaný súčin má nasledovné tri vlastnosti:
\begin{align*}
(A \otimes B)^T &= A^T \otimes B^T \\
(A+B) \otimes C &= A \otimes C + B \otimes C \\
(AB) \otimes (CD) &= (A \otimes C)(B \otimes D) \\
\end{align*}
Kroneckerov súčin Hadamardových matíc je opäť Hadamarodva matica. Naozaj:
$$
(H \otimes H^\prime)(H \otimes H^\prime)^T  = 
(H \otimes H^\prime)(H^T \otimes H^{\prime T}) =
HH^T \otimes H^\prime H^{\prime T} =
nI_n \otimes mI_m =
mnI_{mn}.
$$

\begin{veta}
Pre $n=2^k$ existuje Hadamardova matica.
\end{veta}
\begin{proof}
Zoberme maticu
$$
H_2 = \begin{pmatrix}1&1\\1&-1\end{pmatrix}
$$
Definujme
$$H_{2^k} = \underbrace{H_2 \otimes H_2 \otimes \dots \otimes H_2}_{k\text{-krát}}.$$
Podľa vyššie popísaných vlastností je to Hadamardova matica rádu $2^k$.
\end{proof}

\begin{veta}
Normalizovaná Hadamardova matica rádu $m = 4 \mu$ je ekvivaletná
$(v,k,\lambda)$-konfigurácii s parametrami
$$
v=4\mu-1,\quad k=2\mu-1,\quad \lambda=\mu-1.
$$
\end{veta}
\begin{proof}
Z normalizovanej Hadamardovej matice vyškrtneme prvý riadok a prvý stĺpec a $-1$ zmeníme
na $0$. Keďže ľubovoľný riadok rôzny od prvého je naň komý, tak platí $\sum_{i=1}^n h_{1i}
h_{ji} = 0 $ ($j>1$), ale $h_{1i}=1$ pre všetky $i$, preto $\sum_{i=1}^n h_ji = 0$, čiže
počet kladných jednotiek sa rovná počtu záporných jednotiek, teda počet kladných
(záporných) jednotiek je $2\mu$.

Pretože pre $i \neq j$, $i,j>1$ sú riadky na seba kolmé a každý má po $2\mu$ kladných
jednotiek, majú na (práve) $\mu$ miestach kladné jednotky v rovnakých stĺpcoch.

Z toho plynie, že v našej $0,1$-matici rádu $4\mu-1$ je súčet riadku rovný $2\mu-1$ a dva
riadky majú $\mu-1$ jednotiek v rovnakých stĺpoch. To svedčí o tom, že naša $0,1$-matica
je maticou incidencie $(v,k\lambda)$-konfigurácie s vyššie udanými parametrami. Táto
konfigurácia na nazýva Hadamardova konfigurácia. V obrátenom postupe možno každej
Hadamardovej konfigurácii priradiť normalizovanú Hadamardovu maticu rádu $4\mu$.
\end{proof}

\section{Konečné projektívne roviny}
Konečnou projektívnou rovinou rádu $n$ sa rozumie $(v,k,\lambda)$-konfigurácia s
parametrami 
$$
v = n^2 + n + 1, \quad
k = n + 1, \quad
\lambda = 1.
$$
Bloky $X_i$, $i=1,2,\dots,n^2+n+1$ sa nazývajú priamkami a prvky blokov bodmi. Vzťah $x_i
\in X_j$ znamená, že bod $x_i$ leží na priamke $X_j$ a vzťah $x_i \in X_j \cap X_k$, že
priamky $X_j, X_k$ sa pretínajú v bode $x_i$.

\begin{priklad}
$(v,k,\lambda)$-konfigurácia určená úplnou diferenčnou množinou ${1,2,4} \subset \Z_7$ je
projektívnou rovinou, ktorú možno nasledovne znázorniť.
\begin{figure}[h]
\begin{center}
\includegraphics{fig.20}
\end{center}
\end{figure}
\end{priklad}

Čo sa týka existencie konečných projektívnych rovín, tak platí veta (dôsledok vety
Buck-Ryser).

\begin{veta}
Na existenciu konečnej projektívnej roviny rádu $n$ je nutné, aby pri $n \equiv 1,2 \pmod
4$ existovali celé čísla $a,b$ spĺňajúce rovnosť $n=a^2+b^2$.
\end{veta}
Z tejto vety vyplýva neexistencia konečných projektívnych rovín rádov napr. $6,14,21,22$.

\section{Ortogonálne latinské štvorce a projektívne roviny}
\section[$(b,v,r,k,\lambda)$-konfigurácie]{Blokové konfigurácie: $(b,v,r,k,\lambda)$-konfigurácie}
\section{Steinerove trojice}

\end{document}