Compactness and finite equivalence of infinite digraphs (Q1356449)

An infinite digraph \(G\) is called compact provided there is a homomorphism from a digraph \(H\) to \(G\) if and only if there is a homomorphism from \(H'\) to \(G\) for any finite subdigraph \(H'\) of \(H\). It is proved that there are exactly \(2^{\aleph_0}\) compact digraphs, up to homomorphic equivalence. Two infinite digraphs \(G\) and \(H\) are finitely equivalent if they possess the same set of finite subdigraphs (up to homomorphic equivalence). Denote by \({\mathcal F}(G)\) the class of homomorphic equivalence classes of all digraphs that are finitely equivalent to \(G\). It is proved that \({\mathcal F}(G)\) consists of a single homomorphic equivalence class iff there is a digraph \(H\) homomorphically equivalent to \(G\), such that \(H\) is compact and is a disjoint union of finite digraphs. In nearly all other cases \({\mathcal F}(G)\) is a proper class. The theory of finite equivalence is extended to infinite undirected graphs. In this case either \({\mathcal F}(G)\) consists of a single graph or \({\mathcal F}(G)\) is a proper class. Several open problems are stated.