No label defined (Q4944915)

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\leq 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'\leq G(A,k)\) has the property that \(f\in G(A,k)\) implies \(f\leq 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\leq 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. For the entire collection see [Zbl 0932.00038].