text:
\begin{document}
\title{Scaling of the Atmosphere of Self-Avoiding Walks}
\author{A L Owczarek$^1$ and T Prellberg$^2$\\
  \footnotesize
  \begin{minipage}{13cm}
    $^1$ Department of Mathematics and Statistics,\\
    The University of Melbourne, Victoria~3010, Australia.\\
    \texttt{a.owczarek@ms.unimelb.edu.au}\\[1ex]

$^2$ School of Mathematical Sciences\\
Queen Mary, University of London\\
Mile End Road, London E1 4NS, UK\\
\texttt{t.prellberg@qmul.ac.uk}
\end{minipage}
}

\maketitle

\begin{abstract}
The number of free sites next to the end of a self-avoiding walk is known as the \emph{atmosphere}.
The average atmosphere can be related to the number of configurations. Here we study the distribution
of atmospheres as a function of length and how the number of walks of fixed atmosphere scale.
Certain bounds on these numbers can be proved. We use Monte Carlo estimates to verify our conjectures. Of particular interest
are walks that have zero atmosphere, which are known as \emph{trapped}. We demonstrate that these
walks scale in the \emph{same} way as the full set of self-avoiding walks, barring an overall constant factor.

\end{abstract}

\newpage

Consider an $n$-step self-avoiding walk $\omega=(\omega_0,\omega_1,\ldots,\omega_n)$
with $n+1$ sites $\omega_i\in\mathbb Z^d$ for $d\geq2$, and steps having unit length,
i.e. $|\omega_{i+1}-\omega_i|=1$.

\begin{figure}[ht!]
\label{figure1}
\centering
\includegraphics[width=0.4\textwidth]{sawatm.eps}
\caption{A self-avoiding walk on the square lattice $\mathbb Z^2$ with
$n=20$ steps and an atmosphere $a=2$.}
\end{figure}

The number of edges that can be appended to the last visited vertex $\omega_n$ to
create an $(n+1)$-step is called the \emph{atmosphere} of the walk $\omega$.
Clearly the smallest value of the atmosphere is zero, in which case the walk is
called \emph{trapped}. A zero-step self-avoiding walk has atmosphere $2d$, and for
$n\geq1$ any $n$-step self-avoiding walk has atmosphere of at most $2d-1$.

We partition the set of $n$-step self-avoiding walks by the value of their atmosphere.
Denote by $c_n$ the number
of $n$-step self-avoiding walks starting at $\omega_0=0$, and by $c_n^{(a)}$ the
number of $n$-step self-avoiding walks starting at $\omega_0=0$ with atmosphere $a$.

The subject of this paper is the fraction of $n$-step self-avoiding walks with fixed
atmosphere,
\begin{equation}
p_n^{(a)}=\frac{c_n^{(a)}}{c_n}\;,
\end{equation}
 and its limiting behaviour as $n\to\infty$.

The atmosphere was introduced by Rechnitzer and Janse van Rensburg \cite{rechnitzer2002a} for self-avoiding walks. Since it is well established theoretically, though not proven, that
\begin{equation}
c_n \sim A_1 \mu^n n^{\gamma-1}
\label{cn-scale}
\end{equation}
they immediately pointed out that the \emph{mean} atmosphere could be used to estimate the connective constant $\mu$ and exponent $\gamma$ since
\begin{equation}
\langle a \rangle = \sum_a a p_n^{(a)} =  \frac{\sum_a a c_n^{(a)}}{c_n} = \frac{c_{n+1}}{c_n}\;.
\end{equation}
Subsequently they have generalised this elegant idea to self-avoiding walks near walls \cite{rechnitzer2004a} and recently to self-avoiding polygons \cite{janse2008a}.

Motivating this paper is recent interest in various subsets of  walks that do not \emph{trap} \cite{guttmann2007,bousquet2008} including prudent walks \cite{turban1987,santra2001}. The question that naturally arises for each class of walks is \emph{``Does  the numbers of walks in the class scale in the same way as full set of self-avoiding walks"}; that is, as in equation~(\ref{cn-scale}) with the same value of $\mu$ and the same value of $\gamma$.

It is then natural to consider the limits
\begin{equation}
p^{(a)} = \lim_{n\to\infty} \frac{c_n^{(a)}}{c_n}\;.
\label{limits}
\end{equation}
In this paper we demonstate results in the literature \cite{madras1993,madras1988} can be used to prove
\begin{equation}
\liminf_{n\to\infty}\frac{c_n^{(a)}}{c_n}>0\;,
\label{liminfs}
\end{equation}
and so that if one assumes the limit  exists then one has immediately
 that
 \begin{equation}
 p^{(a)} >0\;.
 \end{equation}
 Going further and assuming the scaling in  equation~(\ref{cn-scale})  we can therefore predict
 \begin{equation}
c_n^{(a)} \sim A_1^{(a)} \mu^n n^{\gamma-1}\;,
\label{cna-scale}
\end{equation}
where
 \begin{equation}
 A_1^{(a)} =   p^{(a)} A_1\;.
 \end{equation}
  Hence walks that trap, that is, those with atmosphere zero will have the same connective constant and same value of exponent $\gamma$ as all self-avoiding walks. Conversely the same is true for walks that do not trap.

Furthermore we use the Monte Carlo Algorithm flatPERM\cite{prellberg2004}  to provided estimates for $p_n^{(a)}$ up to length $n=512$ and use the corrections-to-scaling to extrapolate high-precision estimates of $ p^{(a)} $.

\paragraph{Theory}
Intuitively one would expect that the probability that the end of
a long self-avoiding walk $\omega$ ends at the corner of a cube $Q$
of fixed size, but otherwise does not intersect with the cube, is non-zero.
Therefore one can append to this walk a short walk contained within the cube
with fixed atmosphere. Using a related argument, we shall prove below  that
the \emph{limes inferior} of $p_n^{(a)}$ is bounded away from zero.

Our main result is the following theorem.

\begin{theorem}
\label{theorem1}
Let $0\leq a<2d$. Then
$$\liminf_{n\to\infty}p_n^{(a)}>0\;,$$
and
$$\limsup_{n\to\infty}p_n^{(a)}<1\;.$$

\end{theorem}

This theorem is very similar to a result concerning tail patterns of self-avoiding walks.

\begin{definition}
A self-avoiding walk $P=(p_0,p_1,\ldots,p_k)$ is called a \emph{tail pattern} if there is a self-avoiding walk
$\omega=(\omega_0,\omega_1,\ldots,\omega_n)$ such that $P=(\omega_{n-k},\omega_{n-k+1},\ldots,\omega_n)$.
$P$ is called a \emph{proper tail pattern} if for all sufficiently large $n$ there is a self-avoiding walk having
$P$ as a tail pattern.
\end{definition}

Let $c_n[P]$ be the number of $n$-step self-avoiding walks with tail pattern $P$.
We have the following result, which is taken from \cite{madras1993}.

\begin{proposition}
\label{madras}
If $P$ is a proper tail pattern then
$$\liminf_{n\to\infty}\frac{c_n[P]}{c_n}>0\;.$$

\end{proposition}

When applying this proposition for the proof of Theorem \ref{theorem1}, we find that the main difficulty
is that the atmosphere of a proper tail pattern $P$ and the atmosphere of a self-avoiding walk having $P$
as a tail pattern can be different.

\begin{proof}[Proof of Theorem \ref{theorem1}]
It is sufficient to show that for any atmosphere $a$ with $0\leq a<2d$ there exist a proper
tail pattern $P_a$ with atmosphere $a$ and the additional property that any sufficiently long
self-avoiding walk having $P_a$
as a tail pattern has also atmosphere $a$. The first inequality then follows as an immediate
consequence of Proposition \ref{madras}, as $c_n^{(a)}\geq c_n[P_a]$, and therefore
$$\liminf_{n\to\infty}p_n^{(a)}=\liminf_{n\to\infty}\frac{c_n^{(a)}}{c_n}\geq\liminf_{n\to\infty}\frac{c_n[P_a]}{c_n}>0\;.$$
The upper bound follows now from the observation that $\sum_{a=0}^{2d-1}p_n^{(a)}=1$, as
\begin{align*}
\limsup_{n\to\infty}p_n^{(a)}=&\limsup_{n\to\infty}\left(1-\sum_{a'\neq a}p_n^{(a')}\right)\\
\leq&1+\sum_{a'\neq a}\limsup_{n\to\infty}\left(-p_n^{(a')}\right)\\
=&1-\sum_{a'\neq a}\liminf_{n\to\infty}p_n^{(a')}<1\;.
\end{align*}
The pattern $P_a$ is constructed as follows. Consider a self-avoiding walk $\omega$ which starts at the origin,
visits precisely $2d-a$ neighbouring vertices, and ends on the corner of a cube $Q$ containing it.
Continue $\omega$ by a self-avoiding walk $\omega'$ on the set of vertices $\partial Q$ which have distance 1 from $Q$,
and which is Hamiltonian on $\partial Q$. The pattern $P_a$ which is obtained by reversal of steps is a proper
tail pattern. It has atmosphere $a$, and by construction the atmosphere of any sufficiently long
self-avoiding walk having $P$ as a tail pattern must also be $a$.
\end{proof}

