From 78cbd57aad87cd07d4ebe218d09a8a926b12b2cb Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Sat, 26 Mar 2022 15:18:26 +0100
Subject: Troche o grafie losowym

---
 lic_malinka.tex | 190 ++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 143 insertions(+), 47 deletions(-)

(limited to 'lic_malinka.tex')

diff --git a/lic_malinka.tex b/lic_malinka.tex
index 0dde9cd..d98ecee 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -1,10 +1,12 @@
-\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em}
+\documentclass[11pt, a4paper, final]{amsart} 
+\setlength{\emergencystretch}{2em}
 
 \usepackage[backend=biber]{biblatex}
 \addbibresource{licmalinka.bib}
 
 
-\usepackage[T1]{fontenc} \usepackage{mathtools}
+\usepackage[T1]{fontenc} 
+\usepackage{mathtools}
 \usepackage[activate={true,nocompatibility},final,tracking=true,kerning=true,spacing=true,stretch=10,shrink=10]{microtype}
 \microtypecontext{spacing=nonfrench}
 % \usepackage[utf8]{inputenc}
@@ -23,7 +25,6 @@
 \usetikzlibrary{arrows,arrows.meta}
 \tikzcdset{arrow style=tikz, diagrams={>=latex}}
 
-
 \usepackage{etoolbox}
 
 \usepackage{xcolor} 
@@ -40,13 +41,16 @@
 \DeclareMathOperator{\Hom}{Hom}
 \DeclareMathOperator{\Stab}{Stab} 
 \DeclareMathOperator{\st}{st}
-\DeclareMathOperator{\Flim}{FLim} 
+\DeclareMathOperator{\Flim}{Flim} 
 \DeclareMathOperator{\Int}{{Int}}
+\DeclareMathOperator{\rng}{{rng}}
+\DeclareMathOperator{\dom}{{dom}}
 
 \newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} 
 \newcommand{\cC}{\mathcal C} 
 \newcommand{\cV}{\mathcal{V}} 
 \newcommand{\cU}{\mathcal{U}}
+\newcommand{\cG}{\mathcal{G}}
 \newcommand{\bN}{\mathbb N} 
 \newcommand{\bR}{\mathbb R}
 \newcommand{\bZ}{\mathbb Z} 
@@ -447,56 +451,64 @@
   useful when recursively constructing the generic automorphism of a Fraïssé 
   limit.
 
-
-  % \begin{definition} For $\cC$, $M$ as in Fact~\ref{fact:fraisse_thm}, we
-  % write $\Flim(\cC)\coloneqq M$.  \end{definition}
-
-  % \begin{fact} If $\cC$ is a uniformly locally finite Fraïssé class, then
-  % $\Flim(\cC)$ is $\aleph_0$-categorical and has quantifier elimination.
+  % \begin{fact} If $\bK$ is a uniformly locally finite Fraïssé class, then
+  % $\Flim(\bK)$ is $\aleph_0$-categorical and has quantifier elimination.
   % \end{fact}
 
-  % \section{Conjugacy classes in automorphism groups}
-
-  % \subsection{Prototype: pure set} In this section, $M=(M,=)$ is an
-  % infinite countable set (with no structure beyond equality).
-  % \begin{proposition} If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are
-  %   conjugate if and only if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$
-  %   and $f_2$ have the same number of orbits of size $n$.
-  % \end{proposition}
-
-  % \begin{proposition} The conjugacy class of $f\in \Aut(M)$ is dense if
-  %   and only if...  \end{proposition} \begin{proposition} If $f\in
-  % \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is
-  % meagre.  
-  % \end{proposition}
-
-  % \begin{proposition} An automorphism $f$ of $M$ is generic if and only if...
+  \section{Conjugacy classes in automorphism groups}
+
+  \subsection{Prototype: pure set} 
+  In this section, $M=(M,=)$ is an infinite countable set (with no structure
+  beyond equality).
+  \begin{proposition} 
+    If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are conjugate if and only 
+    if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$ and $f_2$ have the same 
+    number of orbits of size $n$.
+  \end{proposition}
+
+  \begin{proposition} The conjugacy class of $f\in \Aut(M)$ is dense if
+    and only if...  \end{proposition} \begin{proposition} If $f\in
+  \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is
+  meagre.  
+  \end{proposition}
+
+  % \begin{proposition} 
+    % An automorphism $f$ of $M$ is generic if and only if...
   % \end{proposition}
 
   % \begin{proof}
 
   % \end{proof}
 
-  % \subsection{More general structures}
-
+  \subsection{More general structures}
 
-  % \begin{proposition} Suppose $M$ is an arbitrary structure and $f_1,f_2\in
-  % \Aut(M)$. Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong
-  % (M,f_2)$.  \end{proposition}
+  \begin{fact} 
+    Suppose $M$ is an arbitrary structure and $f_1,f_2\in \Aut(M)$. 
+    Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong
+    (M,f_2)$ as structures with one additional unary relation that is
+    an automorphism.  
+  \end{fact}
 
