\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em} \usepackage[utf8]{inputenc} \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{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{\cH}{\mathcal{H}} \newcommand{\bN}{\mathbb N} \newcommand{\bR}{\mathbb R} \newcommand{\bZ}{\mathbb Z} \newcommand{\bQ}{\mathbb Q} \newcommand{\bK}{\mathcal K} \newcommand{\FrAut}{\Pi} \newcommand{\FrGr}{\Gamma} \DeclareMathOperator{\im}{{Im}} \DeclareMathOperator{\id}{{id}} \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 if and only if 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$ (although it is 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 $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 if and only if $\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 other 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$, 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$) and $(W_0, W_1,\ldots W_{n-1})\in\sigma$ (every node on a branch is 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 unique $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 auxiliary 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 winning 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}}$ such 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 embeds 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{ultrahomogeneous} if every isomorphism between finitely generated substructures 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, ultrahomogeneous $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 ultrahomogeneous} 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 ultrahomogeneous if and only if it is weakly ultrahomogeneous. \end{lemma} This lemma will play a major role in the later parts of the paper. Weak ultrahomogeneity 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 unordered graphs, which is a Fraïssé class. The language of unordered graphs $L$ consists of a single binary relational symbol $E$. If $G$ is an $L$-structure then we call it a \emph{graph}, and its elements $\emph{vertices}$. If for some vertices $u, v\in G$ we have $G\models uEv$ then we say that there is an $\emph{edge}$ connecting $u$ and $v$. If $G\models \forall x\forall y (xEy\leftrightarrow yEx)$ then we say that $G$ is an \emph{unordered graph}. From now on we omit the word \textit{unordered} and graphs as unordered. \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 $B\setminus A$ and $C\setminus A$). \end{proof} \begin{definition} The \emph{random graph} is the Fraïssé limit of the class of finite graphs $\cG$ denoted by $\FrGr = \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 vertices if they should be connected or not. It turns out that the graph constructed this way is isomorphic to the random graph with probability 1. 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 \FrGr$ there exists $v\in\FrGr\setminus (X\cup Y)$ 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\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 vertices 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 $\FrGr$. Without 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 ultrahomogeneity of $\FrGr$ this isomorphism 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 isomorphic to the random graph $\FrGr$. \end{fact} \begin{proof} Enumerate vertices 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 \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 isomorphism. If $a_{n+1}\in\dom{f_n}$, then simply $b = f_n(a_{n+1})$. Otherwise, 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 vertices of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and $Y$ are those vertices that are not connected with $a_{n+1}$. Let $b$ be a vertex of $G$ that is connected to all vertices 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 isomorphism. 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. Finally, $f = \bigcup^{\infty}_{n=0}f_n$ is an isomorphism 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 $\FrGr$. \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 its substructures $p\colon A\to A$ (also called a partial automorphism of $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} \label{proposition:finite-graphs-whp} 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} \subsection{Graphs with automorphism} The language and theory of unordered graphs is fairly simple. We extend the language by one unary symbol $\sigma$ and interpret it as an arbitrary automorphism on the graph structure. It turns out that the class of such structures is a Fraïssé class. \begin{proposition} Let $\cH$ be the class of all finite graphs with an automorphism, i.e. structures in the language $(E, \sigma)$ such that $E$ is a symmetric relation and $\sigma$ is an automorphism on the structure. $\cH$ is a Fraïssé class. \end{proposition} \begin{proof} Countability and HP are obvious, JEP follows by the same argument as in plain graphs. We need to show that the class has the amalgamation property. Take any $(A, \alpha), (B, \beta), (C,\gamma)\in\cH$ such that $A$ embeds into $B$ and $C$. Without the loss of generality we may assume that $B\cap C = A$ and $\alpha\subseteq\beta,\gamma$. Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in the proof for the plain graphs. We will define the automorphism $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. We let $\delta\upharpoonright_B = \beta, \delta\upharpoonright_C = \gamma$. Let's check the definition is correct. We have to show that $(uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$ holds for any $u, v\in D$. We have two cases: \begin{itemize} \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 $\gamma$. 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} \label{proposition:graph-aut-is-normal} The Fraïssé limit of $\cH$ interpreted as a plain graph (i.e. as a reduct to the language of graphs) 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$. Without the loss of generality assume that $X\cup Y$ is $\sigma$-invariant, i.e. $\sigma(v)\in X\cup Y$ for $v\in X\cup Y$. This assumption can be made because there are no infinite orbits in $\sigma$, which in turn is due to the fact that $\cH$ is the age of $\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 vertices of $X$ and to none of $Y$. By the proposition \ref{proposition:finite-graphs-whp} we can extend $H$ together with its partial isomorphism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with automorphism $\tau$. Once again, without the loss of generality we can assume that $R\subseteq\FrAut$, because $\cH$ is the age of $\FrAut$. But $R\upharpoonright_{G_{XY}}$ together with $\tau\upharpoonright_{G_{XY}}$ are isomorphic to the $G_{XY}$ with $\sigma\upharpoonright_{G_{XY}}$. Thus, by ultrahomogeneity of $\FrAut$ this isomorphism extends to an automorphism $\theta$ of $(\FrAut, \sigma)$. Then $\theta(v)$ is the vertex that is connected to all vertices of $X$ and none of $Y$, because $\theta[R\upharpoonright_X] = X, \theta[R\upharpoonright_Y] = Y$. \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} \label{fact:conjugacy} 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{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} \begin{theorem} \label{theorem:generic_aut_graph} Let $\FrGr$ be the Fraïssé limit of the class of all finite graphs $\bK$. Then $\FrGr$ has a generic automorphism $\tau\in\Aut(\FrGr)$, i.e. the conjugacy class of $\tau$ is comeagre in $G = \Aut(\FrGr)$. \end{theorem} \begin{proof} We will construct a strategy for the second player in the Banach-Mazur game on the topological space $G$. This strategy will give us a subset $A\subseteq G$ and as we will see, this will also be a subset of the conjugacy class of $\tau$. By the Banach-Mazur theorem \ref{theorem:banach_mazur_thm} this will prove that the class is comeagre. Recall, $G$ has a basis consisting of open sets $\{g\in G\mid g\upharpoonright_A = g_0\upharpoonright_A\}$ for some finite set $A\subseteq \FrGr$ and some automorphism $g_0\in G$. In other words, a basic open set is a set of all extensions of some finite partial isomorphism $g_0$ of $\FrGr$. By $B_{g}\subseteq G$ we denote a basic open subset given by a finite partial isomorphism $g$. From now on we will consider only finite partial isomorphism $g$ such that $B_g$ is nonempty. With the use of corollary \ref{corollary:banach-mazur-basis} we can consider only games, where both players choose finite partial isomorphisms. Namely, player \textit{I} picks functions $f_0, f_1,\ldots$ and player \textit{II} chooses $g_0, g_1,\ldots$ such that $f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify the corresponding basic open subsets $B_{f_0}\supseteq B_{g_0}\supseteq\ldots$. Our goal is to choose $g_i$ in such a manner that the resulting function $g = \bigcap^{\infty}_{i=0}g_i$ will be an automorphism of the random graph such that $(\FrGr, g) = \Flim{\cH}$, i.e. the Fraïssé limit of finite graphs with automorphism. Precisely, $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$. By the Fraïssé theorem \ref{theorem:fraisse_thm} it will follow that $(\FrGr, g)\cong (\FrAut, \sigma)$. By the proposition \ref{proposition:graph-aut-is-normal} we can assume without the loss of generality that $\FrAut = \FrGr$ as a plain graph. Hence, by the fact \ref{fact:conjugacy}, $g$ and $\sigma$ conjugate in $G$. Once again, by the Fraïssé theorem \ref{theorem:fraisse_thm} and the \ref{lemma:weak_ultrahom} lemma constructing $g_i$'s in a way such that age of $(\FrGr, g)$ is exactly $\cH$ and so that it is weakly ultrahomogeneous will produce expected result. First, let us enumerate all pairs of finite graphs with automorphism $\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN}$ such that the first element of the pair embeds by inclusion in the second, i.e. $(A_n, \alpha_n)\subseteq (B_n, \beta_n)$. Also, it may be that $A_n$ is an empty graph. We enumerate the vertices of the random graph $\FrGr = \{v_0, v_1, \ldots\}$. Fix a bijection $\gamma\colon\bN\times\bN\to\bN$ such that for any $n, m\in\bN$ we have $\gamma(n, m) \ge n$. This bijection naturally induces a well ordering on $\bN\times\bN$. This will prove useful later, as the main argument of the proof will be constructed as a bookkeeping argument. Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$ and $X_{-1} = \emptyset$. Suppose that player \textit{I} in the $n$-th move chooses a finite partial isomorphism $f_n$. We will construct $g_n\supseteq f_n$ and a set $X_n\subseteq\bN^2$ such that following properties hold: \begin{enumerate}[label=(\roman*)] \item $g_n$ is an automorphism of the induced subgraph $\FrGr_n$, \item $g_n(v_n)$ and $g_n^{-1}(v_n)$ are defined, \item let $\{\langle (A_{n,k}, \alpha_{n, k}), (B_{n,k}, \beta_{n,k}), f_{n, k}\rangle\}_{k\in\bN}$ be the enumeration of all pairs of finite graphs with automorphism such that the first is a substructure of the second, i.e. $(A_{n,k}, \alpha_{n,k})\subseteq (B_{n,k}, \beta_{n,k})$, and $f_{n,k}$ is an embedding of $(A_{n,k}, \alpha_{n,k})$ in the $\FrGr_{n-1}$ (which is the graph induced by $g_{n-1}$). Let $(i, j) = \min\{(\{0, 1, \ldots\} \times \bN) \setminus X_{n-1}\}$ (with the order induced by $\gamma$). Then $X_n = X_{n-1}\cup\{(i,j)\}$ and $(B_{n,k}, \beta_{n,k})$ embeds in $(\FrGr_n, g_n)$ so that this diagram commutes: \begin{center} \begin{tikzcd} (A_{i,j}, \alpha_{i,j}) \arrow[d, "\subseteq"'] \arrow[r, "f_{i,j}"] & (\FrGr_{n-1}, g_{n-1}) \arrow[d, "\subseteq"] \\ (B_{i,j}, \beta_{i,j}) \arrow[r, dashed, "\hat{f}_{i,j}"'] & (\FrGr_n, g_n) \end{tikzcd} \end{center} \end{enumerate} First item makes sure that no infinite orbit will not be present in $g$. The second item together with the first one are necessary for $g$ to be an automorphism of $\FrGr$. The third item is the one that gives weak ultrahomogeneity. Now we will show that indeed such $g_n$ may be constructed. First, we will suffice the (iii) item. Namely, we will construct $\FrGr'_n, g'_n$ such that $g_{n-1}\subseteq g'_n$ and $f_{i,j}$ extends to an embedding of $(B_{i,j}, \beta_{i,j})$ to $(\FrGr'_n, g'_n)$. Without the loss of generality we may assume that $f_{i,j}$ is an inclusion and that $A_{i,j} = B_{i,j}\cap\FrGr_{n-1}$. Then let $\FrGr'_n = B_{i,j}\cup\FrGr_{n-1}$ and $g'_n = g_{n-1}\cup \beta_{i,j}$. Then $(B_{i,j}, \beta_{i,j})$ simply embeds by inclusion in $(\FrGr'_n, g'_n)$, i.e. this diagram commutes: \begin{center} \begin{tikzcd} (A_{i,j}, \alpha_{i,j}) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & (\FrGr_{n-1}, g_{n-1}) \arrow[d, "\subseteq"] \\ (B_{i,j}, \beta_{i,j}) \arrow[r, dashed, "\subseteq"'] & (\FrGr'_n, g'_n) \end{tikzcd} \end{center} The argument that those are actually embeddings is almost the same as in proof of the amalgamation property of $\cH$. It may be also assumed without the loss of generality that $\FrGr'_n\subseteq \FrGr$. Of course by the recursive assumption $\FrGr_{n-1}\subseteq\FrGr$. The $\FrGr'_n \setminus\FrGr_{n-1} = B_{i,j}\setminus A_{i,j}$ can be found in $\FrGr$ by the random graph property -- we can find vertices of the remaining part of $B_{i,j}$ each at a time so that all edges are correct. Now, by the WHP of $\bK$ we can extend the graph $\FrGr'_n\cup\{v_n\}$ together with its partial isomorphism $g'_n$ to a graph $\FrGr_n$ together with its automorphism $g_n\supseteq g'_n$, where without the loss of generality we may assume that $\FrGr_n\subseteq\FrGr$. This way we've constructed $g_n$ that has all desired properties. Now we need to see that $g = \bigcap^{\infty}_{n=0}g_n$ is indeed an automorphism of $\FrGr$ such that $(\FrGr, g)$ has the age $\cH$ and has weak ultrahomogeneity. It is of course an automorphism of $\FrGr$ as it is defined for every $v\in\FrGr$ and is a sum of increasing chain of finite automorphisms. Take any finite graph with automorphism $(B, \beta)$. Then, there are $i, j$ such that $(B, \beta) = (B_{i, j}, \beta_{i,j})$ and $A_{i,j}=\emptyset$. By the bookkeeping there was $n$ such that $(i, j) = \min\{\{0,1,\ldots\}\times\bN\setminus X_{n-1}\}$. This means that $(B, \beta)$ embeds into $(\FrGr_n, g_n)$, hence it embeds into $(\FrGr, g)$. With a similar argument we can see that $(\FrGr, g)$ is weakly ultrahomogeneous. By this we know that $g$ and $\sigma$ conjugate in $G$. As we stated in the beginning of the proof, the set of possible outcomes of the game (i.e. possible $g$'s we end up with) is comeagre in $G$, thus $\sigma^G$ is also comeagre and $\sigma$ is a generic automorphism. \end{proof} \printbibliography \end{document}