Note that the idea of this proof generalises easily to different notions of atmosphere, such as a $k$-step atmosphere
given by the number of $(n+k)$-step self-avoiding walks which can be grown from an $n$-step self-avoiding walk.

\paragraph{Simulation results}
Backed up by the rigorous results, we now consider results of simulations for
self-avoiding walks on the square lattice $\mathbb Z^2$. Using flatPERM,
a flat-histogram kinetic growth algorithm, we have grown $10^9$ walks at length 512.
As a consequence of using a flat-histogram method with respect to the atmosphere,
we could boost the occurrence of zero-atmosphere walks roughly by a factor of three,
with minimal computational overhead.

\begin{figure}[ht!]
\centering
\includegraphics[width=0.9\textwidth]{atm.eps}
\caption{A plot of the probability $p_n^{(a)}$ of an $n$-step self-avoiding walk on the
square lattice having atmosphere $a$. Shown are $p_n^{(a)}$ for $a=0$, $1$, $2$, $3$
(from bottom to top) on a logarithmic scale versus $1/n$. We note that there are only small
corrections to scaling.}
\label{figure2}
\end{figure}

\begin{figure}[ht!]

\centering
\includegraphics[width=0.9\textwidth]{atms.eps}
\caption{A plot of the probability $p_n^{(a)}$ of an $n$-step self-avoiding walk on the
square lattice having atmosphere $a$. Shown are $p_n^{(a)}$ for $a=0$ (bottom right), $1$ (bottom left), $2$ (top right), $3$ (top left) on
a linear scale versus $1/n$, together with linear fits of $p_n^{(a)}$ to $1/n$ computed
from all walks with at least $100$ steps.}
\label{figure3}
\end{figure}

From Figure \ref{figure2} it is clear that the quantities $p_{n}^{(a)}$ approach an
asymptotic value quickly as $n\to\infty$ with only small corrections to scaling.

Figure \ref{figure3} shows that these corrections are asymptotically linear in $1/n$.
We therefore conjecture on the basis of our simulations that the limit
$$p^{(a)}=\lim_{n\to\infty}\frac{c_n^{(a)}}{c_n}$$
indeed exists. A linear fit can be used to obtain estimates for $p^{(a)}$, and we find that
\begin{align}
p^{(0)}=&0.009096(4)\\
p^{(1)}=&0.05476(1)\\
p^{(2)}=&0.22500(2)\\
p^{(3)}=&0.71114(3)
\end{align}
for self-avoiding walks on the square lattice $\mathbb Z^2$.

\section*{Acknowledgements}
Financial support from the Australian Research Council via its support
for the Centre of Excellence for Mathematics and Statistics of Complex
Systems is gratefully acknowledged by the authors.


TITLE: Time and work problem found to be hard
QUESTION [0 upvotes]: First pipe passes 4 liters of water per minute less then second pipe. How many liters of water per
minute passes through the first pipe if it fills a 480 liter basin 8 minutes longer than the second
pipe fills a 384 basin?

REPLY [2 votes]: Say the first pipe fills at a rate of $x$ liters per minute.
Then, the second pipe fills at a rate of $x+4$ liters per minute.
We know that $t=\frac{q}{r}$ where $r$ is the rate of filling, $t$ is the time taken and $q$ is the quantity filled.
So, $\frac{480}{x}=\frac{384}{x+4}+8$
Solve for $x$ by cross multiplying


TITLE: Find the Maclaurin series for the function $\tan^{-1}(2x^2)$
QUESTION [1 upvotes]: Find the Maclaurin series for the function  $\tan^{-1}(2x^2)$
Express your answer in sigma notation, simplified as much as possible. What is the open interval of convergence of the series.
I have the correct answer, but I would like to use another method to solve this.
By taking the function and its derivative, find the sum and then taking the anti derivative. This does not yield the same answer for me.

REPLY [2 votes]: You probably know the series for $\tan^{-1} t$. Plug in $2x^2$ for $t$.
If you do not know the series for $\arctan t$, you undoubtedly know the series for $\dfrac{1}{1-u}$. Set $u=-x^2$, and integrate term by term.
For the interval of convergence of the series for $\tan^{-1} (2x^2)$, you probably know when the series for $\tan^{-1}t$ converges. That knowledge can be readily translated to knowledge about $\tan^{-1}(2x^2)$.


text:
\begin{document}
\maketitle

\begin{abstract}
  We consider the conjugacy problem for the automorphism groups of a number of countable homogeneous structures. In each case we find the precise complexity of the conjugacy relation in the sense of Borel reducibility.
\end{abstract}

\section{Introduction}

In \cite{summer}, we showed together with Scott Schneider that the conjugacy problem for the automorphism group of the random graph is Borel complete. In this article we aim to continue this work and examine the complexity of the conjugacy problem for a variety of countable homogeneous structures. We begin by giving a brief overview of the above concepts.

Let $\mathcal L=\{R_i\}$ be a countable set of relation symbols, where each $R_i$ has arity $n_i$. Then the \emph{space of countable $\mathcal L$-structures} is given by
\[\Mod_{\mathcal L}=\prod\mathcal P(\NN^{n_i})\text{.}
\]
Here, $\Mod_{\mathcal L}$ has the product topology, and each factor has the natural Cantor set topology. Following Friedman--Stanley \cite{FS} and Hjorth--Kechris \cite{HK}, we identify the \emph{classification problem} for a set of $\mathcal L$-structures $C\subset\Mod_{\mathcal L}$ with the \emph{isomorphism equivalence relation} on $C$. In this article we will most often consider the language $\mathcal L=\{R\}$ where $R$ is a binary relation, and classes $C$ such as the countable undirected graphs, directed graphs, linear orderings, and so on.

In order to weigh the relative complexity of such classification problems, we use the following notion of reducibility between equivalence relations. First, recall that a Borel structure on a set $X$ is said to be \emph{standard} if it arises as the Borel $\sigma$-algebra of a separable, completely metrizable topology on $X$. Now if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be \emph{Borel reducible} to $F$, written $E\leq_BF$, if there exists a Borel function $f\colon X\to Y$ such that for all $x,x'\in X$,
\[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\text{.}
\]
Intuitively, if you have a set of complete invariants for $F$ and $E\leq_BF$ then by composing with the reduction function $f$ you can use the same invariants for $E$ as well.

If $E$ is Borel reducible to the equality relation on some (any) standard Borel space, then $E$ is said to be \emph{smooth} or completely classifiable. On the other end of the spectrum, if $E$ has the property that for any countable language $\mathcal L$ and any Borel class $C\subset\Mod_{\mathcal L}$ the isomorphism relation on $C$ is reducible to $E$, then $E$ is said to be \emph{Borel complete}. We remark that if $E$ is a Borel complete equivalence relation then $E$ is necessarily a non-Borel subset of $X\times X$ \cite{FS}.

We will use the following examples of Borel complete equivalence relations. The result is essentially folklore.

\begin{thm}
  The isomorphism equivalence relation on each of the following classes of countable structures is Borel complete:
\begin{itemize}
\item Linear orders
\item Tournaments
\item $K_n$-free graphs, where $K_n$ is the complete graph on $n$ vertices and $n\geq 3$
\item $\mathcal{F}$-avoiding digraphs, where $\mathcal{F}$ is a family of tournaments, each of size $\geq 3$.
\end{itemize}
\end{thm}

