From d457bc06427c6e70c0d6cb19b1b6203bdd57ffc9 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Wed, 20 Apr 2022 20:55:53 +0200
Subject: Main proof

---
 lic_malinka.tex | 116 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 100 insertions(+), 16 deletions(-)

(limited to 'lic_malinka.tex')

diff --git a/lic_malinka.tex b/lic_malinka.tex
index f7a3570..47dea88 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -1,10 +1,10 @@
 \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}
@@ -19,7 +19,6 @@
 \usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}
 \usepackage{mathtools} 
 \usepackage{enumitem} 
-\usepackage[utf8]{inputenc}
 \usepackage{tikz-cd} 
 \usepackage{tikz}
 \usetikzlibrary{arrows,arrows.meta}
@@ -541,6 +540,20 @@
   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 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}
     \label{proposition:finite-graphs-whp}
     The class of finite graphs $\cG$ has the weak Hrushovski property. 
@@ -568,7 +581,7 @@
 
     Take any graphs $(A, \alpha), (B, \beta), (C,\gamma)$ such that $A$ embedds
     into $B$ and $C$. Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in
-    the proof for the plain graphs. We will define the automorphis
+    the proof for the plain graphs. We will define the automorphism
     $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. (TODO: chyba nie
     tylko extends ale coś więcej: wiem o co chodzi, ale nie wiem jak to
     napisać) We let $\delta_{\upharpoonright X} = \id_X$ for $X\in \{A,
@@ -591,6 +604,7 @@
   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 is isomorphic to
     the random graph $\FrGr$. 
   \end{proposition}
@@ -647,6 +661,7 @@
   \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
@@ -660,19 +675,6 @@
     $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
@@ -683,5 +685,87 @@
     %   \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 coresponding 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. 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 generatlity 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 ultrahomogenous
+	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 embedds 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 verticies of the random graph 
+	$\FrGr = \{v_0, v_1, \ldots\}$.
+	
+	Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$. 
+	Suppose that player \textit{I} in the $n$-th move chose a finite partial
+	isomoprhism $f_n$. We will construct $g_n\supseteq f_n$ 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}\}$. Then
+		$(B_{n,k}, \beta_{n,k})$ embedds 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, g_n) \\
+			(B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\hat{f}_{i,j}"']
+		  \end{tikzcd}
+		\end{center}
+	\end{enumerate}
+
+	First item makes sure that no inifite 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. 
+  \end{proof}
+
+
+
   \printbibliography
 \end{document}
-- 
cgit v1.2.3

