path: root/lic_malinka.tex

\documentclass[11pt, a4paper, final]{amsart} 
\setlength{\emergencystretch}{2em}

\usepackage[backend=biber]{biblatex}
\addbibresource{licmalinka.bib}


\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}

\usepackage{amsfonts} 
\usepackage{amsmath} 
\usepackage{amssymb}
\usepackage{amsthm} 
\usepackage{XCharter} 
\usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}
\usepackage{mathtools} 
\usepackage{enumitem} 
\usepackage[utf8]{inputenc}
\usepackage{tikz-cd} 
\usepackage{tikz}
\usetikzlibrary{arrows,arrows.meta}
\tikzcdset{arrow style=tikz, diagrams={>=latex}}

\usepackage{etoolbox}

\usepackage{xcolor} 
\definecolor{green}{RGB}{0,127,0}
\definecolor{redd}{RGB}{191,0,0} 

\definecolor{red}{RGB}{105,89,205}
\usepackage[colorlinks=true]{hyperref}

\usepackage[notref, notcite]{showkeys} 
\usepackage[cmtip,arrow]{xy}

\DeclareMathOperator{\Aut}{Aut} 
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Stab}{Stab} 
\DeclareMathOperator{\st}{st}
\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} 
\newcommand{\bQ}{\mathbb Q}
\newcommand{\bK}{\mathbb K}

\DeclareMathOperator{\im}{{Im}} 
\DeclareMathOperator{\lin}{{Lin}}
\DeclareMathOperator{\Th}{{Th}}

\newtheorem{theorem}{Theorem} 
\numberwithin{theorem}{section}
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact} 
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{question}[theorem]{Question}
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem*{theorem2}{Theorem}
\newtheorem*{claim2}{Claim} 
\newtheorem*{corollary2}{Corollary}
\newtheorem*{question2}{Question} 
\newtheorem*{conjecture2}{Conjecture}


\newtheorem{clm}{Claim} \newtheorem*{clm*}{Claim}


\theoremstyle{definition} 
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition2}{Definition} 
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark} 
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark2}{Remark}