\begin{proof}
  The isomorphism relation on countable linear orders is Borel complete by Theorem~3 of \cite{FS}. Since any linear order is in particular a tournament, it follows that the isomorphism relation on countable tournaments is Borel complete too. For a nice presentation of a proof that the isomorphism relation on countable graphs is Borel complete, see Theorem~13.1.2 of \cite{gao}. The ``tag'' used in this proof can be easily modified to show Borel completeness for the isomorphism relation on the remaining two classes.
\end{proof}

In this article we will also study the \emph{conjugacy problem}, or the problem of deciding whether two elements in a given group are conjugate. As before we identify the conjugacy problem for $G$ with the conjugacy equivalence relation on $G$. When $G$ is the automorphism group of a countable $\mathcal{L}$-structure $M$, this equivalence relation is actually a special case of the isomorphism equivalence relations described above. Indeed, we can identify $\Aut(M)$ with the class $C\subset\Mod_{\mathcal L\cup\{R\}}$ of all expansions $(M;R^f)$ where $R^f$ is the binary relation which is the graph of the automorphism $f$. Then two elements of $\Aut(M)$ are conjugate if and only if the corresponding structures in $C$ are isomorphic.

We will study the conjugacy problem only for structures that are \emph{homogeneous}. A structure is homogeneous if every finite partial automorphism can be extended to a full automorphism. We direct the reader's attention to the survey \cite{macpherson} for a good overview of countable homogeneous structures. We will give several examples of homogeneous structures at the beginning of each subsequent section.

Homogeneous structures and their automorphisms have been studied a great deal from the point of view of model theory and algebra, for a survey of a portion of this work see \cite{lascar}. More recently, a deep connection between structural Ramsey theory and the topological dynamics of such groups has been explored, as detailed in \cite{kpt} and numerous subsequent articles.

Returning to conjugacy, after the results of \cite{summer} it seemed reasonable to conjecture that the conjugacy problem for automorphism groups of homogeneous structures is always either smooth (for ``trivial'' homogeneous structures like $\NN$ with no relations) or Borel complete (for ``complicated'' homogeneous structures like the random graph). After studying many further examples, we observe that this pattern \emph{mostly} holds, even though we found an exception in Theorem~\ref{thm:Ginfty}. It is our hope that a model theorist will look upon our results with a knowing wink and suggest or prove the right conjecture.

In Section~\ref{sec:LinearAndLocalOrders}, we sketch the proof that the conjugacy problem for countable homogeneous linear orders is Borel complete.  We also introduce local orders (and, more generally, the structures $S(n)$) and solve the analogous problem for them.  In the Section~\ref{sec:UndirectedGraphs}, we treat countable homogeneous simple undirected graphs. In Section~\ref{sec:Digraphs} we treat countable homogeneous digraphs, including tournaments. Here, a \emph{digraph} is a graph where $a\to b$, $b\to a$, or neither, \emph{but not both}.  We leave three technical cases of countable homogeneous digraphs for a future note.

\section{Linear and local orders}
\label{sec:LinearAndLocalOrders}

\subsection{Linear orders}
\label{sec:linear}

There is only one countable homogeneous linear order, called the rational order $\QQ$. This is perhaps the best-known nontrivial homogenous structure because it is the unique countable dense linear order without endpoints.  Foreman has shown in \cite[Theorem~76]{F} that the conjugacy relation on $\Aut(\QQ)$ is Borel complete. We present here a slightly streamlined variant of his proof, since the details will be useful in the next subsection.

\begin{thm}[\protect{\cite[Theorem~76]{F}}]\label{thm:foreman}
  The isomorphism relation on countable linear orders is Borel reducible to the conjugacy relation on $\Aut(\QQ)$. Hence the conjugacy relation on $\Aut(\QQ)$ is Borel complete.
\end{thm}

\begin{proof}
  We must construct a Borel map $L\mapsto\phi_L$ from the set of linear orders on $\NN$ into $\Aut(\QQ)$ which satisfies:
\[\text{$L$ is isomorphic to $L'$}\iff\text{$\phi_L$ is conjugate to $\phi_{L'}$}\;.
\]
To ensure that $(\Leftarrow)$ holds, \emph{i.e.} that $L$ can be recovered from the conjugacy class of $\phi_L$, we simply arrange that the fixed point set of $\phi_L$ is isomorphic to $L$.  The main point in guaranteeing $(\Rightarrow)$ is to make sure that if $L$ and $L'$ are isomorphic, then the linear orderings of orbitals of $\phi_L$ and $\phi_{L'}$ will be isomorphic.

Here, the \emph{orbitals} of $\phi\in\Aut(\QQ)$ are the convex closures of the orbits $\set{\phi^n(q):n\in\ZZ}$.  Evidently, every orbital $R$ of $\phi$ is either:
\begin{itemize}
\item an ``up-bump:'' for all $q\in R$ we have $\phi(q)>q$;
\item a ``down-bump:'' for all $q\in R$ we have $\phi(q)<q$; or
\item a singleton which is a fixed point of $\phi$.
\end{itemize}
\noindent What we need is the following classical result:

\begin{lem}[\protect{\cite[Theorem~2.2.5]{G}}]\label{lem:glass}
  Let $\phi,\psi\in\Aut(\QQ)$ and suppose that there is an order-preserving bijection between the orbitals of $\phi$ and the orbitals of $\psi$ which is also \emph{type preserving}, in the sense that it sends up-bumps to up-bumps, down-bumps to down-bumps, and fixed points to fixed points.  Then $\phi$ and $\psi$ are conjugate in $\Aut(\QQ)$.
\end{lem}

Hence, to show $(\Rightarrow)$, it suffices to ensure that the order type (and type) of the orbitals of $\phi_L$ depends only on the order type of $L$.  For this, we will need to be a little bit careful:

\begin{lem}\label{lem:perfect}
  For any countable linear order $L$, there exists an order-preserving embedding $\alpha\colon L\to\QQ$ such that for every $q\in\QQ\smallsetminus\im(\alpha)$ there is a greatest element $q^-$ of $\im(\alpha)\cup\set{-\infty}$ below $q$ and a least element $q^+$ of $\im(\alpha)\cup\set{\infty}$ above $q$.
\end{lem}

\begin{proof}
  Let $\alpha_0\colon L\to\QQ$ be any embedding.  Letting $S$ be $\im(\alpha_0)$ together with the set of points $q\in\QQ\smallsetminus\im(\alpha_0)$ satisfying the desired property, it is easy to see that $S$ is a dense linear order without endpoints.  Hence there exists an isomorphism $i\colon S\to\QQ$, and now the composition $\alpha=i\circ\alpha_0$ is as desired.
\end{proof}

We now describe the construction of the Borel assignment $L\mapsto\phi_L$. Given the countable linear order $L$, let $\alpha_L\colon L\to\QQ$ be an embedding satisfying the property in Lemma~\ref{lem:perfect}.  We begin our definition of $\phi_L$ by declaring it fixes every point of $\im(\alpha_L)$.  On the other hand, if $q\in\QQ\smallsetminus\im(\alpha_L)$, then we wish to define $\phi_L$ on each the interval $(q^-,q^+)$ so as to guarantee that $(q^-,q^+)$ is an up-bump for $\phi_L$.  This can easily be done, for instance, using a piecewise linear function similar to the one pictured in Figure~\ref{fig:bump}.

\begin{figure}
  \begin{tikzpicture}
    \draw (0,0) -- (3.8,0);
    \draw (0,0) -- (0,3.2);
    \draw (1,1) node[circle,draw,inner sep=1pt] {}
      edge (1.8,2.5)
      node[anchor=north] {$(a,a)$}
      (3,3) node[circle,draw,inner sep=1pt] {}
      edge (1.8,2.5)
      node[anchor=west] {$(b,b)$};
  \end{tikzpicture}
  \caption{An ``up-bump'' on the interval $(a,b)$.\label{fig:bump}}
\end{figure}

Since the fixed-point set of $\phi_L$ is exactly $\im(\alpha_L)$, we have guaranteed $(\Leftarrow)$. Since every remaining orbital of $\phi_L$ is an up-bump, the orbital structure of $\phi_L$ depends only on the order type of $L$.  Thus Lemma \ref{lem:glass} guarantees $(\Rightarrow)$.

