From b3153e4851bca628d92f85a953a0eb433959e021 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Mon, 28 Mar 2022 21:52:44 +0200
Subject: Update, wip ostry

---
 lic_malinka.tex | 66 ++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 46 insertions(+), 20 deletions(-)

(limited to 'lic_malinka.tex')

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} 
-- 
cgit v1.2.3

