Update, wip ostry

1 files changed, 46 insertions, 20 deletions

diff --git a/lic_malinka.tex b/lic_malinka.tex
index 6200d4c..a7ead6d 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -58,6 +58,9 @@
 \newcommand{\bQ}{\mathbb Q}

 \newcommand{\bK}{\mathcal K}

 

+\newcommand{\FrAut}{\Pi}

+\newcommand{\FrGr}{\Gamma}

+

 \DeclareMathOperator{\im}{{Im}} 

 \DeclareMathOperator{\id}{{id}} 

 \DeclareMathOperator{\lin}{{Lin}}

@@ -479,7 +482,7 @@
 

   \begin{definition}

     The \emph{random graph} is the Fraïssé limit of the class of finite graphs

-    $\cG$ denoted by $\Gamma = \Flim(\cG)$.

+    $\cG$ denoted by $\FrGr = \Flim(\cG)$.

   \end{definition}

 

   The concept of the random graph emerges independently in many fields of

@@ -488,41 +491,41 @@
   that the graph constructed this way is exactly the random graph we described

   above.

 

-  The random graph $\Gamma$ has one particular property that is unique to the

+  The random graph $\FrGr$ has one particular property that is unique to the

   random graph.

 

   \begin{fact}[random graph property]

-    For each finite disjoint $X, Y\subseteq \Gamma$ there exists $v\in\Gamma$

+    For each finite disjoint $X, Y\subseteq \FrGr$ there exists $v\in\FrGr$

     such that $\forall u\in X (vEu)$ and $\forall u\in Y (\neg vEu)$.

   \end{fact}

   \begin{proof}

-    Take any finite disjoint $X, Y\subseteq\Gamma$. Let $G_{XY}$ be the

-    subgraph of $\Gamma$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$,

+    Take any finite disjoint $X, Y\subseteq\FrGr$. Let $G_{XY}$ be the

+    subgraph of $\FrGr$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$,

     where $w$ is a new vertex that does not appear in $G_{XY}$. Also, $w$ is connected to 

     all verticies of $G_{XY}$ that come from $X$ and to none of those that come

-    from $Y$. This graph is of course finite, so it is embeddable in $\Gamma$.

+    from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$.

     Wihtout loss of generality assume that this embedding is simply inclusion. 

     Let $f$ be the partial isomorphism from $X\sqcup Y$ to $H$, with $X$ and

     $Y$ projected to the part of $H$ that come from $X$ and $Y$ respectively. 

-    By the ultrahomogenity of $\Gamma$ this isomoprhism extends to an automorphism

-    $\sigma\in\Aut(\Gamma)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. 

+    By the ultrahomogenity of $\FrGr$ this isomoprhism extends to an automorphism

+    $\sigma\in\Aut(\FrGr)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. 

   \end{proof}

 

   \begin{fact}

     If a countable graph $G$ has the random graph property, then it is

-    isomorhpic to the random graph $\Gamma$.

+    isomorhpic to the random graph $\FrGr$.

   \end{fact}

   \begin{proof}

-    Enumerate verticies of both graphs: $\Gamma = \{a_1, a_2\ldots\}$ and $G

+    Enumerate verticies of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G

     = \{b_1, b_2\ldots\}$.

-    We will construct a chain of partial isomorphisms $f_n\colon \Gamma\to G$

+    We will construct a chain of partial isomorphisms $f_n\colon \FrGr\to G$

     such that $\emptyset = f_0\subseteq f_1\subseteq f_2\subseteq\ldots$ and $a_n \in

     \dom(f_n)$ and $b_n\in\rng(f_n)$.

 

     Suppose we have $f_n$. We seek $b\in G$ such that $f_n\cup \{\langle

-    a_{n+1}, b\rangle\}$ is a partial isomoprhism. Let $X = \{a\in\Gamma\mid

-    aE_{\Gamma} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are

-    verticies of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\Gamma$ and

+    a_{n+1}, b\rangle\}$ is a partial isomoprhism. Let $X = \{a\in\FrGr\mid

+    aE_{\FrGr} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are

+    verticies of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and

     $Y$ are those verticies that are not connected with $a_{n+1}$. Let $b$ be

     a vertex of $G$ that is connected to all verticies of $f_n[X]$ and to none

     $f_n[Y]$ (it exists by the random graph property). Then $f_n\cup \{\langle

@@ -530,13 +533,13 @@
     $b_{n+1}$ in the similar manner, so that $f_{n+1} = f_n\cup \{\langle

     a_{n+1}, b\rangle, \langle a, b_{n+1}\rangle\}$ is a partial isomorphism.

 

-    $f = \bigcup^{\infty}_{n=0}f_n$ is an isomoprhism between $\Gamma$

-    and $G$. Take any $a, b\in \Gamma$. Then for some big enough $n$ we have

-    that $aE_{\Gamma}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$ .

+    $f = \bigcup^{\infty}_{n=0}f_n$ is an isomoprhism between $\FrGr$

+    and $G$. Take any $a, b\in \FrGr$. Then for some big enough $n$ we have

+    that $aE_{\FrGr}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$ .

   \end{proof}

 

   Using this fact one can show that the graph constructed in the probabilistic

-  manner is in fact isomorphic to the random graph $\Gamma$.

+  manner is in fact isomorphic to the random graph $\FrGr$.

 

   \begin{proposition}

     The class of finite graphs $\cG$ has the weak Hrushovski property. 

@@ -570,12 +573,35 @@
     napisać) We let $\delta_{\upharpoonright X} = \id_X$ for $X\in \{A,

     B\setminus A, C\setminus B\}$. Let's check the definition is correct. In

     order to do that, we have to show that for any $u, v\in

-    D (uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$. We have a few cases:

+    D\quad(uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$. We have two cases:

     \begin{itemize}

-      \item 

+      \item $u, v\in X$, where $X$ is either $B$ or $C$. This case is trivial.

+      \item $u\in B\setminus A, v\in C\setminus A$. Then

+        $\delta(u)=\beta(u)\in B\setminus A$, similarly $\delta(v)=\gamma(v)\in

+        C\setminus A$. This follows from the fact, that $\beta\upharpoonright_A

+        = \alpha$, so for any $w\in A\quad\beta^{-1}(w)=\alpha^{-1}(w)\in A$,

+        similarly for $\FrGr$. Thus, from the construction of $D$, $\neg uE_Dv$

+        and $\neg \delta(u)E_D\delta(v)$.

     \end{itemize}

   \end{proof}

 

+  The proposition says that there is a Fraïssé for the class $\cH$ of finite

+  graphs with automorphisms. We shall call it $(\FrAut, \sigma)$. Not

+  surprisingly, $\FrAut$ is in fact a random graph.

+

+  \begin{proposition}

+    The Fraïssé limit of $\cH$ interpreted as a plain graph is isomorphic to

+    the random graph $\FrGr$.

+  \end{proposition}

+

+  \begin{proof}

+    It is enough to show that $\FrAut = \Flim(\cH)$ has the random graph

+    property. Take any finite disjoint $X, Y\subseteq \FrAut$. Let $G_{XY}$ be

+    the graph induced by $X\cup Y$. Take $H=G_{XY}\sqcup {v}$ as a supergraph

+    of $G_{XY}$ with one new vertex $v$ connected to all verticies of $X$ and

+    to none of $Y$. By the weak homogeneity $H$ embedds to $\FrAut$

+  \end{proof}

+

   \section{Conjugacy classes in automorphism groups}

 

   \subsection{Prototype: pure set}