Finally, we observe that our construction can be made explicit by fixing an enumeration of $\QQ$ in advance and using it to carry out all back-and-forth constructions.  In other words, we can ensure that the map $L\mapsto\phi_L$ is a Borel assignment. This completes the proof of Theorem~\ref{thm:foreman}.
\end{proof}

\subsection{Local orders and the structures $\bm{S(n)}$}
\label{sec:local}

The class of local orders is closely related to the class of linear orders. A \emph{local order} is a tournament with the property that for every $b$ both $\set{a\in T:a\rightarrow b}$ and $\set{c\in T:b\rightarrow c}$ are linearly ordered by $\to$. As was the case with linear orderings, there is a unique countable homogeneous local order called $\mathcal O$. See Section~6 of \cite{cameron} for more on local orders.

The structure $\mathcal O$ can be realized as one of a family of homogeneous structures $S(n)$, which are defined as follows. Begin with a fixed dense subset $D$ of the unit circle of the complex plane such that for every $x,y\in D$ neither $\arg(x)$ nor $\arg(x/y)$ are rational multiples of $\pi$. For each fixed $n\geq2$, the structure $S(n)$ consists of $n$ binary relations $\to_k$ on $D$ defined by $x\to_ky$ iff $\arg(x/y)\in(2\pi k/n,2\pi(k+1)/n)$. (Of course only $\to_0,\ldots,\to_{\lceil n/2\rceil}$ are formally needed.) Each of the structures $S(n)$ is easily seen to be homogeneous.

Now the local order $\mathcal O$ can be defined from $S(2)$ by letting $x\to_{\mathcal O}y$ iff $x\to_0y$ or $y\to_1x$ for all $x,y\in D$. The structure $S(3)$ also gives rise to a homogeneous digraph on $D$ defined by $x\to y$ iff $x\to_0 y$ or $y\to_2x$. As we shall see in Section~\ref{sec:Digraphs}, the list of homogeneous digraphs does not include any structure corresponding to $S(n)$ for $n>3$.

\begin{thm}\label{thm:Sn}
  Let $n\geq2$. The isomorphism relation on countable linear orders is Borel reducible to the conjugacy relation on $\Aut(S(n))$.  Hence the conjugacy relation on $\Aut(S(n))$ is Borel complete.
\end{thm}

\begin{proof}
  Given a countable linear ordering $L$, we will define an automorphism $\phi_L$ of $S(n)$ in such a way that $L\cong L'$ iff $\phi_L$ and $\phi_{L'}$ are conjugate in $\Aut(S(n))$. Note that we lose no generality in assuming that $L$ has lower and upper endpoints.

  To begin, let $A_k=\set{x\mid 2\pi k/n<\arg(x)<2\pi(k+1)/n}$ denote the $k^\text{th}$ ``arc'' of the unit circle. Since $S(n)\cap A_0$ is naturally linearly ordered by argument value (or $\to_0$), we may let $\alpha_L$ be an embedding from $L$ into $S(n)\cap A_0$ which satisfies the property in Lemma~\ref{lem:perfect}.

  Next let $f$ be the map from the unit circle to $A_0$ defined by $f(x)=xe^{-2\pi k/n}$ whenever $x\in A_k$. Notice that $f$ is one-to-one on the subset $S(n)$, and also that $f(S(n))$ is naturally linearly ordered by argument value. Thus we may define an automorphism $\psi_L$ on $f(S(n))$ with fixed point set exactly $\im(\alpha_L)$, a down-bump below the minimum of $\im(\alpha_L)$, a down-bump above the maximum of $\im(\alpha_L)$, and up-bumps elsewhere.  Finally, we let $\phi_L=f^{-1}\circ\psi_L\circ f$ be the corresponding automorphism of $S(n)$.  Notice that $\phi_L \upharpoonright_{A_0}=\psi_L$.

  By Lemma~\ref{lem:glass}, if $L\cong L'$, then $\psi_L$ is conjugate to $\psi_{L'}$ and it follows that $\phi_L$ is conjugate to $\phi_{L'}$. On the other hand, any $\phi_{L}$ has just two special fixed points which are the endpoints of down-bumps, and we can recover $L$ as the linear order of fixed points that lie between (in circular order) these two special fixed points. Thus using the argument of Theorem~\ref{thm:foreman}, if $\phi_{L'}$ is conjugate to $\phi_L$ we must have $L'\cong L$.
\end{proof}

\section{Undirected graphs}
\label{sec:UndirectedGraphs}

Lachlan and Woodrow \cite{lachlan} classified the countably infinite homogeneous undirected graphs as follows.

\begin{itemize}
\item for $m,n\leq\infty$ and either $m$ or $n$ infinite, the graph $m\cdot K_n$ consisting of $m$ many disjoint copies of $K_n$ (section~\ref{sec:mKn});
\item the generic undirected graph, also known as the random graph (see \cite{summer});
\item for $n<\infty$, the generic $K_n$-free graph (section~\ref{sec:random}), and;
\item graph complements of each of these (they have the same automorphism group).
\end{itemize}

\subsection{Composite undirected graphs}
\label{sec:mKn}

We first show that the classification of automorphisms of $m\cdot K_n$ is smooth when one of $m$ or $n$ is finite.

\begin{thm}\label{thm:Gn}
  If $m,n\leq\infty$ and either $m$ or $n$ is finite, then the conjugacy problem for the automorphism group of $m\cdot K_n$ is smooth.
\end{thm}

Before beginning the proof, observe that each automorphism $\phi\in\Aut(m\cdot K_n)$ acts on the set of copies of $K_n$ by an element $\phi'\in S_m$.  Recall that for $m\leq\infty$ the elements of $S_m$ are determined up to conjugacy by their \emph{cycle type}, that is, the sequence which tells the number of $k$-cycles for each $k\leq\infty$.  The situation is only slightly more complicated for elements of $\Aut(m\cdot K_n)$ since if $k<\infty$, each $k$-cycle of copies of $K_n$ contains an additional piece of information: the permutation of $K_n$ obtained by following the cycle from one copy of $K_n$ all the way around to the start.  More precisely, given $\phi\in\Aut(m\cdot K_n)$ and an $k$-cycle $Y_0,\ldots,Y_{k-1}$ of copies of $K_n$, we can consider $\phi^k\restriction Y_0$ as an element of $S_n=\Aut(Y_0)$. The \emph{twist type} of the cycle $Y_0,\ldots,Y_{k-1}$ is then the conjugacy equivalence class of $\phi^k\restriction Y_0$ in $S_n$.  This is well-defined since $\phi^j$ witnesses that $\phi^k\restriction Y_i$ and $\phi^k\restriction Y_{i+j}$ are conjugate.

\begin{proof}[Proof of Theorem~\ref{thm:Gn}]
  Let us first assume that $m=\infty$ and $n$ is finite. Let $T$ denote the set of conjugacy classes in $S_n=\Aut(K_n)$.  We claim that elements of $\Aut(\infty\cdot K_n)$ are classified up to conjugacy by the following invariants:
  \begin{itemize}
  \item for each $k<\infty$ and $t\in T$, the number of $k$-cycles of copies of $K_n$ with twist type equal to $t$; and
  \item the number of infinite cycles of copies of $K_n$.
  \end{itemize}
  It is easy to see that conjugate automorphisms will possess the same invariants.  Conversely, suppose that $\phi$ and $\psi$ have the same invariants.  Let $Y_0,\ldots,Y_{k-1}$ and $Z_0,\ldots Z_{k-1}$ be cycles of copies of $K_n$ for $\phi$ and $\psi$, respectively, and assume they have the same twist type.  Then there is a bijection $\delta_0\colon Y_0\to Z_0$ which satisfies $\delta_0\circ\phi^k=\psi^k\circ\delta_0$. This implies that it is well-defined to say: extend $\delta_0$ to the entire cycle by letting $\delta(\phi^i(y))=\psi^i\circ\delta_0(y)$ for all $i<k$. Applying the same construction to each cycle, we can define $\delta$ on all of $\infty\cdot K_n$.  (For infinite cycles there is not even any twist type to worry about.)  It is easy to see that this $\delta$ is an automorphism of $\infty\cdot K_n$ and satisfies $\delta\circ\phi=\psi\circ\delta$.

  Next, we consider the case when $m$ is finite and $n=\infty$. In this case the set $T$ of conjugacy classes of $S_\infty=\Aut(K_\infty)$ is uncountable. But since $m$ is finite, each fixed automorphism only mentions a finite set of elements of $T$ as twist types of cycles of copies of $K_\infty$. Thus in this case the elements of $\Aut(m\cdot K_\infty)$ are classified by:
  \begin{itemize}
  \item the finite subset $T_0\subset T$ of elements realized as the twist type of some cycle of copies of $K_\infty$, and;
  \item for each $k<\infty$ and $t\in T_0$, the number of $k$-cycles of copies of $K_\infty$ with twist type equal to $t$.
  \end{itemize}
  It is easy to show that a finite subset of $T$ can be coded by a single real number (for this, use a fixed linear ordering of $T$ to enumerate the finite set, and then use any Borel bijection $\bigcup_{i<\omega} T^i\to\RR$). Thus this is once again a smooth classification.
