\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{array}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Counting Unlabelled Topologies and\\
\vskip .1in
Transitive Relations}
\vskip 1cm
\large
Gunnar~Brinkmann\\
Applied Mathematics and Computer Science\\
Ghent University\\
B--9000 Ghent \\
Belgium\\
\href{mailto:Gunnar.Brinkmann@ugent.be}{\tt Gunnar.Brinkmann@ugent.be}
\\
\ \\
Brendan~D.~McKay\footnote{Research supported by the Australian Research Council.}\\
Department of Computer Science\\
Australian National University\\
Canberra ACT 0200 \\
Australia\\
\href{mailto:bdm@cs.anu.edu.au}{\tt bdm@cs.anu.edu.au}
\end{center}

\vskip .2in

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\usepackage{amsmath,amsthm,amssymb}
% \usepackage{pdfsync}

%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
%\newtheorem{definition}{Definition}

\def\Aut{\operatorname{Aut}}
\def\abs#1{\mathopen|#1\mathclose|}

\def\({\bigl(}
\def\){\bigr)}
\def\twid{$\scriptstyle\sim $}

%\maketitle

\begin{abstract}
 We enumerate isomorphism classes of several types of transitive
 relations (equivalently, finite topologies) up to 15 or 16 points.  
\end{abstract}

\section{Introduction}
Pfeiffer~\cite{pf} presented a classification of various types
of order relations and determined their numbers up to~12 points.
In this paper, we extend the counts to 15 or 16 points. We defer
to~\cite{pf} for historical survey, and only give enough background
to precisely define the objects we are counting.

