From d457bc06427c6e70c0d6cb19b1b6203bdd57ffc9 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Wed, 20 Apr 2022 20:55:53 +0200 Subject: Main proof --- lic_malinka.pdf | Bin 374634 -> 381541 bytes lic_malinka.tex | 116 ++++++++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 100 insertions(+), 16 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 8229069..b46df85 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ 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