\end{proof}

Although the situation when $m=n=\infty$ is similar, in this case each automorphism may mention countably many elements from the uncountable set $T$ of twist types. This turns out to be at a higher level of complexity than the smooth relations, but still lower than the Borel complete relations. In this way the following result is unique among all the results in this paper.

Before stating the result, we let $E_\sset$ denote the equivalence relation on $\RR^\omega$ given by $\sigma\mathrel{E_\sset}\tau$ iff $\sigma$ and $\tau$ enumerate the same countable set. The Borel complexity of $E_\sset$ is known to lie properly in between the smooth and Borel complete complexities (see for example \cite{gao}, Chapter~8, where $E_\sset$ is denoted $=^+$).

\begin{thm}\label{thm:Ginfty}
  The conjugacy problem for the automorphism group of the graph $\infty\cdot K_\infty$ is bireducible with $E_\sset$.
\end{thm}

\begin{proof}
  Again let $T$ denote the set of conjugacy classes in $S_\infty=\Aut(K_\infty)$. The arguments of the previous proof imply that elements of $\Aut(\infty\cdot K_\infty)$ are classified by:
  \begin{itemize}
  \item the subset $T_0\subset T$ of elements realized as the twist type of some finite cycle of copies of $K_\infty$;
  \item for each $k<\infty$ and $t\in T_0$, the number of $k$-cycles of copies of $K_\infty$ with twist type equal to $t$; and
  \item the number of infinite cycles of copies of $K_\infty$.
  \end{itemize}
  We must verify that this implies the conjugacy problem for $\Aut(\infty\cdot K_\infty)$ is Borel bireducible with $E_\sset$. To see that the conjugacy problem is Borel reducible to $E_\sset$, note that we can code the invariant above by the countable subset of $T\times(\NN\cup\{\infty\})^3$. Indeed, given $\phi$, form the set of all $(t,k,l,i)$ where $t$ is a twist type occurring in $\phi$, $k\in\NN$, $l$ is the number of $k$-cycles of copies of $K_n$ with twist type equal to $t$, and $i$ is the number of infinite cycles of copies of $K_\infty$.

  We next reduce $E_\sset$ to the conjugacy problem for $\Aut(\infty\cdot K_\infty)$ as follows. Given a countable subset $T_0\subset T$, we form an automorphism $\phi$ of $\infty\cdot K_\infty$ which has infinitely many $2$-cycles of copies of $K_\infty$, no other cycles, and such that each $t\in T_0$ appears exactly once as a twist type.
\end{proof}

\subsection{Random graphs}
\label{sec:random}

In this section we discuss the generic graph, known as the \emph{random graph} $\Gamma$, as well as the generic  $K_n$-free graph denoted $\Gamma_n$. Here if $\mathcal C$ is a class of finite graphs (or digraphs, or relational structures) we say $G$ is \emph{generic} for the class $\mathcal C$ if $G$ is homogeneous and the set of finite substructures of $G$ is exactly $\mathcal C$. The classes $\mathcal C$ which admit a generic object are characterized by the well-known Fra\"iss\'e theory.

When dealing with generic objects, we will often use the following characterization, known as the \emph{one-point extension property}. This states that $G$ is generic for the class $\mathcal C$ if and only if every finite subset $S\subset G$ lies in $\mathcal C$, and whenever $S\cup\{x\}$ lies in $\mathcal C$ there is some $a\in G$ such that the identity function on $S$ extends to an isomorphism $S\cup\{x\}\cong S\cup\{a\}$.

In the article \cite{summer} we showed with Scott Schneider that the conjugacy problem for $\Aut(\Gamma)$ is Borel complete. The next result gives a streamlined version of the argument from \cite{summer}, and at the same time generalizes it to work for $\Aut(\Gamma_n)$ too.

\begin{thm}\label{thm:graphs}
  The isomorphism relation for countable $K_n$-free graphs is Borel reducible to the conjugacy problem for $\Aut(\Gamma_n)$. Hence the conjugacy problem for $\Aut(\Gamma_n)$ is Borel complete.
\end{thm}

\begin{proof}
  Given a countable $K_n$-free graph $G$, we construct a copy $\Delta_G$ of $\Gamma_n$ together with an automorphism $\phi_G$ of $\Delta_G$. It is enough to show that $G\cong G'$ iff $\phi_G$ and $\phi_{G'}$ are conjugate by an isomorphism $\Delta_G\cong\Delta_{G'}$.

  To begin, let $\Delta_G^0$ consist of two disjoint copies of $G$, with each vertex adjacent to the corresponding vertex in the other copy. Also, let $\phi_G^0$ be the automorphism of $\Delta_G^0$ which exchanges corresponding vertices from the two copies of $G$.

  Next suppose $\Delta_G^k$ and $\phi_G^k$ have been constructed and define $\Delta_G^{k+1}\supset\Delta_G^k$ as follows. For each finite subset $S\subset \Delta_G^k$ which does not contain a copy of $K_{n-1}$, we place a point $x$ into $\Delta_G^{k+1}$ which is adjacent to every vertex of $S$ and no other vertices in $\Delta_G^{k+1}$. Then let $\phi_G^{k+1}$ be the unique extension of $\phi_G^k$ to $\Delta_G^{k+1}$.

  To complete the construction, we let $\Delta_G=\bigcup\Delta_G^k$ and $\phi_G=\bigcup\phi_G^k$. It is clear that $\Delta_G$ has the one-point extension property relative to the class of $K_n$-free graphs and hence that it is a copy of $\Gamma_n$. Moreover, if $G\cong G'$ then this extends to an isomorphism $\Delta_G^0\cong\Delta_{G'}^0$, and this uniquely extends layer-by-layer to an isomorphism $\alpha\colon\Delta_G\cong\Delta_{G'}$. It is easy to verify that this isomorphism satisfies $\alpha\phi_G=\phi_{G'}\alpha$.

  For the converse, first note from the construction that if $x$ lies in $\Delta_G^0$ then $x$ is adjacent to $\phi_G(x)$, while if $x$ lies in some $\Delta_G^{k+1}\smallsetminus\Delta_G^k$ then so does $\phi_G(x)$ and hence $x$ is \emph{not} adjacent to $\phi_G(x)$. Thus if we are given $\phi_G$ we can recover $\Delta_G^0$ as the set of vertices $x$ such that $x$ is adjacent to $\phi_G(x)$. And we can further recover $G$ as the quotient graph of $\Delta_G^0$ by the orbit equivalence relation on $\phi_G$.

  Now if $\alpha\colon\Delta_G\cong\Delta_{G'}$ and $\alpha\phi_G=\phi_{G'}\alpha$ it follows that $\alpha$ restricts to an isomorphism $\Delta_G^0\cong\Delta_{G'}^0$ that sends $\phi_G$-orbits to $\phi_{G'}$-orbits. Therefore by passing to the quotient graphs of $\Delta_G^0,\Delta_{G'}^0$ by the $\phi_G$ and $\phi_{G'}$-orbit equivalence relations, we see that $\alpha$ induces an isomorphism  $G\cong G'$.

  To conclude, we remark briefly on how the construction can be exhibited in a Borel fashion. We fix the underlying sets of $G,\Delta_G,\Gamma_n$ to be $\NN$. The construction of $\Delta_G$ can be made Borel by reserving an infinite subset $I_k\subset\NN$ for each $\Delta_G^k$, and using a previously fixed enumeration of the finite subsets $S\subset I_k$. This immediately implies that the construction of $\phi_G$ is Borel also. Finally we can regard $\phi_G$ as an automorphism of $\Gamma_n$ using a back-and-forth construction between $\Delta_G$ and $\Gamma_n$, where each choice in the construction is resolved by choosing the least available witness.
