A note on homomorphism-independent families (Q5937945)

A family of objects \(\{ A_i\mid i\in J\}\) is said to be independent if there is no homomorphism \(A_i\rightarrow A_j\) for distinct \(i,j\in J\). The authors establish infinite independent families of finite objects (IIFF) for many classes of graphs. A class \(\mathcal K\) of graphs is a finitely generated Horn class (FGH-class) if there exists a finite set \({\mathcal A}\) of finite graphs such that \({\mathcal K}\) consists of all subgraphs of categorical products of graphs from \({\mathcal A}\). Dropping the finiteness condition on \({\mathcal A}\) one gets the notion of universal Horn class (UH). The two results that there exist continuum many UH-classes and there exist continuum many UH-classes of \(H\)-colourable graphs, that is, graphs \(G\) for which there is a homomorphism \(G\rightarrow H\) for any non-bipartite graph \(H\) are reproved with an approach based on the following earlier result of the authors. Let \(H\) be a fixed finite graph. Then the class \(\rightarrow H = \{ G \mid \text{ there is a homomorphism } G\rightarrow H \}\) is an FGH-class. NEWLINENEWLINENEWLINEIn Section 1 the existence of IIFF's is connected with the universality of the respective categories. In Section 2 an IIFF is constructed without any relation to universality. In Section 3 examples show how much weaker the existence of an IIFF is, as compared with the universality. In particular, in Section 1 it is shown that the class \({\mathbf Ch}_n\) of (precisely) \(n\)-chromatic undirected graphs, \(n\geq 3\), the class \({\mathbf LC}_n\) of undirected graphs with the shortest length of a cycle at least \(n\) and the class of all graphs \(G\) with a homomorphic image isomorphic to \(H\) contain a homomorphism-independent family of any size, and a countable one consisting of finite objects.