From 78cbd57aad87cd07d4ebe218d09a8a926b12b2cb Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sat, 26 Mar 2022 15:18:26 +0100 Subject: Troche o grafie losowym --- lic_malinka.pdf | Bin 345258 -> 367251 bytes lic_malinka.tex | 190 ++++++++++++++++++++++++++++++++++++++++++-------------- update-pdf.sh | 3 + 3 files changed, 146 insertions(+), 47 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 5663434..f447c1c 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ 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} diff --git a/update-pdf.sh b/update-pdf.sh index 8d1534a..f342079 100644 --- a/update-pdf.sh +++ b/update-pdf.sh @@ -18,6 +18,9 @@ do then echo "updating" pdflatex $PRACA + biber $PARACA + pdflatex $PRACA + pdflatex $PRACA else sleep 0.2 fi -- cgit v1.2.3