\end{proof}

\section{Digraphs}
\label{sec:Digraphs}

For us, the terms \emph{directed graph} and \emph{digraph} both mean an antisymmetric and irreflexive binary relation (a Graph Theorist\texttrademark\ would use the term \emph{oriented graph}). The countable homogeneous digraphs have been classified by Cherlin \cite{cherlin}. The following catalog of these digraphs also serves as a table of contents for this section.

\begin{itemize}
\item We have already mentioned $\QQ$, $S(2)$, and $S(3)$, which can all be viewed as digraphs (sections~\ref{sec:linear} and~\ref{sec:local})
\item The generic tournament $\mathcal T$ (section~\ref{sec:tournament})
\item Generic independent set avoiding digraphs $\Lambda_n$ (section~\ref{sec:tournament})
\item Compositions of certain tournaments with $I_n$ (section~\ref{sec:composite})
\item Slight modifications of certain tournaments $\hat T$ (section~\ref{sec:hat})
\item Generic tournament-avoiding digraphs $\Gamma_{\mathcal F}$ (section~\ref{sec:Tfree})
\item Generic complete multipartite digraphs (section~\ref{sec:multipartite})
\item Semigeneric multipartite digraph \cite{cherlin-imprimitive} (not treated)
\item Generic partial order $\mathcal P$ (not treated)
\item Shuffled generic partial order $P(3)$ (not treated)
\end{itemize}

There are also several finite examples, but the conjugacy problems for their automorphism groups are all clearly smooth.

\subsection{The random tournament and universal $I_n$-free digraphs.}
\label{sec:tournament}

There is a generic countable tournament $\mathcal T$, sometimes also called the \emph{random tournament}.

\begin{thm}\label{thm:tournament}
  The isomorphism relation for countable tournaments is Borel reducible to the conjugacy problem for $\Aut(\mathcal T)$. Hence the conjugacy problem for $\Aut(\mathcal T)$ is Borel complete.
\end{thm}

\begin{proof}
  We employ a similar method to the proof of Theorem~\ref{thm:graphs}, adapting some of the combinatorial details to this situation. Given a countable tournament $T$ we again construct a copy $\Delta_T$ of $\mathcal T$ together with an automorphism $\phi_T$ of $\Delta_T$ in such a way that $T\cong T'$ iff $\phi_T$ is conjugate to $\phi_{T'}$. As before, the construction can easily be checked to be Borel.

  To begin, we let $\Delta_T^0$ consist of \emph{three} copies of $T$, where for each vertex $x\in T$ we place three vertices $x_0,x_1,x_2$ into $\Delta_T^0$ with $x_0\to x_1\to x_2\to x_0$. For each edge $x\to y$ of $T$ we place the nine edges $x_i\to y_j$ into $\Delta_T^0$. We then let $\phi_T^0$ be the automorphism of $\Delta_T^0$ that maps the vertices of $\Delta_T^0$ in the fashion $x_0\mapsto x_1\mapsto x_2\mapsto x_0$ so that in all cases $x_i\to \phi_T^0(x_i)$.

  Now suppose that $\Delta_T^k$ and $\phi_T^k$ have been constructed and define $\Delta_T^{k+1}$ as follows. For each finite subset $S\subset\Delta_T^k$ we place a vertex $x$ into $\Delta_T^{k+1}$ such that $s\to x$ for all $s\in S$ and $a\leftarrow x$ for all $a\in\Delta_T^k\smallsetminus S$. Then there is a unique automorphism $\phi_T^{k+1}$ of $\Delta_T^{k+1}$ which extends $\phi_T^k$.

  We still need to add edges within $\Delta_T^{k+1}\smallsetminus\Delta_T^k$ to make $\Delta_T^{k+1}$ a tournament. First, within each nontrivial $\phi_T^{k+1}$-orbit of $\Delta_T^{k+1}\smallsetminus\Delta_T^k$ we make a copy of $C_3$ by adding the edges $x\leftarrow\phi_T^{k+1}(x)$.  Second, if $\{x_i\}$ and $\{y_j\}$ are distinct $\phi_T^{k+1}$-orbits within $\Delta_T^{k+1}\smallsetminus\Delta_T^k$, we either add all the edges $x_i\to y_j$ or all the edges $x_j\leftarrow y_j$.  This choice can be made systematic, for example, by referring to a previously fixed well-order of the finite subsets $S\subset\Delta_T^k$. We can then add all the edges $x_i\to y_j$  if the least representative $S_{x_i}$ is earlier in this well-order than the least representative $S_{y_j}$.

  It is easy to see that if $T\cong T'$ then $\phi_T$ is conjugate to $\phi_{T'}$. Moreover given $\phi_T$, we can recover $\Delta_T^0$ as the set of vertices $x$ such that $x\to\phi_T(x)$. It follows that we can conclude exactly as in the proof of Theorem~\ref{thm:graphs}.
\end{proof}

Just as the random graph $\Gamma$ admitted a family of $K_n$-free generalizations $\Gamma_n$, the random tournament $\mathcal T$ admits a family of $I_n$-free generalizations $\Lambda_n$. (Here, recall that $I_n$ denotes an edgeless graph with $n$ vertices.) With this notation, $\Lambda_2$ is just $\mathcal{T}$ itself.

\begin{thm}\label{thm:I_n-free digraphs}
  For all $n\geq2$, the conjugacy problem for $\Aut(\Lambda_n)$ is Borel complete.
\end{thm}

\begin{proof}
  We explain how to modify the previous proof to work for this family of graphs. Once again suppose that $T$ is a tournament and that $\Delta_T^k$ and $\phi_T^k$ have been constructed. This time, for each pair of finite subsets $S,S'\subset\Delta_T^k$ such that $S'$ does not contain an independent set of size $n-1$, we add a vertex $x$ to $\Delta_T^{k+1}$ such that $s\to x$ for all $s\in S$, $s$ is not adjacent to $x$ for all $s\in S'$, and $a\leftarrow x$ for all $a\in\Delta_T^{k+1}\smallsetminus(S\cup S')$. In this way we realize all types over $\Delta_T^k$ that do not violate the $I_n$-free property.

  The remainder of the construction of $\Delta_T$ and $\phi_T$ is the same as before. Then we can similarly argue that $\Delta_T$ is a copy of $\Lambda_n$, $\phi_T$ is an automorphism of $\Delta_T$, and the map $T\mapsto\phi_T$ gives a Borel reduction from isomorphism of $I_n$-free graphs to conjugacy in $\Aut(\Delta_T)=\Aut(\Lambda_n)$.
\end{proof}

\subsection{Composite digraphs}
\label{sec:composite}

For any graph $G$ and $n\leq\infty$, we let $n\cdot G$ denote the graph with $n$ disjoint copies of $G$. We also let $G[n]$ denote $G$ with each vertex replaced by an independent set of size $n$, where the edges between the independent sets are determined by the edges of $G$. Then there are eight classes of homogeneous composite digraphs:

\begin{itemize}
\item $\infty\cdot C_3$,\ \ \ $C_3[\infty]$
\item $n\cdot\QQ$,\ \ \ $\QQ[n]$
\item $n\cdot S(2)$,\ \ \ $S(2)[n]$
\item $n\cdot\mathcal T$,\ \ \ $\mathcal T[n]$
\end{itemize}

The following result settles the complexity of the conjugacy problem for the automorphism groups of each of these digraphs.

\begin{thm}
  \begin{itemize}
  \item The conjugacy problems for $\Aut(\infty\cdot C_3)$ and $\Aut(C_3[\infty])$ are both smooth.
  \item The conjugacy problems for the remaining digraphs in the list above are all Borel complete. Indeed, if $G$ is a tournament and the conjugacy problem for $\Aut(G)$ is Borel complete, then the conjugacy problems for $\Aut(n\cdot G)$ and $\Aut(G[n])$ are Borel complete.
  \end{itemize}
\end{thm}

