On the density of trigraph homomorphisms (Q2373444): Difference between revisions

A trigraph \(G\) consists of a finite set \(V(G)\) of vertices, and two (possibly intersecting) edge sets \(E_1(G)\), \(E_2(G)\) on \(V(G)\), such that \(E_1(G)\cup E_2(G)\) contains all unordered pairs of (possibly equal) vertices. Let \(G\) and \(H\) be any trigraphs. A homomorphism \(f\) of \(G\) to \(H\) is a mapping of \(V(G)\) to \(V(H)\) such that \(uv\in E_i(G)\) implies \(f(u)f(v)\in E_i(H)\) (\(i=1,2\)). \(G<H\) means that there exists a homomorphism of \(G\) to \(H\), but not of \(H\) to \(G\); if \(G<H\) but there exists no \(K\) such that \(G<K<H\), \(G<H\) is called a gap. From the authors' abstract: ``An order is dense if \(A<B\) implies \(A<C<B\) for some \(C\). The homomorphism order of (nontrivial) graphs is known to be dense. Homomorphisms of trigraphs extend homomorphisms of graphs'' [cf. \textit{P. Hell} and \textit{J. Nešetřil}, Graphs and homomorphisms. Oxford University Press (2004; Zbl 1062.05139)], ``and model many partitions of interest in the study of perfect graphs.'' Two trigraphs are homomorphically equivalent if each admits a homomorphism to the other. A trigraph is a core if it is not homomorphically equivalent to any proper subtrigraph. A digon (respectively diloop) of \(G\) is a pair \(u,v\) of distinct (respectively identical) vertices such that \(uv\in E_1(G)\cap E_2(G)\); \(G^*\) is the subtrigraph induced by all vertices incident to digons. Theorem 1. Suppose \(G\) and \(H\) are cores without diloops such that \(G<H\). If (1) \(G\) is a subtrigraph of \(H\) with \(G^*=H^*\); (2) every homomorphism of \(G\) to \(H\) is injective; and (3) the core of each proper subtrigraph of \(H\) which contains \(G\) is equal to \(G\), then \(G<H\) is a gap. Otherwise there exists a trigraph \(K\) with \(G<K<H\).