\AtEndEnvironment{proof}{\setcounter{clm}{0}}
\newenvironment{clmproof}[1][\proofname]{\proof[#1]\renewcommand{\qedsymbol}{$\square$(claim)}}{\endproof}

\newcommand{\xqed}[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill
  \quad\hbox{\ensuremath{#1}}}


\title{Tytuł} 
\author{Franciszek Malinka}

\begin{document}
  \begin{abstract} 
    Abstract 
  \end{abstract} 
  \section{Introduction}

  \section{Preliminaries} 
  \subsection{Descriptive set theory}
  \begin{definition} 
    Suppose $X$ is a topological space and $A\subseteq X$.
    We say that $A$ is \emph{meagre} in $X$ if $A = \bigcup_{n\in\bN}A_n$,
    where $A_n$ are nowhere dense subsets of $X$ (i.e. $\Int(\bar{A_n})
    = \emptyset$).  
  \end{definition}

  \begin{definition} 
    We say that $A$ is \emph{comeagre} in $X$ if it is
    a complement of a meagre set. Equivalently, a set is comeagre iff it
    contains a countable intersection of open dense sets.  
  \end{definition}

      % \begin{example}
  Every countable set is meagre in any $T_1$ space, so, for example, $\bQ$
  is meagre in $\bR$ (though being dense), which means that the set of
  irrationals is comeagre. Another example is...
      % \end{example}

  \begin{definition}
    We say that a topological space $X$ is a \emph{Baire space} if every
    comeagre subset of $X$ is dense in $X$ (equivalently, every meagre set has
    empty interior).  
  \end{definition}

  \begin{definition}
    Suppose $X$ is a Baire space. We say that a property $P$ \emph{holds
    generically} for a point in $x\in X$ if $\{x\in X\mid P\textrm{ holds for
    }x\}$ is comeagre in $X$.  
  \end{definition}

  \begin{definition} Let $X$ be a nonempty topological space and let
    $A\subseteq X$. The \emph{Banach-Mazur game of $A$}, denoted as
    $G^{\star\star}(A)$ is defined as follows: Players $I$ and
    $\textit{II}$ take turns in playing nonempty open sets $U_0, V_0,
    U_1, V_1,\ldots$ such that $U_0 \supseteq V_0 \supseteq U_1 \supseteq
    V_1 \supseteq\ldots$. We say that player $\textit{II}$ wins the game if
    $\bigcap_{n}V_n \subseteq A$.  
  \end{definition}

  There is an important theorem on the Banach-Mazur game: $A$ is comeagre
  iff $\textit{II}$ can always choose sets $V_0, V_1, \ldots$ such that
  it wins. Before we prove it we need to define notions necessary to
  formalise and prove the theorem.

  \begin{definition}
    $T$ is \emph{the tree of all legal positions} in the Banach-Mazur game
    $G^{\star\star}(A)$ when $T$ consists of all finite sequences $(W_0,
    W_1,\ldots, W_n)$, where $W_i$ are nonempty open sets such that
    $W_0\supseteq W_1\supseteq\ldots\supseteq W_n$. In another words, $T$ is
    a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$.
  \end{definition} 

  \begin{definition}
    We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal
    positions $T$ if $\sigma\subseteq T$ and for any $(W_0, W_1, \ldots,
    W_n)\in\sigma, n\ge 0$ there is a $W$ such that $(W_0, W_1,\ldots, W_n,
    W)\in\sigma$ (it simply means that there's no finite branch in~$\sigma$).  
  \end{definition}

  \begin{definition}
    Let $\sigma$ be a pruned subtree of the tree of all legal positions $T$. By
    $[\sigma]$ we denote \emph{the set of all infinite branches of $\sigma$},
    i.e. infinite sequences $(W_0, W_1, \ldots)$ such that $(W_0, W_1, \ldots
    W_n)\in \sigma$ for any $n\in \bN$.  
  \end{definition}

  \begin{definition} 
    A \emph{strategy} for $\textit{II}$ in
    $G^{\star\star}(A)$ is a pruned subtree $\sigma\subseteq T$ such that
    \begin{enumerate}[label=(\roman*)] 
      \item $\sigma$ is nonempty, 
      \item if $(U_0, V_0, \ldots, U_n, V_n)\in\sigma$, then for all open
      nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, U_n, V_n,
      U_{n+1})\in\sigma$, 
      \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for a unique $V_n$,
        $(U_0, V_0, \ldots,  U_{n}, V_n)\in\sigma$.
    \end{enumerate} 
  \end{definition}

  Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing
  $U_0$ as any open subset of $X$, then $\textit{II}$ plays unique (by
  (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by
  playing any $U_1\subseteq V_0$ and $\textit{II}$ plays uniqe $V_1$
  such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc.

  \begin{definition} 
    A strategy $\sigma$ is a \emph{winning strategy for $\textit{II}$} if for
    any game $(U_0, V_0\ldots)\in [\sigma]$ player $\textit{II}$ wins, i.e.
    $\bigcap_{n}V_n \subseteq A$.
  \end{definition}

  Now we can state the key theorem.

  \begin{theorem}[Banach-Mazur, Oxtoby]
  \label{theorem:banach_mazur_thm} 
    Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is
    comeagre $\Leftrightarrow$ $\textit{II}$ has a winning strategy in
    $G^{\star\star}(A)$.
  \end{theorem}

  In order to prove it we add an auxilary definition and lemma.
  \begin{definition}
    Let $S\subseteq\sigma$ be a pruned subtree of tree of all legal positions
    $T$ and let $p=(U_0, V_0,\ldots, V_n)\in S$.  We say that S is
    \emph{comprehensive for p} if the family $\cV_p = \{V_{n+1}\mid (U_0,
    V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ (it may be that $n=-1$, which
    means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in
    $V_n$ (where we think that $V_{-1} = X$).
    We say that $S$ is \emph{comprehensive} if it is comprehensive for
    each $p=(U_0, V_0,\ldots, V_n)\in S$.  
  \end{definition}

  \begin{fact} 
    If $\sigma$ is a winnig strategy for $\mathit{II}$ then
    there exists a nonempty comprehensive $S\subseteq\sigma$. 
  \end{fact}

  \begin{proof}
    We construct $S$ recursively as follows:
    \begin{enumerate} 
      \item $\emptyset\in S$, 
      \item if $(U_0, V_0, \ldots, U_n)\in S$, then $(U_0, V_0, \ldots, U_n,
        V_n)\in S$ for the unique $V_n$ given by the strategy $\sigma$, 
      \item let $p = (U_0, V_0, \ldots, V_n)\in S$. For a possible player $I$'s
        move $U_{n+1}\subseteq V_n$ let $U^\star_{n+1}$ be the unique set
        player $\mathit{II}$ would respond with by $\sigma$. Now, by Zorn's
        Lemma, let $\cU_p$ be a maximal collection of nonempty open subsets
        $U_{n+1}\subseteq V_n$ such that the set $\{U^\star_{n+1}\mid
        U_{n+1}\in\cU_p\}$ is pairwise disjoint.  Then put in $S$ all $(U_0,
        V_0, \ldots, V_{n}, U_{n+1})$ such that $U_{n+1} \in \cU_p$. This way
        $S$ is comprehensive for $p$: the family $\cV_p = \{V_{n+1}\mid (U_0,
        V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ is exactly
        $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$, which is pairwise disjoint and
        $\bigcup\cV_p$ is obviously dense in $V_n$ by the maximality of $\cU_p$
        -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint
        from $\bigcup\cV_p$, then $\tilde{U}^{\star}_{n+1}\subseteq
        \tilde{U}_{n+1}$ would be also disjoint from $\bigcup\cV_p$, so the
        family $\cU_p\cup\{\tilde{U}_{n+1}\}$ would violate the maximality of
        $\cU_p$.  
      \qedhere 
    \end{enumerate} 
  \end{proof}

  \begin{lemma} 
    \label{lemma:comprehensive_lemma}
    Let $S$ be a nonempty comprehensive pruned subtree of a strategy $\sigma$.
    Then:
    \begin{enumerate}[label=(\roman*)]
      \item For any open $V_n\subseteq X$ there is at most one $p=(U_0, V_0,
        \ldots, U_n, V_n)\in S$.  
      \item Let $S_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$ for $n\in\bN$
        (i.e. $S_n$ is a family of all possible choices player $\textit{II}$
        can make in its $n$-th move according to $S$). Then $\bigcup S_n$ is
        open and dense in $X$.  
      \item $S_n$ is a family of pairwise disjoint sets.  
    \end{enumerate} 
  \end{lemma}

  \begin{proof} 
    (i): Suppose that there are some $p = (U_0, V_0,\ldots,
    U_n, V_n)$, $p'=(U'_0, V'_0, \ldots, U'_n, V'_n)$ such that $V_n
    = V'_n$ and $p \neq p'$. Let $k$ be the smallest index such that those
    sequences differ. We have two possibilities: 
    \begin{itemize} 
      \item $U_k = U'_k$ and $V_k\neq V'_k$ -- this cannot be true simply by
        the fact that $S$ is a subset of a strategy (so $V_k$ is unique for
        $U_k$). \item $U_k\neq U'_k$: by the comprehensiveness of $S$ we know 
        that for $q =(U_0, V_0, \ldots, U_{k-1}, V_{k-1})$ the set $\cV_q$ is 
        pairwise disjoint. Thus $V_k\cap V'_k=\emptyset$, because $V_k, V'_k\in 
        \cV_q$. But this leads to a contradiction -- $V_n$ cannot be a nonempty 
        subset of both $V_k, V'_k$.  
    \end{itemize}

    (ii): The lemma is proved by induction on $n$. For $n=0$ it follows
    trivially from the definition of comprehensiveness. Now suppose the
    lemma is true for $n$. Then the set $\bigcup_{V_n\in
    S_n}\bigcup\cV_{p_{V_n}}$ (where $p_{V_n}$ is given uniquely from
    (i)) is dense and open in $X$ by the induction hypothesis. But
    $\bigcup S_{n+1}$ is exactly this set, thus it is dense and open in
    $X$.

    (iii): We will prove it by induction on $n$. Once again, the case $n
    = 0$ follows from the comprehensiveness of $S$. Now suppose that the
    sets in $S_n$ are pairwise disjoint. Take some $x \in V_{n+1}\in
    S_{n+1}$. Of course $\bigcup S_n \supseteq \bigcup S_{n+1}$, thus by
    the inductive hypothesis $x\in V_{n}$ for the unique $V_n\in S_n$. It
    must be that $V_{n+1}\in \cV_{p_{V_n}}$, because $V_n$ is the only
    superset of $V_{n+1}$ in $S_n$. But $\cV_{p_{V_n}}$ is disjoint, so
    there is no other $V'_{n+1}\in \cV_{p_{V_n}}$ suc h that $x\in
    V'_{n+1}$. Moreover, there is no such set in
    $S_{n+1}\setminus\cV_{p_{V_n}}$, because those sets are disjoint from
    $V_{n}$. Hence there is no $V'_{n+1}\in S_{n+1}$ other than $V_n$
    such that $x\in V'_{n+1}$. We've chosen $x$ and $V_{n+1}$ arbitrarily,
    so $S_{n+1}$ is pairwise disjoint.  
  \end{proof}

  Now we can move to the proof of the Banach-Mazur theorem.

  \begin{proof}[Proof of theorem \ref{theorem:banach_mazur_thm}]
    $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with
    $\bigcap_n A_n\subseteq A$.  The simply $\textit{II}$ plays $V_n
    = U_n\cap A_n$, which is nonempty by the denseness of $A_n$.

    $\Leftarrow$: Suppose $\textit{II}$ has a winning strategy $\sigma$.
    We will show that $A$ is comeagre. Take a comprehensive $S\subseteq
    \sigma$. We claim that $\mathcal{S} = \bigcap_n\bigcup S_n \subseteq
    A$. By the lemma~\ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup
    S_n$ are open and dense, thus $A$ must be comeagre. Now we prove the
    claim towards contradiction. 
  
    Suppose there is $x\in \mathcal{S}\setminus A$. By the lemma
    \ref{lemma:comprehensive_lemma}, (iii) for any $n$ there is unique
    $x\in V_n\in S_n$. It follows that $p_{V_0}\subset
    p_{V_1}\subset\ldots$. Now the game $(U_0, V_0, U_1, V_1,\ldots)
    = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ is not winning for
  player $\textit{II}$, which contradicts the assumption that $\sigma$ is
  a winning strategy.  \end{proof}

  \begin{corollary} 
    \label{corollary:banach-mazur-basis} 
    If we add a constraint to the Banach-Mazur game such that players can only 
    choose basic open sets, then the theorem \ref{theorem:banach_mazur_thm} 
    still suffices.  
  \end{corollary}

  \begin{proof} 
    If one adds the word \textit{basic} before each occurrence
    of word \textit{open} in previous proofs and theorems then they all
    will still be valid (except for $\Rightarrow$, but its an easy fix --
    take $V_n$ a basic open subset of $U_n\cap A_n$).  
  \end{proof}

  This corollary will be important in using the theorem in practice --
  it's much easier to work with basic open sets rather than any open
  sets.

  \section{Fraïssé classes}

  In this section we will take a closer look at classes of finitely
  generated structures with some characteristic properties. More
  specifically, we will describe a concept developed by a French
  mathematician Roland Fraïssé called Fraïssé limit.

  \subsection{Definitions} 
  \begin{definition}
    Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is
    the class $\bK$ of all finitely generated structures that embedds into $M$.
    The age of $M$ is also associated with class of all structures embeddable in
    $M$ \emph{up to isomorphism}.
  \end{definition}

  \begin{definition}
    We say that $M$ has \emph{countable age} when its age has countably many 
    isomorphism types of finitely generated structures. 
  \end{definition}

  \begin{definition}
    Let $\bK$ be a class of finitely generated structures. $\bK$ has 
    \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated
    substructure $B$ of $A$ it holds that $B\in\bK$. 
  \end{definition}

  \begin{definition}
    Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has
    \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a
    structure $C\in\bK$ such that both $A$ and $B$ embed in $C$.
  \end{definition}

  Fraïssé has shown fundamental theories regarding age of a structure, one of 
  them being the following one:
  
  \begin{fact}
    \label{fact:age_is_hpjep}
    Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set 
    of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if
    and only if $\bK$ is the age of some finite or countable structure. 
  \end{fact}

  Beside the HP and JEP Fraïssé has distinguished one more property of the 
  class $\bK$, namely amalgamation property.

  \begin{definition}
    Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$
    has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and
    embeddings $f\colon A\to B, g\colon A\to C$ there exists $D\in\bK$ together
    with embeddings $h\colon B\to D$ and $j\colon C\to D$ such that 
    $h\circ f = j\circ g$.
    \begin{center}
      \begin{tikzcd}
                                  & D & \\
        B \arrow[ur, dashed, "h"] &   & C \arrow[ul, dashed, "j"'] \\
                                  & A \arrow[ur, "g"'] \arrow[ul, "f"]
      \end{tikzcd}
    \end{center}
  \end{definition}

  \begin{definition}
    Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogenous} if every
    isomorphism between finitely generated substrucutres of $M$ extends to an
    automorphism of $M$.
  \end{definition}

  Having those definitions we can provide the main Fraïssé theorem.

  \begin{theorem}[Fraïssé theorem]
    \label{theorem:fraisse_thm}
    Let L be a countable language and let $\bK$ be a nonempty countable set of
    finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is 
    the age of a countable, ultrahomogenous $L$-structure $M$. Moreover, $M$ is
    unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$
    and denote this by $M = \Flim(\bK)$.
  \end{theorem}

  This is a well known theorem. One can read a proof of this theorem in Wilfrid
  Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof
  of this theorem appears another, equally important \ref{lemma:weak_ultrahom}.

  \begin{definition}
    We say that an $L$-structure $M$ is \emph{weakly ultrahomogenous} if for any
    $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and
    an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which
    extends $f$.
    \begin{center}
      \begin{tikzcd}
        A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\
        B \arrow[ur, dashed, "g"']
      \end{tikzcd}
    \end{center}
  \end{definition}

  \begin{lemma}
    \label{lemma:weak_ultrahom}
    A countable structure is ultrahomogenous if and only if it is weakly
    ultrahomogenous.
  \end{lemma}

  This lemma will play a major role in the later parts of the paper. Weak
  ultrahomogenity is an easier and more intuitive property and it will prove
  useful when recursively constructing the generic automorphism of a Fraïssé 
  limit.

  % \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}

  \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}

  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}

  \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}

  \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{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
  % orbits of $f$ are finite.  \end{proposition} \begin{proposition} Suppose
  %   $\cC$ is a Fraïssé class in an arbitrary countable language with WHP.
  %   Then generically, for an $f\in \Aut(\Flim(\cC))$ ...  \end{proposition}

    %   \begin{proposition} Generically, the set of fixed points of $f\in
  %   \Aut(M)$ is isomorphic to $M$ (as a graph).  \end{proposition}

  \printbibliography
\end{document}