1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
\documentclass[../lic_malinka.tex]{subfiles}
\begin{document}
In this section we give examples and anti-examples of Fraïssé classes
with WHP or CAP.
\begin{example}
The class of all finite graphs $\cG$ is a Fraïssé class with WHP and free
amalgamation.
\end{example}
We have already shown this fact. Thus get that the random graph has a generic
automorphism.
\begin{example}
A $K_n$-free graph is a graph with no $n$-clique as its subgraph.
Let $\cG_n$ be the class of finite \emph{$K_n$-free} graphs. $\cG_n$
is a Fraïssé class with WHP and free amalgamation.
\end{example}
Showing that $\cG_n$ is indeed a Fraïssé class is almost the same as in
normal graphs, together with free amalgamation. WHP is trickier and the proof
can be seen in \cite{eppa_presentation} Theorem 3.6. Hence, $\Flim(\cG_n)$
has a generic automorphism.
\begin{example}
The class $\cV$ of all finitely generated vector spaces over a countable field
is a Fraïssé class with WHP and CAP.
\end{example}
Vector spaces of the same dimension are isomorphic, thus it is obvious that
$\cV$ is essentially countable. Also $HP$ and $JEP$ are obvious, as we can
always embed space with smaller dimension into the bigger one.
Amalgamation is a little more complex but still comes intuitively. Let $A$,
$B$ and $C$ be finitely dimensional vector spaces such that $C = A\cap B$.
Thus, we can write that $A = C\oplus C_A$ and $B = C\oplus C_B$. Then let
$D = C_A \oplus C \oplus C_B$ with embedding of $A$ and $B$ into $C_A\oplus C$
and $C_B\oplus C$ respectively. This is also canonical amalgamation.
The Fraïssé limit of $\cV$ is an $\omega$-dimensional vector space (which
is easy to see by Theorem \ref{theorem:fraisse_thm}). Hence we can conclude
that it has a generic automorphism.
Now we give some anti-examples:
\begin{example}
Let $\cL$ be the class of all finite linear orderings. Then:
\begin{enumerate}
\item $\cL$ is a Fraïssé class.
\item $\cL$ has canonical amalgamation.
\item $\cL$ does not have WHP.
\end{enumerate}
\end{example}
$\cL$ of course has HP and is essentially countable. JEP is also easy,
as having two finite linear orderings we can just embed the one with fewer
elements into the bigger one.
We will show that $\cL$ has canonical amalgamation (CAP).
Let $C$ be a finite linear ordered set.
We will define $\otimes_C$. Let $A$, $B$ be finite linear orderings that
$C$ embeds into. We may suppose that $C = A\cap B$. Then we define an
ordering on $D = A\cup B$. For $d,e \in D$, let $d\le_D e$ if one of the
following hold:
\begin{itemize}
\item $d,e\in A$ and $d\le_A e$,
\item $d,e\in B$ and $d\le_B e$,
\item $d\in A, e\in B$ and there is $c\in C$ such that $d\le_A c$ and
$c\le_B e$,
\item $d\in B, e\in A$ and there is $c\in C$ such that $d\le_B c$ and
$c\le_A e$,
\item $d\in A, e\in B$ and for all $c\in C$ $d\le_A c\Leftrightarrow e\le_B c$
\end{itemize}
One can imagine that $D$ can be constructed by laying elements of $C$
in a row and putting elements of $A$ and $B$ appropriately between elements
of $C$ with all elements of $A$ to the left and all elements of $B$ to
the right between two adjacent elements of $C$. This clearly is
a canonical amalgamation.
\vspace{0.5cm}
\begin{figure}[h]
\centering
\begin{tikzpicture}
\draw[->,thick] (-1.5,0)--(1.5,0) node[right]{$C$};
\foreach \x in {0,...,2}
\node at ({-1.5+3/4*(1+\x)},0)[circle,fill=green,inner sep=2pt]{};
\draw[->] (-1,0.5) -- (-3,1.5);
\draw[->] (1,0.5) -- (3,1.5);
\draw[->,thick] (-6, 2)--(0,2) node[right]{$A$};
\foreach \x in {0,...,7}
\node at ({-6 + 6/9 * (\x+1)},2)[rectangle,fill=red, inner sep=2pt]{};
\foreach \x in {2,5,6}
\node at ({-6 + 6/9 * (\x+1)},2)[circle,fill=green, inner sep=2pt]{};
\draw[->] (-3,2.5) -- (-2,3.5);
\draw[->,thick] (1, 2)--(6,2) node[right]{$B$};
\foreach \x in {0,2,4,6}
\node at ({1+5/8*(\x+1)},2)[star,fill=blue, inner sep=2pt]{};
\foreach \x in {1, 3, 5}
\node at ({1+5/8*(\x+1)},2)[circle,fill=green, inner sep=2pt]{};
\draw[->] (3,2.5) -- (2,3.5);
\draw[->,thick] (-5, 4)--(5,4) node[right]{$D$};
% \foreach \x in {0,...,11}
% \node at ({-5+10/13*(\x+1)}, 4)[circle,fill=black,inner sep=2pt]{};
\foreach \x in {3,7,9}
\node at ({-5+10/13*(\x+1)}, 4)[circle,fill=green,inner sep=2pt]{};
\foreach \x in {0,1,4,5,10}
\node at ({-5+10/13*(\x+1)}, 4)[rectangle,fill=red,inner sep=2pt]{};
\foreach \x in {2,6,8,11}
\node at ({-5+10/13*(\x+1)}, 4)[star,fill=blue,inner sep=2pt]{};
\end{tikzpicture}
\caption{Visual representation of the construction.}
\end{figure}
\vspace{0.5cm}
On the other hand $\cL$ cannot have $WHP$. This follows from the fact that
that only automorphism of a finite linear ordering is identity, so
we cannot extend a partial automorphism sending exactly one element to
some distinct element. However, in this case, generic automorphism exists
which was shown by Truss \cite{truss_gen_aut}.
\begin{definition}
Let $X$ be a set. A ternary relation $\le^C \subseteq X^3$ is a
\emph{cyclic order}, where we denote $(a,b,c)\in{\le^C}$ as $a\le^{C}_{b}c$
(or simply $a\le_bc$ when there's only one relation in the context),
when it satisfies the following properties:
\begin{itemize}
\item If $a\le_bc$, then $b\le_ca$.
\item If $a\le_bc$, then not $c\le_ba$.
\item If $a\le_bc$ and $a\le_cd$, then $a\le_bd$.
\item If $a,b,c$ are pairwise distinct, then either $a\le_bc$ or
$c\le_ba$.
\end{itemize}
\end{definition}
It is easy to visualize a cyclic ordering as a directed (\textit{nomen omen})
cycle. For example, a 11-element cyclic order could be drawn like this:
\begin{figure}[h]
\centering
\begin{tikzpicture}
\def \n {11}
\def \radius {3cm}
\def \margin {10}
\foreach \s in {1,...,\n}
{
\node[draw, circle] at ({360/\n * (\s - 1)}:\radius) {};
\draw[->, >=latex] ({360/\n * (\s - 1)+\margin}:\radius)
arc ({360/\n * (\s - 1)+\margin}:{360/\n * (\s)-\margin}:\radius);
}
\node[draw, circle, fill=green] at ({360/\n * (1 - 1)}:\radius) {};
\node[draw, circle, fill=blue] at ({360/\n * (5 - 1)}:\radius) {};
\node[draw, circle, fill=red] at ({360/\n * (9 - 1)}:\radius) {};
\end{tikzpicture}
\end{figure}
For three elements $a, b, c$ we say that $a\le_bc$ if after ''cutting'' the
cycle at $b$ we have a path from $a$ to $c$.
In this particular example we can say that the green element is
red-element-smaller than the blue one.
\begin{example}
The class $\cC$ of all finite cyclic orders is a Fraïssé class, but does
not have WHP or CAP.
\end{example}
It is not hard to show that $\cC$ is indeed the Fraïssé class. As usual,
the hardest part is showing AP, which in this case is done analogously to
the linear orders. The Fraïssé limit of $\cC$ is a countable unit circle.
$\cC$ hasn't WHP by the similar argument to this for linear
orderings. Imagine a cycling order of three elements and a partial automorphism
with one fixed point and moving second element to the third. This cannot be
extended to automorphism of any finite cyclic order.
Also, $\cC$ cannot have CAP. A reason to that is that it do not admit
canonical amalgamation over the empty structure see this by taking
1-element cyclic order and 3-element cyclic order with automorphism other
than identity).
In contrast to linear orderings the Fraïssé limit $\Sigma = \Flim{\cC}$
has no generic automorphism. Consider the set $A$ of automorphisms of $\Sigma$
with at least one finite orbit of size greater than $1$. It is open, not dense
and closed on conjugation. Openness follows from the fact that all
finite orbits of a given automorphism have the same size. Thus $A$ can be
represented as a union of basic set generated by finite cycles of
length greater than $1$. It is not dense, as it has empty intersection with
basic set generated by identity of a single element. It is also closed on
taking conjugation, as the order of elements does not change when conjugating.
Thus there cannot be a dense conjugacy class in $\Aut(\Sigma)$ and so there's
no generic automorphism.
\end{document}
|
