From b3153e4851bca628d92f85a953a0eb433959e021 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Mon, 28 Mar 2022 21:52:44 +0200 Subject: Update, wip ostry --- lic_malinka.pdf | Bin 370895 -> 372613 bytes lic_malinka.tex | 66 +++++++++++++++++++++++++++++++++++++++----------------- 2 files changed, 46 insertions(+), 20 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 6f1f6c1..751fe33 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ 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