Troche o grafie losowym

1 files changed, 143 insertions, 47 deletions

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}