Generalized homomorphism graph functions (Q753838): Difference between revisions

Lovász posed the problem of characterizing all real-valued functions f on finite graphs which are increasing \((f(G)\leq f(H)\) if G is a subgraph of H) and multiplicative \((f(G\times H)=f(G)\cdot f(H),\) for the conjunction, or categorical product \(\times)\). The author has earlier given several classes of such functions, and he presents here a new class, properly extending a class defined previously. The new class consists of functions \(\phi_{G,S}\), whose value \(\phi_{G,S}(H)\) is defined to be the number of distinct restrictions \(f| S\) of homomorphisms f: \(G\mapsto H\) to the fixed set \(S\subseteq V(G)\). Lovász observed that the class of increasing multiplicative functions was closed under taking products, positive powers, and pointwise limits, and asked whether a certain class of functions generated all increasing multiplicative functions by the above operations. The author has shown previously that this was not so. The new class of functions \(\phi_{G,S}\) extends the basic class proposed by Lovász, but is still not large enough to generate all increasing multiplicative functions by products, positive powers, and pointwise limits. Similar questions are also considered for the Cartesian product, and for functions f which are increasing, multiplicative, and additive \((f(G+H)=f(G)+f(H),\) for the disjoint union \(+)\).