\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}