\input zb-basic
\input zb-ioport
\iteman{io-port 01420847}
\itemau{Komj\'ath, P\'eter}
\itemti{A theorem on countable ordered sets with an application to universal graphs.}
\itemso{Buss, Samuel R. (ed.) et al., Logic colloquium '98. Proceedings of the annual European summer meeting of the Association for Symbolic Logic, Prague, Czech Republic, August 9-15, 1998. Natick, MA: A K Peters, Ltd. Lect. Notes Log. 13, 296-301 (2000).}
\itemab
If $(A,<)$ is a poset and $k<\omega$ is a natural number, $k=\{0,1, \dots,k-1\}$, with $G(A,k)$ the set of all functions $f:A^2\to k$, then $G(A,k)$ can be interpreted as the collection of (complete) digraphs whose colored edges come from a set of $k$ colors. If $k=2=\{0,1\}$, the colors are ``absent'' and ``present'' and we may interpret $G(A,k)=G(A,2)$ as the collection of digraphs on the set $A$. For $f,g\in G(A,k)$, let be $f\le g$ if for some order-preserving $\varphi:A\to A$, $f(x,y)=g$ $(\varphi(x)$, $\varphi(y))$ for $x<y$ in $A$. This provides an (induced) quasi-order on $G(A,k)$. If $G'\le G(A,k)$ has the property that $f\in G(A,k)$ implies $f\le g$ for some $g\in G'$, then $G'$ is cofinal. The cofinality of $G(A,k)$ is the least cardinality of a cofinal set. Given these definitions the author proves a very nice theorem which combines and generalizes a collection of results in graph theory $(k=2$, e.g.): If $(A,<)$ is a countable poset and $k<\omega$, then $G(A,k)$ has finite cofinality (while $G(A,\omega)$ is seen to have countable cofinality). Thus if $(A,<)$ is a countable poset, then there exist finitely many graphs on $A$ such that every graph on $A$ is (order-)isomorphic to an induced subgraph of one of these graphs. Note also that if $A$ is a set, then it is naturally a poset if it is ordered as an antichain with $<$ the empty relation, i.e., $x\le y$ if $x=y$. The order-preserving functions $\varphi: A\to A$ are then arbitrary functions. The corresponding cofinality is then minimal among all other cofinalities.
\itemrv{Joseph Neggers (Tuscaloosa)}
\itemcc{}
\itemut{digraphs; cofinality; cofinal set; countable poset; order-preserving functions}
\itemli{}
\end