We consider only directed graphs (digraphs) that do not have
multiple edges but may have up to one loop per point. A {\it
transitive relation digraph (TRD)\/} is a digraph such that presence
of edges $(x,y)$ and $(y,z)$ implies that $(x,z)$ is also present (even
if $x,y,z$ are not distinct). (We cannot use the more natural term
``transitive digraph'' since its most common definition does not allow
loops; this has the unfortunate consequence that transitive digraphs
don't correspond to transitive relations.)

A {\it strong
component\/} of a digraph is a maximal set of points $P$ such that
there is a directed path within $P$ from $x$ to $y$ for
each pair $x,y\in P$.  (This permits the zero-length path from $x\in P$ to
itself.) 

If a strong component of a TRD has only
one point, there may or may not be a loop on that point. However,
larger strong components of a TRD have loops
on every point and edges in both directions between each pair of
points. If the strong components of a TRD
are contracted to single points, the result is a TRD
that has no directed cycles apart from loops.

Two digraphs are {\it isomorphic\/} if there is a bijection between their
point-sets that induces a bijection between their edge-sets.  Thus we
can refer to {\it isomorphism classes\/} of digraphs.

Of course a digraph can be viewed as representing some kind of
order relation $\le$, where $x\le y$ iff there is an edge $(x,y)$.
In the language and notation of Pfeiffer, we have the following
correspondences:
\begin{itemize}\addtolength{\itemsep}{-0.4\baselineskip}
\item A {\it transitive relation\/} corresponds to an arbitrary TRD.
  Let $t(n)$ be the number of isomorphism classes of transitive relations.
  This is Sloane's sequence \seqnum{A091073}.
\item A {\it quasi-order\/} corresponds to a TRD
  such that every single-point strong component has a loop.
  Let $q(n)$ be the number of isomorphism classes of quasi-orders.
  This is Sloane's sequence \seqnum{A001930}.
\item A {\it soft order\/} corresponds to a TRD
  whose strong components each have only one point (with or
  without loop). Let $s(n)$ be the number of isomorphism classes
  of soft orders.  This is Sloane's sequence \seqnum{A079265}.
  \item A {\it partial order\/} corresponds to an
  TRD whose strong components are all
  single points with loops. Because we can remove and replace the
  loops in a unique fashion, the counts here are the same as for
  acyclic TRDs. Let $p(n)$ be the number of
  isomorphism classes of partial orders. \end{itemize}

There are also relationships with finite topologies: general topologies are
in bijective correspondence with quasi-orders, and $T_0$-topologies
are in bijective correspondence with partial orders.  These bijections
preserve isomorphism, so we are also counting isomorphism classes of
topologies.

\medskip

For enumerative purposes, we will define some specialized numbers.
\begin{itemize}\addtolength{\itemsep}{-0.4\baselineskip}
\item $q(n,m)$ is the number of isomorphism classes of TRDs
    with $n$ points and $m$ strong components, such that each single-point
    strong component has a loop.
\item $t(n,m)$ is the number of isomorphism classes of TRDs
    with $n$ points and $m$ strong components (with single-point strong
    components having a loop or not).
\end{itemize}

In terms of these specialized numbers, we have
\begin{align*}
   q(n) &= \sum_{m=1}^n q(n,m), &
   t(n) &= \sum_{m=1}^n t(n,m),\\[0.4ex]
   p(n) &= q(n,n), &
   s(n) &= t(n,n).
\end{align*}

\section{Computing $t(n,m)$ and $q(n,m)$ for small $n$}

Our main tool is a program which generates non-isomorphic partially
ordered sets ({\it posets\/}).  In our paper~\cite{posets}, we gave values
of $p(n)$ up to $n=16$ based on output from that program.

Given a poset $P$, we can make a TRD $G$ by replacing
each point by a directed clique (perhaps of a single point).
Such directed cliques become the strong components of~$G$.
If~points $v,w$ of $P$ become strong components $c_v,c_w$ of $G$,
then an edge $(v,w)$ of $P$ becomes the set of all possible edges from
$c_v$ to $c_w$ in~$G$.  Clearly non-isomorphic posets lead to
non-isomorphic TRDs, since $G$ uniquely determines~$P$.
The only remaining issue is that some of the TRDs made
from $P$ may be isomorphic due to symmetries (automorphisms) of~$P$.

Given a poset $P$, we can represent its expansion to a TRD
by assigning a positive integer {\it weight\/} to each point.
This weight corresponds to the size of the directed clique that the point
will be expanded to.   We also consider {\it extended weights\/} where there
are two types of weight with value~1 (corresponding to loop and non-loop).

For any permutation $\gamma$, define
\begin{align*}
C_\gamma(x) &= \prod_{i=1}^k\, (1 - x^{a_i})^{-1}\\[0.4ex]
C'_\gamma(x) &= \prod_{i=1}^k\, \(1 +  (1 - x^{a_i})^{-1}\),
\end{align*}
where $a_1, a_2,\dots, a_k$ are the cycle lengths of $\gamma$.

\begin{theorem} Let $1\le m\le n$.  Then
\begin{align*}
  q(n,m) &= [x^{n-m}]\, \sum_P 
      \Bigl(\, \abs{\Aut(P)}^{-1} \!\sum_{\gamma\in \Aut(P)} C_\gamma(x)\Bigr) \\[0.5ex]
   t(n,m) &= [x^{n-m}]\, \sum_P 
      \Bigl(\, \abs{\Aut(P)}^{-1} \!\sum_{\gamma\in \Aut(P)} C'_\gamma(x)\Bigr),
\end{align*}
where the first sum in each case is over isomorphism class representatives
$P$ of posets on $m$ points, $\Aut(P)$ is the automorphism group of~$P$,
and $[x^{n-m}]$ denotes extraction of the coefficient of $x^{n-m}$. 
\end{theorem}

\begin{proof}
We prove the formula for $q(n,m)$; the other is similar.
Let $P$ be a poset with $m$ points.
By the Frobenius-Burnside Lemma, the  number
of equivalence classes under $\Aut(P)$ of weight assignments with
total weight $n$ is
the average over $\gamma\in\Aut(P)$ of the number $w_n(\gamma)$
of such weight assignments fixed by~$\gamma$.

Consider one such element $\gamma\in\Aut(P)$ with cycles of length
$a_1, a_2,\dots, a_k$.  A~weight assignment is fixed by $\gamma$
iff it is constant on each cycle of $\gamma$, so $w_n(\gamma)$ is
the coefficient of $x^n$ in
$$\prod_{i=1}^k ( x^{a_i} + x^{2a_i} + x^{3a_i} + \cdots\;)
  = x^m C_\gamma(x).$$
The result now follows by averaging over $\gamma$.
\end{proof}

As mentioned earlier, $q(n,n)=p(n)$.  We can also identify $q(n,n{-}1)$
as the total number of orbits of $\Aut(P)$ over all posets on $n-1$
points.  Using our previously-computed value of $p(16)$, this enabled
us to determine $q(n,m)$ for $n\le 16$ and $t(n,m)$ for
$n\le 15$ by computing the automorphism groups of all the posets
up to 15 points.  Except in some simple (but common) situations where
the poset generator had already determined $\Aut(P)$, this was
computed using \texttt{nauty}~\cite{nauty}.

The resulting values are given in Tables~1--3.  The programs were run
twice in case of machine errors.  We also successfully recovered the
numbers given by Pfeiffer~\cite{pf} and the values of $p(n)$ up to $n=15$
given by Brinkmann and McKay~\cite{posets}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|ccc}
$n$ & $q(n)$ & $s(n)$ & $t(n)$ \\[0.2ex]
\hline
1 & 1 & 2 & 2 \\
2 & 3 & 7 & 8 \\
3 & 9 & 32 & 39 \\
4 & 33 & 192 & 242 \\
5 & 139 & 1490 & 1895 \\
6 & 718 & 15067 & 19051 \\
7 & 4535 & 198296 & 246895 \\
8 & 35979 & 3398105 & 4145108 \\
9 & 363083 & 75734592 & 90325655 \\
10 & 4717687 & 2191591226 & 2555630036 \\
11 & 79501654 & 82178300654 & 93810648902 \\
12 & 1744252509 & 3984499220967 & 4461086120602 \\
13 & 49872339897 & 249298391641352 & 274339212258846 \\
14 & 1856792610995 & 20089200308020179 & 21775814889230580 \\
15 & 89847422244493 & ~2081351202770089728~ & ~2226876304576948549~ \\
16 & ~5637294117525695~ 
\end{tabular}
\end{center}
\caption{Quasi-orders, soft orders, and transitive relations}
\label{table1}
\end{table}

\begin{table}[H]
\small\setlength{\extrarowheight}{-0.10ex}
\begin{center}
\begin{tabular}{c|c|c||c|c|c||c|c|c}
1 & 1 & 1 &  10 & 1 & 1 &  14 & 1 & 1 \\
\cline{1-3}
2 & 1 & 1 &  10 & 2 & 14 &  14 & 2 & 20 \\
2 & 2 & 2 &  10 & 3 & 120 &  14 & 3 & 256 \\
\cline{1-3}
3 & 1 & 1 &  10 & 4 & 849 &  14 & 4 & 2790 \\
3 & 2 & 3 &  10 & 5 & 5123 &  14 & 5 & 27637 \\
3 & 3 & 5 &  10 & 6 & 27439 &  14 & 6 & 260840 \\
\cline{1-3}
4 & 1 & 1 &  10 & 7 & 127965 &  14 & 7 & 2385741 \\
4 & 2 & 5 &  10 & 8 & 501591 &  14 & 8 & 21304106 \\
4 & 3 & 11 &  10 & 9 & 1487301 &  14 & 9 & 184860968 \\
4 & 4 & 16 &  10 & 10 & 2567284 &  14 & 10 & 1535230287 \\
\cline{1-3}\cline{4-6}
5 & 1 & 1 &  11 & 1 & 1 &  14 & 11 & 11832383054 \\
5 & 2 & 6 &  11 & 2 & 15 &  14 & 12 & 80018898562 \\
5 & 3 & 22 &  11 & 3 & 150 &  14 & 13 & 425004096962 \\
5 & 4 & 47 &  11 & 4 & 1193 &  14 & 14 & 1338193159771 \\
\cline{7-9}
5 & 5 & 63 &  11 & 5 & 8406 &  15 & 1 & 1 \\
\cline{1-3}
6 & 1 & 1 &  11 & 6 & 53443 &  15 & 2 & 21 \\
6 & 2 & 8 &  11 & 7 & 309719 &  15 & 3 & 299 \\
6 & 3 & 35 &  11 & 8 & 1599822 &  15 & 4 & 3525 \\
6 & 4 & 113 &  11 & 9 & 7040921 &  15 & 5 & 38420 \\
6 & 5 & 243 &  11 & 10 & 23738557 &  15 & 6 & 401602 \\
6 & 6 & 318 &  11 & 11 & 46749427 &  15 & 7 & 4124565 \\
\cline{1-3}\cline{4-6}
7 & 1 & 1 &  12 & 1 & 1 &  15 & 8 & 41997196 \\
7 & 2 & 9 &  12 & 2 & 17 &  15 & 9 & 424381067 \\
7 & 3 & 52 &  12 & 3 & 182 &  15 & 10 & 4221560826 \\
7 & 4 & 213 &  12 & 4 & 1632 &  15 & 11 & 40603719604 \\
7 & 5 & 682 &  12 & 5 & 13011 &  15 & 12 & 365485856203 \\
7 & 6 & 1533 &  12 & 6 & 96226 &  15 & 13 & 2906408331804 \\
7 & 7 & 2045 &  12 & 7 & 664467 &  15 & 14 & 18255153928204 \\
\cline{1-3}
8 & 1 & 1 &  12 & 8 & 4268404 &  15 & 15 & 68275077901156 \\
\cline{7-9}
8 & 2 & 11 &  12 & 9 & 24858756 &  16 & 1 & 1 \\
8 & 3 & 71 &  12 & 10 & 124784466 &  16 & 2 & 23 \\
8 & 4 & 367 &  12 & 11 & 484673601 &  16 & 3 & 343 \\
8 & 5 & 1503 &  12 & 12 & 1104891746 &  16 & 4 & 4396 \\
\cline{4-6}
8 & 6 & 4989 &  13 & 1 & 1 &  16 & 5 & 52033 \\
8 & 7 & 12038 &  13 & 2 & 18 &  16 & 6 & 597502 \\
8 & 8 & 16999 &  13 & 3 & 218 &  16 & 7 & 6804011 \\
\cline{1-3}
9 & 1 & 1 &  13 & 4 & 2154 &  16 & 8 & 77823441 \\
9 & 2 & 12 &  13 & 5 & 19320 &  16 & 9 & 897440095 \\
9 & 3 & 95 &  13 & 6 & 162404 &  16 & 10 & 10402896209 \\
9 & 4 & 570 &  13 & 7 & 1304373 &  16 & 11 & 119938485210 \\
9 & 5 & 2923 &  13 & 8 & 10009358 &  16 & 12 & 1348204100877 \\
9 & 6 & 12591 &  13 & 9 & 72589838 &  16 & 13 & 14281079724622 \\
9 & 7 & 44842 &  13 & 10 & 483531684 &  16 & 14 & 134410089884839 \\
9 & 8 & 118818 &  13 & 11 & 2803234294 &  16 & 15 & 1003992754517006 \\
9 & 9 & ~~183231~~ &  13 & 12 & 12677658783 &  16 & 16 & ~~4483130665195087~~ \\
  &&& 13 & 13 & ~~33823827452~~
\end{tabular}
\end{center}
\caption{Values of $q(n,m)$ for various $n,m$}
\label{table2}
\end{table}

\begin{table}[H]
\small
\begin{center}
\begin{tabular}{c|c|c||c|c|c||c|c|c}
1 & 1 & 2 &  9 & 1 & 1 &  13 & 1 & 1 \\
\cline{1-3}
2 & 1 & 1 &  9 & 2 & 15 &  13 & 2 & 21 \\
2 & 2 & 7 &  9 & 3 & 174 &  13 & 3 & 335 \\
\cline{1-3}
3 & 1 & 1 &  9 & 4 & 1769 &  13 & 4 & 4852 \\
3 & 2 & 6 &  9 & 5 & 17694 &  13 & 5 & 70797 \\
3 & 3 & 32 &  9 & 6 & 170391 &  13 & 6 & 1066041 \\
\cline{1-3}
4 & 1 & 1 &  9 & 7 & 1577763 &  13 & 7 & 16906476 \\
4 & 2 & 8 &  9 & 8 & 12823256 &  13 & 8 & 282183725 \\
4 & 3 & 41 &  9 & 9 & 75734592 &  13 & 9 & 4922404711 \\
\cline{4-6}
4 & 4 & 192 &  10 & 1 & 1 &  13 & 10 & 87597193530 \\
\cline{1-3}
5 & 1 & 1 &  10 & 2 & 17 &  13 & 11 & 1521294651297 \\
5 & 2 & 9 &  10 & 3 & 207 &  13 & 12 & 23426706135708 \\
5 & 3 & 63 &  10 & 4 & 2380 &  13 & 13 & 249298391641352 \\
\cline{7-9}
5 & 4 & 332 &  10 & 5 & 26352 &  14 & 1 & 1 \\
5 & 5 & 1490 &  10 & 6 & 294156 &  14 & 2 & 23 \\
\cline{1-3}
6 & 1 & 1 &  10 & 7 & 3243880 &  14 & 3 & 381 \\
6 & 2 & 11 &  10 & 8 & 34592661 &  14 & 4 & 5964 \\
6 & 3 & 84 &  10 & 9 & 325879156 &  14 & 5 & 93159 \\
6 & 4 & 583 &  10 & 10 & 2191591226 &  14 & 6 & 1521101 \\
\cline{4-6}
6 & 5 & 3305 &  11 & 1 & 1 &  14 & 7 & 26315265 \\
6 & 6 & 15067 &  11 & 2 & 18 &  14 & 8 & 486434324 \\
\cline{1-3}
7 & 1 & 1 &  11 & 3 & 248 &  14 & 9 & 9568317752 \\
7 & 2 & 12 &  11 & 4 & 3068 &  14 & 10 & 197959166598 \\
7 & 3 & 112 &  11 & 5 & 37919 &  14 & 11 & 4196507844123 \\
7 & 4 & 883 &  11 & 6 & 472519 &  14 & 12 & 86930341478767 \\
7 & 5 & 6537 &  11 & 7 & 6031290 &  14 & 13 & 1595279690032943 \\
7 & 6 & 41054 &  11 & 8 & 77251333 &  14 & 14 & 20089200308020179 \\
\cline{7-9}
7 & 7 & 198296 &  11 & 9 & 960789368 &  15 & 1 & 1 \\
\cline{1-3}
8 & 1 & 1 &  11 & 10 & 10587762484 &  15 & 2 & 24 \\
8 & 2 & 14 &  11 & 11 & 82178300654 &  15 & 3 & 435 \\
\cline{4-6}
8 & 3 & 139 &  12 & 1 & 1 &  15 & 4 & 7190 \\
8 & 4 & 1294 &  12 & 2 & 20 &  15 & 5 & 120514 \\
8 & 5 & 11096 &  12 & 3 & 288 &  15 & 6 & 2110489 \\
8 & 6 & 90758 &  12 & 4 & 3911 &  15 & 7 & 39534004 \\
8 & 7 & 643701 &  12 & 5 & 52415 &  15 & 8 & 798048843 \\
8 & 8 & ~3398105~ &  12 & 6 & 724866 &  15 & 9 & 17393487215 \\
\multicolumn{2}{l}{ }& & 12 & 7 & 10377573 &  15 & 10 & 406531057397 \\
\multicolumn{2}{l}{ }& & 12 & 8 & 153952401 &  15 & 11 & 10041016241522 \\
\multicolumn{2}{l}{ }& & 12 & 9 & 2314756589 &  15 & 12 & 254873608116034 \\
\multicolumn{2}{l}{ }& & 12 & 10 & 33895893064 &  15 & 13 & 6326335208572503 \\
\multicolumn{2}{l}{ }& & 12 & 11 & 440211138507 &  15 & 14 & 138933427209562650 \\
\multicolumn{2}{l}{ }& & 12 & 12 & ~3984499220967~ & 
 15 & 15 & ~2081351202770089728~
\end{tabular}
\end{center}
\caption{Values of $t(n,m)$ for various $n,m$}
\label{table3}
\end{table}

\def\,{\kern0.2em}
\begin{thebibliography}{99}

\bibitem{posets} G.~Brinkmann and B.\,D.~McKay, Posets on up to 16 points,
 {\it Order} {\bf 19} (2002), \hbox{147--179}.

\bibitem{nauty}B.~McKay, \texttt{nauty} -- a program for graph isomorphism and
 automorphism, available at
 \href{http://cs.anu.edu.au/~bdm/nauty/}{\texttt{http://cs.anu.edu.au/\twid bdm/nauty/}}.

\bibitem{pf}G.~Pfeiffer, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html}{Counting transitive relations},
 {\it J. Integer Seq.} {\bf 7} (2004), paper 04.3.2.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 06A99; Secondary 05C20, 05C30.

\noindent \emph{Keywords:} transitive relation, finite topology,
order, directed graph.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001930}, \seqnum{A079265}, and \seqnum{A091073} .)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 19 2004;
revised version received March 18 2005. 
Published in {\it Journal of Integer Sequences}, March 29 2005.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}