A partially ordered set of functionals corresponding to graphs (Q1332414): Difference between revisions

If \(\Omega = (x,{\mathcal M}, \mu)\) is a measure space and if \(M(\Omega)\) is the class of all measurable bounded nonnegative symmetric functions on \(\Omega^ 2\) and if \(G=(V,E)\), \(V=\{v_ 1, \dots, v_ m\}\), then for \(h \in M (\Omega) : \prod_{uiuj \in E} h(x_ i,x_ j)\) is the configuration product of \(G\) relative to \(h\) and \(U_ G\) where \(U_ G(h) = \int \cdots \int (\prod_{uiuj \in E} h(x_ i,x_ j))d \mu(x_ 1) \dots d \mu (x_ m)\) is the functional corresponding to \(G\), which if \(h\) is the adjacency function of \(H\) on the vertex set \(X\) of \(H\) and \(\mu\) the counting measure determines \(\text{hom} (G,H)\), the number of homomorphisms (edge-preserving maps) from \(G\) to \(H\). The binary relation \(G \geq L\) means that \(U_ G (h) \geq U_ L (h)\) under all admissible circumstances which is according to the author's T1.1 equivalent to \(\text{hom}(G,H)\geq\text{hom}(L,H)\) for all (simple) graphs \(H\) and which yields a partial order with interesting properties. If \(T^ k\) denotes the poset of \(k\)-edge trees, then as a consequence of previous results and observations obtained in a section on comparability criteria containing many examples it follows in T1.2 that \(G\in T^ k\) implies \(K_{1,k}\geq T^ k_{k-2} \geq G\) \((T^ k_ i\) is obtained by connecting \(i\) vertices (leaves) to the end of a \((k-i)\)-edge path). Furthermore, several incomparability results are also obtained, some of them based on the Muirhead theorem of venerable age and applied to study of \(T^ k\) for small \(k\) to produce some graph-theoretical insights of unusual perspective to those unfamiliar with the approach outlined in this paper.