\begin{proof}
  To show that $\Aut(\infty\cdot C_3)$ is smooth, we can use an argument identical to the one in Theorem~\ref{thm:Gn}. Here, the ``twist types'' are simply the three elements of $\Aut(C_3)$. The argument for $\Aut(C_3[\infty])$ is similar, since any element of $\Aut(C_3[\infty])$ acts on the copies of $I_\infty$ by an automorphism of $C_3$. And as with the previous argument, each cycle of copies of $I_\infty$ has an associated ``twist type'' which is a conjugacy class of $S_\infty=\Aut(I_\infty)$.

  Next, if conjugacy in $\Aut(G)$ is Borel complete, let $\phi\oplus\mathrm{id}$ denote the automorphism of $n\cdot G$ which acts by $\phi$ on the first copy of $G$ and trivially on the remaining copies. Then it is easy to see that since $G$ is connected, the map $\phi\mapsto\phi\oplus\mathrm{id}$ is a reduction from conjugacy in $\Aut(G)$ to conjugacy in $\Aut(n\cdot G)$.

  Finally, we let $\phi[n]$ denote the automorphism of $G[n]$ which acts by $\phi$ on the copies of $I_n$ and acts trivially within copies of $I_n$. Once again, it is easy to check that since $G$ is a tournament the map $\phi\mapsto\phi[n]$ is a reduction from conjugacy in $\Aut(G)$ to conjugacy in $\Aut(G[n])$.
\end{proof}

We conjuncture that the above result may be strengthened, either by weakening the hypotheses on the graph $G$ or by generalizing it to a larger class of countable structures.

\subsection{Hat graphs}
\label{sec:hat}

Given a tournament $T$, we define $\hat T$ as follows: let $a$ be a new point and let $\hat T$ initially consist of two disjoint copies of $a\to T$, call them $a\to T$ and $\bar{a}\to\bar{T}$. Given points $x\in T\cup\{a\}$ and $y\in\bar{T}\cup\{\bar{a}\}$, we let $x\to\bar{y}$ if $x\leftarrow y$ and $x\leftarrow\bar{y}$ if $x\to y$.

The automorphism group of $\hat T$ is generated by $\Aut(T)$ together with a rather trivial automorphism swapping the two copies.  If $T$ is infinite, then the graph $\hat T$ is homogeneous in only two cases: $T=\QQ$ and $T=\mathcal{T}$.  In each of these cases, the conjugacy relation is Borel complete, and it follows that the conjugacy relation in $\hat T$ is also Borel complete.

\subsection{Generic tournament-avoiding digraphs}
\label{sec:Tfree}

While the random graph $\Gamma$ had generic $K_n$-free variants $\Gamma_n$, the generic countable digraph has a family of continuum many variants. For any family $\mathcal{F}$ tournaments (each of size $\geq3$), we say that a directed graph $G$ is \emph{$\mathcal{F}$-free} if it does not contain a copy of any element of $\mathcal F$. For each such family $\mathcal{F}$ there is a universal countable homogeneous such graph $\Gamma_{\mathcal{F}}$. In the case that $\mathcal{F}=\emptyset$, the resulting graph $\Gamma_{\mathcal{F}}$ is simply called the \emph{random digraph}.

\begin{thm}\label{thm:digraphs}
  If $\mathcal{F}$ is a family of tournaments of size $\geq3$, then the isomorphism problem for the class of $\mathcal F$-free digraphs is Borel reducible to the conjugacy problem for $\Aut(\Gamma_{\mathcal{F}})$.  Hence the conjugacy problem for $\Aut(\Gamma_{\mathcal{F}})$ is Borel complete.
\end{thm}

\begin{proof}
  We combine the arguments in the proofs of Theorems~\ref{thm:graphs} and \ref{thm:tournament}. Given a countable $\mathcal{F}$-avoiding digraph $G$ we construct a copy $\Delta_G$ of $\Gamma_{\mathcal F}$ and an automorphism $\phi_G$ of $\Delta_G$. This time we let $\Delta_G^0$ consist of \emph{four} copies of $G$, where for each $x\in G$ we place vertices $x_0,\ldots,x_3$ into $\Delta_G^0$ with $x_0\to x_1\to x_2\to x_3\to x_0$. For each edge $x\to y$ in $G$ we place the four edges $x_i\to y_i$ into $\Delta_G^0$. Note that the only tournaments in $\Delta_G^0$ are those already present in $G$. We then let $\phi_G^0$ be the automorphism of $\Delta_G^0$ that maps $x_0\mapsto\cdots\mapsto x_3\mapsto x_0$ so that in all cases $x_i\to\phi_G^0(x_i)$.

  Now suppose that $\Delta_G^k$ and $\phi_G^k$ have been constructed and define $\Delta_G^{k+1}$ and $\phi_G^{k+1}$ as follows. For each finite subset $S\subset\Delta_G^k$ we provisionally place a vertex $x$ into $\Delta_G^{k+1}$ such that $s\to x$ for all $s\in S$ and $a\leftarrow x$ for all $a\in\Delta_G^k\smallsetminus S$. However, if doing so would create a copy of some $T\in\mathcal{F}$, we simply skip adding the element $x$ instead. As in the proof of Theorem~\ref{thm:tournament}, we let $\phi_G^{k+1}\supset\phi_G^k$ be the unique extension to an automorphism of $\Delta_G^{k+1}$, and add edges within the $\phi_G^{k+1}$-orbits of $\Delta_G^{k+1}\smallsetminus\Delta_G^k$ in such a way that each nontrivial orbit is a copy of $C_4$ where $x\leftarrow\phi_G^{k+1}(x)$. The conclusion of the proof is now the same as in the proof of Theorem~\ref{thm:tournament}.
\end{proof}

\subsection{Generic complete $n$-partite digraphs}
\label{sec:multipartite}

A digraph is said to be \emph{complete $n$-partite} if it is $n$-partite and has a maximal set of edges.  For each $2\leq n\leq\infty$, there exists a generic such graph, which we denote $n*I_\infty$.

\begin{thm}
  The isomorphism problem for countable tournaments is Borel reducible to conjugacy problem for $\Aut(n*I_\infty)$. Hence the conjugacy problem for $\Aut(n*I_\infty)$ is Borel complete.
\end{thm}