-  % \begin{definition} We say that a Fraïssé class $\cC$ has \emph{weak
-  %   Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and partial
-  %   automorphism $p\colon A\to A$, there is some $B\in \cC$ such that $p$ can
-  %   be extended to an automorphism of $B$, i.e.\ there is an embedding
-  %   $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following
-  %   diagram commutes: 
-  %   \begin{center} 
-  %     \begin{tikzcd} 
-  %       B\ar[r,"\bar p"]&B\\
-  %       A\ar[u,"i"]\ar[r,"p"]&A\ar[u,"i"] 
-  %     \end{tikzcd} 
-  %   \end{center}
-  % \end{definition}
+  \begin{proof}
+    Suppose that $f_1 = g^{-1}f_2g$ for some $g\in \Aut(M)$. 
+    Then $g$ is the automorphism we're looking for. On the other hand if 
+    $g\colon (M, f_1)\to (M, f_2)$ is an isomorphism, then 
+    $g\circ f_1 = f_2 \circ g$ which exactly means that $f_1, f_2$ conjugate.
+  \end{proof} 
+
+  \begin{definition} We say that a Fraïssé class $\bK$ has \emph{weak
+    Hrushovski property} (\emph{WHP}) if for every $A\in \bK$ and an isomorphism
+    of substructures of $A$ $p\colon A\to A$, there is some $B\in \bK$ such 
+    that $p$ can be extended to an automorphism of $B$, i.e.\ there is an 
+    embedding $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following
+    diagram commutes: 
+    \begin{center} 
+      \begin{tikzcd} 
+        B\ar[r,dashed,"\bar p"]&B\\
+        A\ar[u,dashed,"i"]\ar[r,"p"]&A\ar[u,dashed,"i"] 
+      \end{tikzcd} 
+    \end{center}
+  \end{definition}
 
   % \begin{proposition} Suppose $\cC$ is a Fraïssé class in a relational
   % language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$, all
@@ -504,10 +516,94 @@
   %   $\cC$ is a Fraïssé class in an arbitrary countable language with WHP.
   %   Then generically, for an $f\in \Aut(\Flim(\cC))$ ...  \end{proposition}
 
-  % \subsection{Random graph} \begin{definition} The \emph{random graph}
-  % is...  \end{definition}
+  \subsection{Random graph} 
+  
+  In this section we'll take a closer look on a class of finite graphs, which
+  form a Fraïssé class.
+
+  \begin{proposition}
+    Let $\cG$ be the class of all finite graphs. $\cG$ is a Fraïssé class.
+  \end{proposition}
+  \begin{proof}
+    $\cG$ is of course countable (up to isomorphism) and has the HP 
+    (graph substructure is also a graph). It has JEP: having two finite graphs 
+    $G_1,G_2$ take their disjoint union $G_1\sqcup G_2$ as the extension of them
+    both. $\cG$ has the AP. Having graphs $A, B, C$, where $B$ and $C$ are
+    supergraphs of $A$, we can assume without loss of generality, that 
+    $(B\setminus A) \cap (C\setminus A) = \emptyset$. Then 
+    $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we're looking
+    for (with edges as in B and C and without any edges between the disjoint
+    parts).
+  \end{proof}
+
+  \begin{definition}
+    The \emph{random graph} is the Fraïssé limit of the class of finite graphs
+    $\cG$ denoted by $\Gamma = \Flim(\cG)$.
+  \end{definition}
+
+  The concept of the random graph emerges independently in many fields of
+  mathematics. For example, one can construct the graph by choosing at random
+  for each pair of verticies if they should be connected or not. It turns out
+  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
+  random graph.
+
+  \begin{fact}[random graph property]
+    For each finite disjoint $X, Y\subseteq \Gamma$ there exists $v\in\Gamma$
+    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\}$,
+    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$.
+    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. 
+  \end{proof}
+
+  \begin{fact}
+    If a countable graph $G$ has the random graph property, then it is
+    isomorhpic to the random graph $\Gamma$.
+  \end{fact}
+  \begin{proof}
+    Enumerate verticies of both graphs: $\Gamma = \{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$
+    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
+    $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
+    a_{n+1}, b\rangle\}$ is a partial isomoprhism. We find $a$ for the
+    $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)$ .
+  \end{proof}
 
-  % \begin{fact} The \end{fact}
+  Using this fact one can show that the graph constructed in the probabilistic
+  manner is in fact isomorphic to the random graph $\Gamma$.
+
+  \begin{proposition}
+    The class of finite graphs $\cG$ has the weak Hrushovski property. 
+  \end{proposition}
+
+  \begin{proof}
+    It may be there some day, but it may not!
+  \end{proof}
 
   %   \begin{proposition} Generically, the set of fixed points of $f\in
   %   \Aut(M)$ is isomorphic to $M$ (as a graph).  \end{proposition}
-- 
cgit v1.2.3