\begin{proof}
  We begin by treating the special case when $n=2$.  Given a tournament $T$, we build a copy $\Delta_T$ of $2*I_\infty$ and an automorphism $\phi_T$ of $\Delta_T$ as follows. We let $\Delta_T^0$ consist of four copies of $T$, where for each vertex $x\in T$ we place four vertices $x_0,\ldots,x_3$ into $\Delta_T^0$ with edges $x_0\to\cdots\to x_3\to x_0$. For each edge $x\to y$ of $T$ we place \emph{eight} edges $x_{2i}\to y_{2j+1}$ and $x_{2i+1}\to y_{2j}$ into $\Delta_T^0$ (this is depicted in Figure~\ref{fig:bipartite}). Since $T$ is a tournament, we have that $\Delta_T^0$ is a complete bipartite graph. Next we let $\phi_T^0$ be the automorphism of $\Delta_T^0$ that maps the vertices of $\Delta_T^0$ in the fashion $x_0\mapsto\cdots\mapsto x_3\mapsto x_0$, so that in all cases we have $x_i\to\phi_T^0(x_i)$.

  \begin{figure}[h]
    \centering
    \begin{tikzpicture}[->]
      \node (x) at (-6,0) {$x$};
      \node (y) at (-4,0) {$y$};
      \draw[->] (x)--(y);
      \node at (-2.5,0) {becomes};
      \node (x0) at (-1,1) {$x_0$};
      \node (x1) at (1,1) {$x_1$};
      \node (x2) at (-1,.5) {$x_2$};
      \node (x3) at (1,.5) {$x_3$};
      \node (y0) at (-1,-.5) {$y_0$};
      \node (y1) at (1,-.5) {$y_1$};
      \node (y2) at (-1,-1) {$y_2$};
      \node (y3) at (1,-1) {$y_3$};
      \draw (x0)--(x1);\draw (x1)--(x2);\draw (x2)--(x3);\draw (x3)--(x0);
      \draw (y0)--(y1);\draw (y1)--(y2);\draw (y2)--(y3);\draw (y3)--(y0);
      \draw[-,shorten >=2pt,double,double distance=2.4pt] (-.4,.4) -- (.4,-.4);
      \draw[double] (-.4,.4) -- (.4,-.4);
      \draw[-,shorten >=2pt,double,double distance=2.4pt] (.4,.4) -- (-.4,-.4);
      \draw[double] (.4,.4) -- (-.4,-.4);
    \end{tikzpicture}
    \caption{The construction of $G_0$ from $T$.\label{fig:bipartite}}
  \end{figure}

  Now suppose that $\Delta_T^k$ and $\phi_T^k$ have been constructed and inductively suppose that $\Delta_T^k$ consists of two maximal independent sets $A_0$ and $A_1$. We build extensions $\Delta_T^{k+1}\supset\Delta_T^k$ and $\phi_T^{k+1}\supset\phi_T^k$ as follows. For each $A_i$ and each finite subset $S\subset A_{1-i}$, we put a new point $x$ into $\Delta_T^{k+1}$ such that $s\to x$ for all $s\in S$ and $a\leftarrow x$ for all $a\in A_{1-i}\smallsetminus S$. As usual we let $\phi_T^{k+1}$ be the unique extension of $\phi_T^k$ to $\Delta_T^{k+1}$. We then add edges within each $\phi_T^{k+1}$-orbit in $\Delta_T^{k+1}\smallsetminus\Delta_T^k$ so as to ensure $x\leftarrow\phi_T^{k+1}(x)$ always holds. Finally, we fill in the remaining edges between the $\phi_T^{k+1}$-orbits in $\Delta_T^{k+1}\smallsetminus\Delta_T^k$ similarly to the proof of Theorem~\ref{thm:tournament}. More specifically, if $\{x_i\}$ and $\{y_i\}$ are distinct $\phi_T^{k+1}$-orbits then we add all the edges from $\{x_i\}\cap A_0$ to $\{y_i\}\cap A_1$ and from $\{x_i\}\cap A_1$ to $\{y_i\}\cap A_0$, or else the opposite, in any systematic way. The conclusion of the proof when $n=2$ is now just the same as in the proof of Theorem~\ref{thm:tournament}.

  We now briefly say how to modify the above argument in the case when $n>2$. This time we inductively suppose that $\Delta_T^k$ and $\phi_T^k$ have been constructed and $\Delta_T^k$ consists of $n$ maximal independent sets $A_i$ for $0\leq i<n$. (In the step $k=1$, the $A_i$ will be empty for $2\leq i<n$.) We define $\Delta_T^{k+1}$ as follows: for each $i$ and each finite subset $S\subset\Delta_T^{k}$ that does not meet $A_i$ we add a new point $x$ to $A_i$ such that $s\to x$ for all $s\in S$ and $a\leftarrow x$ for all $a\in\Delta_T^k\smallsetminus(S\cup A_i)$. We then make $\Delta_T^{k+1}\smallsetminus\Delta_T^k$ complete $n$-partite by proceeding as in the case when $n=2$ within $A_0\cup A_1$, and additionally adding edges from $A_i$ to $A_j$ for $i<j$ when $2\leq j$. This guarantees that there is a unique extension to $\phi_T^{k+1}\supset \phi_T^k$ to $\Delta_T^{k+1}$ that interchanges $A_0$ and $A_1$ and preserves $A_i$ for $i\geq2$. The rest of the proof is the same as above.
\end{proof}

\bibliographystyle{alpha}
\begin{singlespace}
  \bibliography{summer,conjugacy}
\end{singlespace}

\end{document}

config: arxiv


TITLE: How to solve $1+2^{a}+2^{2a+1}=b^2$
QUESTION [0 upvotes]: I want to find all integer solutions for $1+2^{a}+2^{2a+1}=b^2$. How could I do this?

REPLY [8 votes]: When $a\le -1$, $1<1+2^a+2^{2a+1}\le 2$, no solution.
When $a=0$, $b=\pm 2$.
When $a\ge 1$, from
$$(2^a+1)^2<b^2=1+2^a+2^{2a+1}<(2^a+2^{a-1}+1)^2$$
we know that $|b|=2^a+k$ for some integer $k$ satisfying $2\le k\le 2^{a-1}$.
Since
$$1+2^a+2^{2a+1}=(2^a+k)^2\Rightarrow 2^a\mid (k-1)(k+1)$$
and since $\gcd(k-1, k+1)\le 2$, we know that either $2^{a-1}\mid (k-1)$ or $2^{a-1}\mid (k+1)$. However, since $2\le k\le 2^{a-1}$, the only possible case is $k=2^{a-1}-1$.
Then
$$1+2^a+2^{2a+1}=(2^a+2^{a-1}-1)^2\iff a=4.$$
Therefore, when $a\ge 1$, $a=4$ and $b=\pm 23$.


TITLE: Can you find such a function? $\lim_{x \to \infty} \frac{f'(x)}{g'(x)}$ doesnt exist
QUESTION [1 upvotes]: We want to find two functions $f,g$ such that $\lim_{x \to \infty} f(x)=\lim_{x\to \infty}g(x) = \infty$, $\lim_{x \to \infty} \frac{f(x)}{g(x)} = 10$, but $\lim_{x \to \infty} \frac{f'(x)}{g'(x)}$ doesnt exist.
I'm having difficulties coming up with an answer. I can't really tell you what I tried since all I did was try and come up with functions that maybe could somehow satisfy this, just guessing, failed so far. Would appreciate a hint in the right direction or the answer.

REPLY [0 votes]: Hint: Let $g$ by linear and $f$ be linear $+$ an oscillation terms that is small in value, but not in derivative.


TITLE: Dimension of Range and Null Space of Composition of Two Linear Maps
QUESTION [6 upvotes]: Question
Suppose $U$, $V$ and $W$ are finite-dimensional vector spaces. Let $\mathcal{L}(U,V)$ and $\mathcal{L}(V,W)$ be the vector spaces of all linear maps from $U$ into $V$ and from $V$ into $W$, respectively. Suppose $S \in \mathcal{L}(V,W)$ and $T \in \mathcal{L}(U,V)$. Then prove that
$\begin{align}
& 1. \, \text{dim null} S \circ T \le \text{dim null} S + \text{dim null} T \\
& 2. \, \text{dim range} S \circ T \le \text{min} \{ \text{dim range} S , \text{dim range} T \}
\end{align}$
My Thought
To prove the first one, I guess that writing the fundamental theorem of linear maps for $S \circ T$ may be a good start
$$\begin{align}
\text{dim null} S \circ T &= \text{dim} U - \text{dim range} S \circ T \\
&= \text{dim null} T + \text{dim range} T - \text{dim range} S \circ T \\
&\le \text{dim null} T + \text{dim} V - \text{dim range} S \circ T \\
&= \text{dim null} T + \text{dim null} S + \text{dim range} S- \text{dim range} S \circ T
\end{align}$$
So if I can prove that
$$\text{dim range} S- \text{dim range} S \circ T \le 0$$
then I am done but this does not seem to be true because it is easy to see that $\text{range} S \circ T \subseteq  \text{range} S$ and hence
$\text{dim range} S \circ T \le \text{dim range} S$
. So I am stuck!
Also, I could observe that $\text{null} T \subseteq \text{null} S \circ T$ and hence
$\text{dim null} T  \le \text{dim null} S \circ T$
but I don't know how to use this!

REPLY [7 votes]: Fo the first question, I would argue like this: let $K = \mathrm{null}(ST) = T^{-1}(\mathrm{null}(S))$, a subspace of $U$, and let $T|_{K} : K \to V$ be the restriction of $T$ to $K$. Because
\begin{align*}
\mathrm{null}(T|_{K}) \subset \mathrm{null}(T) && \text{and} &&\mathrm{ran}(T|_{K}) \subset \mathrm{null}(S)
\end{align*}
we get
\begin{align*}
\dim(\mathrm{null}(ST))
&= \dim(K)  \\
&= \dim(\mathrm{null}(T|_{K})) + \dim(\mathrm{ran}(T|_{K})) \\
&\leq \dim(\mathrm{null}(T))  + \dim(\mathrm{null}(S))
\end{align*}
as desired.
For your second question, note what you need to do is prove (i) $\dim(\mathrm{ran}(ST))≤\dim(\mathrm{ran}(S))$ and (ii) $\dim(\mathrm{ran}(ST))≤\dim(\mathrm{ran}(T))$. I think you can probably see why (i) is true. For (ii), note that $ST$ has the same range as $S|_{\mathrm{ran}(T)}$, and that the range of a linear tranformation has equal or lesser dimension than the domain