Generalized One-to-One Mappings between Homomorphism Sets of Digraphs
Frank a Campo























A
E
G
H̋
I
J
ŁL
S
T






































































































































































plain
conditionCondition
theoremTheorem
definitionDefinition
corollaryCorollary
lemmaLemma
propositionProposition





Generalized One-to-One Mappings between Homomorphism Sets of Digraphs
    Frank a Campo
    Seilerwall 33, D 41747 Viersen, Germany

acampo.frank@gmail.com
=====================================================================




Structural properties of finite digraphs R and S are studied which enforce #(̋G,R) ≤#(̋G,S) for every finite digraph G ∈', where (̋G,H) is the set of homomorphisms from G to H, and ' is a class of digraphs. In a previous study, we have seen that the key for such a relation between R and S is the existence of a strong S-scheme from R to S. Such an S-scheme ρ defines a one-to-one mapping ρ_G : (G,R) →(G,S) for every G ∈', where (G,H) is the set of homomorphisms from G to H mapping proper arcs of G to proper arcs of H. In the present article, we characterize S-schemes ρ which are induced by strict homomorphisms : (R) →(S) between auxiliary systems of R and S, and we analyze the mutual dependency between the properties of ρ and . Wide applicability of the theory is ensured by specifying the auxiliary systems (R) and (S) as EV-systems of R and S. The results are applied on a rearrangement method for digraphs and on undirected graphs.


Mathematics Subject Classification:

Primary: 06A07. Secondary: 06A06.

Key words: digraph, homomorphism, Hom-scheme, Γ-scheme, S-scheme, EV-system.




§ INTRODUCTION
 

The number of homomorphisms between directed graphs (digraphs) may carry important information about structure. Freedman et al. <cit.> characterized in 2007 graph parameters which can be expressed as numbers of homomorphisms into weighted graphs. The still open reconstruction conjecture asks in different fields of graph theory <cit.>, if two objects with at least four vertices are isomorphic if all numbers of embeddings of certain subgraphs into them are equal. An early classical result is the Theorem of Lovász <cit.> from 1967 which states that numbers of homomorphisms distinguish non-isomorphic “relational structures”. With (̋G,H) defined as the set of homomorphisms from a digraph G to a digraph H, the following specifications are relevant for our purpose:

 
Let  be the class of finite digraphs or the class of finite posets. Then, for R, S ∈

    R    ≃ S 
    ⇔   #(̋G,R)     = #(̋G,S)  for every  G ∈.

For the class of finite posets, the equivalence holds also if we replace the homomorphism sets by the sets of strict order homomorphisms.


For digraphs, a short and simple proof of the theorem is contained in <cit.> which - with minor modification - works for posets, too.

The infinite vector Ł(H) ≡ ( #(̋G,H) )_G ∈ is called the Lovász-vector of H.  In the last decades, topics related to it have found interest <cit.> in connection with vertex and edge weights. For undirected graphs, Dvořák <cit.> investigated in 2010 proper sub-classes ' of undirected graphs for which the partial Lovász-vector ( #(̋G,H) )_G ∈' still distinguishes graphs; the distinguishing power of the vector ( #(̋G,H) )_H ∈' has been investigated by Fisk <cit.> in 1995.

This paper continues the work of the author about the pointwise less-equal-relation between partial Lovász-vectors of digraphs:

Given a class ' of digraphs, what is it in the structure of digraphs R and S that enforces


    #(̋G,R) ≤#(̋G,S)   for every  G ∈'  ?




The starting point of the work was the pair of posets R and S in Figure <ref>(c). The author <cit.> has proven that for these posets we have #(̋P,R) ≤#(̋P,S) for every finite poset P. Additional non-trivial examples for the relation “#(̋P,R) ≤#(̋P,S) for every finite poset P” are shown in the Figures <ref>(a)-(b); more pairs of digraphs fulfilling (<ref>) are contained in the Figures <ref> and <ref>.

In the recent paper, a first attempt is made to tackle the theoretical aspect of the question. After the preparatory Section <ref>, a main result from <cit.> is recalled in Section <ref>: it has been shown <cit.>, that for several important classes of digraphs ' and R ∈', (<ref>) is implied by

    #(G,R)  ≤ #(G,S)   for all  G ∈'
 
where (G,H) is the set of strict homomorphisms from G to H, i.e., of those homomorphisms from G to H mapping proper arcs of G to proper arcs of H.

Due to the implication (<ref>)⇒(<ref>), our interest focuses on the existence of a generalized mapping ρ providing a mapping ρ_G : (G,R) →(G,S) for every G ∈'. (A formally satisfying definition is given in Definition <ref>.) We call such a generalized mapping an S-scheme from R to S, and we call ρ strong iff ρ_G is one-to-one for every G ∈'.

For a (strong) S-scheme ρ and G, G' ∈' with G ≠ G', the mappings ρ_G and ρ_G' are in principle independent from each other, no matter how closely G and G' are related. Even in the case of ξ∈(G,R) ∩(G',R), the resulting homomorphisms ρ_G(ξ) ∈(G,S) and ρ_G'(ξ) ∈(G',S) must not be related to each other in any way. It are the induced S-schemes defined in Section <ref> which introduce some regularity by “mapping similar things to similar things”, and they are the subject of this paper. In particular, S-schemes are suitable for constructive approaches, and we will pay special attention to the types of regularity introduced by them.

For an induced S-scheme ρ from R to S, we have for all G ∈'

    ρ_G   =  ϕ∘∘α_G,

where α is a simple S-scheme from R to an auxiliary digraph (R), ϕ is a strict homomorphism from another auxiliary digraph (S) to S, and : (R) →(S) is a strict homomorphism. Obviously, the properties of ρ are mainly determined by the digraphs (R) and (S) and the homomorphism  between them. From a theoretical point of view it is interesting to analyze the mutual dependency between the properties of ρ and , and from a practical point of view, there is a perspective to construct a strong S-scheme ρ from R to S with desired properties by designing (hopefully simple) digraphs (R) and (S) and an appropriate homomorphism  between them.

The theoretical aspect is in the focus in what follows. Still in Section <ref>, we characterize the induced S-schemes in Theorem <ref>. In Theorem <ref>(1), we show that a regularity condition on  called “Condition <ref>” is equivalent to a certain regular behavior of the induced S-scheme ρ, and in Theorem <ref>(2), we see that an additional property of  forces ρ to be strong.

In Section <ref>, we specify (R) and (S) as EV-systems and describe their dependency on the class of digraphs ' they are referring to. In Theorem <ref> in Section <ref>, we use EV-systems in showing that for the classes of digraphs we are mainly interested in, Theorem <ref>(2) can be inverted: if an induced strong S-scheme ρ behaves sufficiently regular, then the corresponding  is one-to-one and fulfills Condition <ref>. Because Condition <ref> is unwieldy to check, we show in Proposition <ref> in Section <ref> how it can be replaced by a more handy condition.
 
In Section <ref>, we take up the rearrangement method developed in <cit.>. By means of this method, a digraph R fulfilling certain conditions is rearranged in such a way that there exists a strong S-scheme ρ from R to the digraph S resulting from the rearrangement. We see that ρ is in fact an induced strong S-scheme, and we describe the corresponding homomorphism : (R) →(S). In Section <ref>, we discuss in detail the posets in Figure <ref>(a) and Figure <ref>(b) under these view points.

Finally, in Section <ref>, we transfer our concepts and results to undirected graphs.



§ BASICS AND NOTATION
 

A (finite) directed graph or digraph G is an ordered pair (V(G),A(G)) in which V(G) is a non-empty, finite set and A(G) ⊆ V(G)  V(G) is a binary relation on V(G). We write vw for an ordered pair (v,w) ∈ V(G)  V(G). The elements of V(G) are called the vertices of G and the elements of A(G) are called the arcs of G. A digraph G is reflexive,  or symmetric, or antisymmetric, etc., iff the relation A(G) has the respective property. A partially ordered set (poset) is a reflexive, antisymmetric, transitive digraph. 

For a digraph G and a non-empty set X ⊆ V(G), the digraph G |_X induced on X is ( X, A(G) ∩ ( X  X) ). The direct sum G + H of digraphs with disjoint vertex sets is defined as usual.

Vertices v, w ∈ V(G) are adjacent iff vw ∈ A(G) or wv ∈ A(G). The open neighborhood N_G(v) of v ∈ V(G) is the set of all w ∈ V(G) ∖{ v } adjacent to v. Furthermore,

    _G(v)     ≡  w ∈ N_G(v)  wv ∈ A(G) , 
    _G(v)     ≡  w ∈ N_G(v)  vw ∈ A(G) .

An arc vw ∈ A(G) is called proper iff v ≠ w; otherwise, it is called a loop. All possible loops of G are collected in the diagonal Δ_G ≡(v,v)v ∈ V(G). G^* ≡ (V(G), A(G) ∖Δ_G) is the digraph G with loops removed.

A sequence v_0, … , v_I of vertices of G with I ∈ is called a walk iff v_i-1v_i ∈ A(G) for all 1 ≤ i ≤ I. The walk is closed iff v_0 = v_I. A digraph is acyclic iff it does not contain a closed walk.

Let G be a digraph. With  denoting the set of all transitive relations T ⊆ V(G)  V(G) with A(G) ⊆ T, the transitive hull ( V(G), ∩ ) of G is the digraph with vertex set V(G) and the (set-theoretically) smallest transitive arc set containing A(G). 

Given digraphs G and H, we call a mapping ξ : V(G) → V(H) a homomorphism from G to H if ξ(v) ξ(w) ∈ A(H) for all vw ∈ A(G). For such a mapping, we write ξ : G → H; we collect the homomorphisms in the set

    (̋G,H)     ≡ ξ : V(G) → V(H) ξ is a homomorphism.

(G) is the set of automorphisms of a digraph G. Isomorphism is indicated by “≃”.

Every homomorphism ξ : G → H maps loops in G to loops in H, but proper arcs of G can be mapped to both, loops and proper arcs of H. We call a homomorphism from G to H strict iff it maps all proper arcs of G to proper arcs of H.

    (G,H)     ≡ (̋G,H) ∩(̋G^*,H^*)

is the set of strict homomorphisms from G to H. The set (̋G^*,H^*) ∖(̋G,H) contains all homomorphisms from G^* to H^* which map a vertex belonging to a loop in G to a vertex of H not belonging to a loop. A mapping ξ : V(G) → V(H) is thus a strict homomorphism, iff it maps loops in G to loops in H and proper arcs of G to proper arcs of H. If H is reflexive, then (G,H) = (̋G^*,H^*); for posets P and Q, the set (P,Q) = (̋P^*,Q^*) is the set of strict order homomorphisms from P to Q.

In order to avoid unnecessary formalism, we work with representative systems of classes of digraphs with respect to isomorphism and not with the classes itself.  is a representative system of the class of all digraphs with finite non-empty vertex set. Furthermore,

    ≡  G ∈ G^* is acyclic, 
         ≡  P ∈ P is a poset, 
    ^*     ≡  P^*  P ∈.

Equivalently,  can be characterized as an representative system of the class of digraphs with antisymmetric transitive hull (which is the reason for the choice of the symbol ) or as the class of subgraphs of posets. ^* is the class of posets with loops removed, i.e., the class of finite irreflexive antisymmetric transitive digraphs. ^* is of interest for us, because every result about homomorphism sets (̋P,Q) with P, Q ∈^* directly translates into a result about the sets of strict order homomorphisms between posets and vice versa. For example, the addendum in Theorem <ref> says that the stated equivalence also holds for = ^*.

We assume ^* ⊂_a, and we will tacitly assume that every digraph we construct in what follows belongs to the respective representative system without exchange of vertices. Nevertheless, for G, H ∈, we retain the notation G ≃ H instead of G = H in order to emphasize that it is structural equivalence we are dealing with, not physical identity.

From set theory, we use additionally the following notation:

    0   ≡∅, 
    n   ≡{ 1, …, n }for every n ∈.


(X,Y) is the set of mappings from X to Y. For f ∈(X,Y) and X' ⊆ X, we write f |_X' for the pre-restriction of f to X', and for Y' ⊆ Y with f(X) ⊆ Y' we write f |^Y' for the post-restriction of f to Y'. Furthermore, we use the symbol f(Y”) for the pre-image of Y”⊆ Y under f; for y ∈ Y, we simply write f(y) instead of f( {y} ). However, in the proof of Lemma <ref>, we use the symbol β^-1 also for the inverse of a bijective mapping β. 𝕀_X is the identity mapping of a set X.

Finally, we use the Cartesian product. Let  be a non-empty set, and let M_i be a non-empty set for every i ∈. Then the Cartesian product of the sets M_i, i ∈, is defined as

    ∏_i ∈ M_i     ≡     f ∈( , ⋃_i ∈ M_i ) f(i) ∈ M_i for all i ∈.




§ S-SCHEMES
 

In Section <ref>, we recall the main concepts and results from <cit.>. It turns out that for our purpose, so-called S-schemes are in the focus: generalized mappings ρ providing a mapping ρ_G : (G,R) →(G,S) for every G ∈' ⊆. In Section <ref>, we introduce induced S-schemes. These S-schemes can be described effectively by two auxiliary digraphs and a strict homomorphism  between them. We characterize the induced S-schemes and show how regularity conditions on  translate into regular behavior of the induced S-scheme ρ and vice versa.



 §.§ Recapitulation
 

Let R, S ∈ and ' ⊆. Assume that there exists a one-to-one homomorphism σ : R → S. Then, for every G ∈' with (̋G,R) ≠∅, we get a one-to-one mapping r_G : (̋G,R) →(̋G,S) by setting for every ξ∈(̋G,R)

    r_G(ξ)    ≡σ∘ξ.

A one-to-one homomorphisms from R to S delivers thus a “natural” (or: trivial) example for #(̋G,R) ≤#(̋G,S) for every G ∈'. For the general investigation of this relation between R and S, the author <cit.> has introduced the following concepts:

 
Let ' ⊆ be a representative system of a class of digraphs. For R, S ∈, we call a mapping

    ρ    ∈∏_G ∈'( (̋G,R), (̋G,S) )

a Hom-scheme from R to S (with respect to '), and we call it strong iff ρ_G : (̋G,R) →(̋G,S) is one-to-one for every G ∈'. We say that a Hom-scheme ρ from R to S is a Γ-scheme, iff

    =

holds for every G ∈', ξ∈(̋G,R), v ∈ V(G), where  is the connectivity component of v in ξ() and  is the connectivity component of v in (). We write R  S iff a strong Γ-scheme from R to S exists. If G is fixed, we write ρ(ξ) instead of ρ_G(ξ).


Here as in the following, it does not matter if there is a G ∈' with (̋G,R) = ∅; in this case, ρ_G = ( ∅, ∅, (̋G,S)). The (trivial) Hom-scheme (<ref>) is always a strong Γ-scheme. We will generalize the concept of such simple Hom-schemes in Section <ref>.

A Hom-scheme ρ from R to S is strong if we can determine  by means of ρ(ξ) for all . We say that we can reconstruct ξ by means of ρ(ξ). Obviously, we can reconstruct ξ by means of ρ(ξ) if we can determine ξ(v) for every v ∈ R by means of ρ(ξ).

A (strong) Γ-scheme is a (strong) Hom-scheme obeying the regularity condition (<ref>) in mapping (̋G,R) to (̋G,S) for every G ∈'. This condition has been introduced in <cit.> under an application-oriented point of view. It may look like an additional difficulty posed upon a question difficult enough in itself. However, in fact, (<ref>) is a regularity condition making things manageable by introducing structure. For a (strong) Hom-scheme ρ  from R to S and G, G' ∈' with G ≠ G', the mappings ρ_G and ρ_G' are independent; even in the case of ξ∈(̋G,R) ∩(̋G',R), there must be no similarity between the image-homomorphisms ρ_G(ξ) and ρ_G'(ξ). It are the Γ-schemes and in particular the induced S-schemes defined in Section <ref> which ensure that “similar things are mapped to similar things”. In this way, S-schemes are suitable for constructive approaches, and we will pay particular attention to the question which type of regularity is introduced by them.

The regularity condition (<ref>) is in particular plausible if we regard a Hom-scheme as a technical apparatus which assigns to every ξ∈(̋G,R) a well-fitting ρ(ξ) ∈(̋G,S). If we allow ⊂ for x ∈ P, then <cit.> tells us that ρ(ξ) preserves the structure of G around v worse than ξ, which is not satisfying. And in the case ⊈, ρ(ξ) has to re-distribute the points of ∖⊆∖{ v } in S. Because the sets ∖ can be arbitrarily complicated, this re-distribution process may require many single case decisions, which is out of the scope of a technical apparatus.

It is easily seen <cit.> that a homomorphism ξ∈(̋G,H) is strict iff = { v } for all v ∈ G. Because a Γ-scheme preserves the sets , we have for every Hom-scheme ρ from R to S

    ρΓ-scheme   ⇒  ρ_G( (G,R) ) ⊆(G,S)   for all  G ∈',

hence #(G,R) ≤#(G,S) for all G ∈' if ρ is additionally strong. One of the main results of <cit.> adds the direction “⇐” to this implication:
 
Let 
    R    ∈' = , 
    
    R    ∈⊆' ⊆, 
    or   R    ∈'  with ' =  or ' = ^*.

Then, for all S ∈, there exists a strong Γ-scheme from R to S with respect to ', iff

    #(G,R)  ≤ #(G,S)   for all  G ∈'.



In the investigation of strong Γ-schemes, it is thus obvious to give special attention to the restriction of Hom-schemes to sets of strict homomorphisms:
 
Let R, S ∈, ' ⊆. We call a mapping

    ρ    ∈ ∏_G ∈'( (G,R), (G,S) )

an S-scheme from R to S with respect to '. We call an S-scheme from R to S strong iff the mapping ρ_G : (G,R) →(G,S) is one-to-one for every .


In fact, we have seen:

 
In the constellations of R and ' described in Theorem <ref>, a strong S-scheme ρ from R to S can always be extended to a strong Γ-scheme ρ' with ρ'_G |_(G,R)^(G,S) = ρ_G for all G ∈'. 


Theorem <ref> and Proposition <ref> remain valid also for other sub-classes ' of , e.g., for the digraphs (posets) with at most k vertices or at most k arcs, and for the class of digraphs in  for which the maximal length of a walk without loops is at most k.



 §.§ Induced S-schemes
 



In the following definition, the main property of the trivial strong Γ-scheme in (<ref>) is generalized and transferred to S-schemes:

 
Let T, (T) ∈, and let α be an S-scheme from T to (T) with respect to ' ⊆. We call α a simple S-scheme iff there exists a strict homomorphism ϕ_T : (T) → T with

    ∀  G ∈', ξ∈(G,T) : ϕ_T ∘  =  ξ.

If G is fixed, we write  instead of . 

Because α is an S-scheme,  is strict for all ∈', ξ∈(G,T). (<ref>) shows that α_G : (G,T) →(G,(T)) is one-to-one for every G ∈'; a simple S-scheme is thus always a strong S-scheme. The difference in notation of the homomorphism argument between general S-schemes (in brackets) and simple S-schemes (as subscript) has been chosen in order to facilitate the reading of formulas.

In what follows, we work in parallel with three S-schemes with respect to ': a simple S-schemes α^R from R to an auxiliary digraph (R), an S-scheme ρ from R to S, and a simple S-scheme α^S from S to an auxiliary digraph (S). In the case of (R) ∈', we are in the situation shown in Figure <ref>. The left triangle G - (S) - S and the right triangle G - (R) - R commute due to (<ref>). Because of (R) ∈' and ϕ_R ∈( (R), R), both homomorphisms ϕ_R  : (R) → S and Sρ( ϕ_R ) : (R) →(S) are well-defined and strict with ρ( ϕ_R ) = ϕ_S ∘Sρ( ϕ_R ) because of (<ref>). We are interested in that also the outer triangle G - (R) - S commutes

    ∀  G ∈', ξ∈(G,R) :     =  ρ( ϕ_R ) ∘,

which is implied by a commuting inner triangle G - (R) - (S)

    ∀  G ∈', ξ∈(G,R) :Sρ(ξ)     =  Sρ( ϕ_R )∘.


The reason for being interested in (<ref>) becomes visible, if we rewrite (<ref>)  by means of (<ref>):

    ∀  G ∈', ξ∈(G,R) :     =  ϕ_S ∘S(R)ρ( ϕ_R )∘.

Here, the properties of ρ are mainly determined by the digraphs (R) and (S) and the strict homomorphism ≡S(R)ρ( ϕ_R ) between them. From a theoretical point of view, it is interesting to analyze the mutual dependency between the properties of ρ and , and from a practical point of view, there is a perspective to construct an S-scheme ρ from R to S with desired properties by designing (hopefully simple) objects (R) and (S) and an appropriate homomorphism  between them. In order to unburden the notation in what follows, we define for T ∈{ R, S }:

    _o(T)     ≡  V( (T)).


In the discussion of Figure <ref>, we have used the assumption (R) ∈' in order to make the cogwheels interlocking. We give an own name to this assumption and to an additional one:


  * ERD: (R) ∈';

  * AID: R(R)ϕ_R = 𝕀__o(R).

Assumption AID requires ERD, because otherwise, R(R)ϕ_R is not defined. If ERD holds, then also ρ(ϕ_R) : (R) → S is well-defined and strict, because ρ is an S-scheme, and S(R)ρ( ϕ_R ) : (R) →(S) is strict, too.

In the following definition, we generalize our approach by replacing S(R)ρ( ϕ_R ) with an arbitrary strict homomorphism from (R) to (S):

 
Let : (R) →(S) be a strict homomorphism. We define for every 

    Gξ  ≡  ϕ_S ∘∘

and call η the S-scheme induced by . 

Additionally, we define for all 

    E_G(ξ)   ≡   v ∈ G ∈[ _o(R) ] .


We write  and E(ξ) in the case of a fixed G ∈'.


For , the mapping η_G(ξ) : V(G) → V(S) is a combination of strict homomorphisms, thus strict. Therefore, η is indeed an S-scheme, as suggested by Definition <ref>, and SGη(ξ) is well defined. For EDR and = S(R)ρ( ϕ_R ), we have η(ξ) = ρ( ϕ_R ) ∘, hence η = ρ in the case of (<ref>). The reader will observe that the set E_G(ξ) can be determined by means of  and η_G(ξ) for all ; knowledge about ξ is not required.

Induced S-schemes are characterized as follows:
 
Let ρ be an S-scheme from R to S with respect to ' ⊆. If ρ is induced by a strict homomorphism from (R) to (S) then, for all G, H ∈', ξ∈(G,R), ζ∈(H,R), v ∈ G, w ∈ H,

    = RHζw  ⇒   = Hζw.

On the other hand, if ERD and AID are fulfilled and ρ is an S-scheme fulfilling (<ref>), then ρ is induced by S(R)ρ( ϕ_R ).

Let : (R) →(S) be a strict homomorphism inducing ρ. Then trivially, = RHζw yields

    =  ϕ_S ( (  ) )   =  ϕ_S ( ( RHζw ) )   =  Hζw,

thus (<ref>).

Now assume ERD and AID and let ρ be an S-scheme fulfilling (<ref>). Due to AID, = R(R)ϕ_R for all , hence 

    (<ref>)= ρ_(R)(ϕ_R)()
     (<ref>)= ϕ_S ( S(R)ρ( ϕ_R )),

and ρ is induced by S(R)ρ( ϕ_R ).



For given (R) and (S), an induced S-scheme can in general be induced by several homomorphisms : (R) →(S). Nevertheless, the following proposition shows that it is beneficial to select  carefully, because suitable properties of  guarantee that η is “close to” being strong:

 
Let  be a strict homomorphism from (R) to (S). Assume

    ∀ , ∈_o(R) :  (  ) = (  )  ⇒ ϕ_R(  ) = ϕ_R(  ),

and assume additionally, that for every 

    ∀  v ∈ E( ξ )  ∃ ∈ϕ_R (  )  :  = (  ).

Then, for every r ∈ V(R) and every 

    ξ(r) ∩ E( ξ )    =   ⋃_∈ϕ_R (r)( (  ) );

we can thus reconctruct ξ|_E(ξ) by means of η(ξ) and .


Let r ∈ V(R) and let W be the set on the right side of (<ref>). For v ∈ξ(r) ∩ E(ξ), assumption (<ref>) delivers an ∈ϕ_R (r) with = (  ), hence

    v  ∈ (  )   =  ( (  ) ).

We conclude v ∈ W due to ϕ_R(  ) = r.

Now let v ∈ W, i.e., v ∈( (  ) ) for an ∈ϕ_R (r). Then v ∈ E(ξ). According to (<ref>), there exists a ∈ϕ_R (  ) with = (  ). Now we get

    (  )   =  Sη(ξ)v  =  (  ),

and assumption (<ref>) yields r = ϕ_R(  ) = ϕ_R(  ) =, hence v ∈ξ(r).



Even if we have found a strict homomorphism : (R) →(S) fulfilling the conditions in Proposition <ref>, there remains a gap for the induced S-scheme η to being strong: how to reconstruct ξ on V(G) ∖ E(ξ)? The gap disappears if E(ξ) = V(G) for all . The following condition does even more:

 
We say that a strict homomorphism : (R) →(S) fulfills Condition <ref>, iff for every 

    SGη(ξ)   =   ∘.



In the case of = S(R)ρ( ϕ_R ), this condition is (<ref>). Induced S-schemes fulfilling Condition <ref> are characterized in the following theorem:

  Assume that ERD and AID are fulfilled and that ρ is an S-scheme from R to S. We define ≡S(R)ρ( ϕ_R ).

(1) ρ is induced by  and  fulfills Condition <ref>, iff ρ fulfills the following regularity condition: for every G, H ∈', ξ∈(G,R), ζ∈(H,R), v ∈ V(G), w ∈ V(H)

    = RHζw     ⇒  SGρ(ξ)v = SHρ(ζ)w.

(2) If ρ is induced by  and  fulfills Condition <ref> and (<ref>), then ρ is a strong S-scheme fulfilling (<ref>).

In particular, in the case of R ∈' =, R ∈⊆' ⊆, or R ∈' with ' = or ' = ^*, ρ can be extended to a strong Γ-scheme ρ' with ρ'_G |_(G,R)^(G,S) = ρ_G for all G ∈'. 

(1) If ρ is induced by  and  fulfills Condition <ref>, then, for = RHζw,

    SGρ(ξ)v  =  (  )
      =  ( RGζw )
      =  SHρ(ζ)w.


Now assume that the S-scheme ρ fulfills (<ref>). According to the second part of Theorem <ref>, ρ is induced by , because (<ref>) implies (<ref>) via (<ref>). For , AID yields = R(R)ϕ, hence,

    SGρ(ξ)v (<ref>)= S(R)ρ(ϕ))    =  (  ),

and  fulfills Condition <ref>.

(2) Due to part (1) of the theorem, we only have to show that ρ is strong. Because Condition <ref> implies E(ξ) = G and (<ref>) for all , Proposition <ref> delivers

    ξ(r)    =   ⋃_∈ϕ_R (r)SGρ(ξ)( (  ) ).

for every ξ∈(G,R), G ∈', r ∈ R. ρ_G is thus one-to-one for every G ∈', and ρ is a strong S-scheme. The addendum follows with Proposition <ref>.



In Theorem <ref> in Section <ref>, we will see that with an appropriate choice of (R) and (S), the inverse of Theorem <ref>(2) is true for the constellations of R and ' described in the addendum.



§ THE EV-SYSTEM OF A DIGRAPH
 

Until now, we have specified nothing about the auxiliary digraphs (R) and (S) we have used in the definition of an induced S-scheme. In Section <ref>, we specify (R) and (S) as EV-systems of R and S, and in Section <ref>, we use them in inverting Theorem <ref>(2) for the cases R ∈' =, R ∈⊆' ⊆, and R ∈' with ' = or ' = ^*. Section <ref> is devoted to the replacement of Conditon <ref> by a more handy condition referring to the homomorphism : (R) →(S) only.



 §.§ EV-systems and their properties
 

In mechanical engineering, the exploded-view drawing of an engine shows the relationship or order of assembly of its components by distributing them in the drawing area in a well-arranged and meaningful way. That is exactly what the EV-system of a digraph does with respect to the relations between its vertices:

 
Let R be a digraph and ' ⊆. We define

    _o(R)    ≡ ( v, D, U )  v ∈ V(R), D ⊆_R(v), U ⊆_R(v) .

For ∈_o(R), we refer to the three components of  by _1, _2, and _3, and we define

    ϕ_R : _o(R)    → V(R), 
       ↦_1.

Furthermore, for every G ∈', ξ∈(G,R), we define the mapping

    RGξ : V(G)    →_o(R), 
    
    v    ↦( , ξ[ _G(v) ], ξ[ _G(v) ] ).

The EV-system (R) of R with respect to ' is the digraph with vertex set _o(R) and arc set A( (R) ) defined by

    ∈ A( (R) ) 
    ≡     ∃  G ∈', ξ∈(G,R), vw ∈ A(G) :  = ,   = .


It is thus the arc set of an EV-system which depends on ', whereas the vertex set is independent of it. ϕ_R ∘ = ξ is trivial. In Lemma <ref>, we will see that ϕ_R is strict, as required. As usual, we write  in the case of a fixed digraph G.



Figure <ref> shows the EV-systems of the posets in Figure <ref>(a)-(b) with respect to  and . All loops are omitted in the diagrams. The poset S in (a) is the only one of the four for which the reference class ' makes a difference. The sets ϕ_T(v), v ∈ V(T), T ∈{ R, S }, are encircled and labeled with the respective v. For each point  in the diagrams, _1 is thus given by this label, and we get _2 and _3 by looking at the labels of the starting points and end points of arrows ending and starting in , respectively.

The reader will have noticed that in the definition of the mappings , the restriction to digraphs G contained in ' is unnecessary; we could define the mappings in the same way also for all digraphs G. We did not do so for two reasons. Firstly, we would burden the discussion in this section with discriminations about where ERD is required and where not, and secondly, we would gain nothing with this effort, because starting in Section <ref>, we work with ρ again and are thus restricted to G ∈'.

In the following three lemmata, we collect basic properties of the EV-system (R) with respect to an arbitrary ' ⊆; starting with Definition <ref>, we deal with the EV-system (R) with respect to the classes ' we are mainly interested in.

According to the definition of A( (R) ), the mapping  is a homomorphism from G to (R) for every . For vw ∈ A(G^*) we have ≠, hence ≠, and  is strict. α is thus an S-scheme from R to (R).

 
For all , ∈_o(R)

    ∈ A( (R ) )      ⇒  _1 _1 ∈ A(R), 
    ∈ A( (R)^* )      ⇒  _1 _1 ∈ A( R^* ), _1 ∈_2, _1 ∈_3, 
    ∈ A( (R) )  with _1 = _1      ⇒   = . 
    Furthermore,   R ∈     ⇒  (R) ∈.


Let ∈ A( (R) ). There exist G ∈', ξ∈(G,R), and vw ∈ A(G) with =, =, thus _1 _1 = ∈ A(R). If ∈ A((R)^*), then v ≠ w, hence _1 _1 = ξ(v) ξ(w) ∈ A( R^*). Furthermore, due to v ∈_G(w), we have

    _1   =   ∈ ξ[ _G(w) ]   =  _2   =  _2.

_1 ∈_3 is similarly shown, and (<ref>) is proven. For ∈ A( (R) ) with _1 = _1, (<ref>) and (<ref>) yield =.

Let R ∈, and let ^0, …, ^I be a closed walk in (R)^*. Due to (<ref>), we have ^i-1_1 ^i_1 ∈ A(R^*) for all i ∈I, and the sequence ^0_1, …, ^I_1 is a closed walk in R^*, in contradiction to R ∈.



 
The mapping ϕ_R is a strict homomorphism from (R) to R, and α^R is a simple S-scheme from R to (R) with respect to '. In the case of ERD,

    Rϕ_R_2 ⊆_2 
        and Rϕ_R_3 ⊆_3

for all ∈_o(R).

ϕ_R is a strict homomorphism because of the two first implications in Lemma <ref>. We have already seen that α^R is an S-scheme from R to (R), and due to ξ = ϕ_R ∘ for all G ∈', ξ∈(G,R), α^R is simple. 
In the case of ERD, α_ϕ_R is well defined with

    ϕ_R_3   =  ϕ_R [ _(R)(  ) ]   =  _1 ∈_(R)(  )  (<ref>)⊆ _3.

ϕ_R_2 ⊆_2 is shown in the same way.




 
If ERD holds, then AID is equivalent to

    ∀ ∈_o(R)  ∃  G ∈', ξ∈(G,R), v ∈ V(G) :  = .


“⇒” is trivial. Assume (<ref>). We write ϕ instead of ϕ_R. Let ∈_o(R) and  with =. Due to (<ref>), we have to show _2 ⊆R(R)ϕ_2 and _3 ⊆R(R)ϕ_3 only.

For a ∈_2, there exists a w ∈_G(v) with a = ξ(w). wv ∈ A(G^*) yields ∈_(R)() due to the strictness of , hence

    a   =  ϕ(  )  ∈ ϕ[ _(R)() ]   =  R(R)ϕ_2.

_3 ⊆R(R)ϕ_3 is proven in the same way.



We now show that ERD and AID are fulfilled for the choices of ' and R we are particularly interested in: R ∈' =, R ∈⊆' ⊆, R ∈' =, and R ∈' = ^*. We need the following objects:

 
For every m, n ∈_0, we define the digraph ∈ by

    V(  )     ≡  D ∪{ p }∪ U, 
    
    A(  )     ≡ ( D ×{ p })  ∪ ( { p }× U ).

where D and U are disjoint sets with # D = m, # U = n, and p ∉ D ∪ U.

Furthermore, for ∈_o(R), we define the digraph X()


  * as _2_3 in the case of R ∈' = or R ∈⊆' ⊆;

  * as the transitive hull of _2_3 in the case of R ∈' = ^*;

  * as the transitive hull of _2_3 with loops added for every vertex in the case of R ∈' =.

ι() : V(X()) → V(R) is a mapping sending p to _1 and D and U bijectively to _2 and _3, respectively.




 is thus a bug with m legs, n tentacles and body-vertex p. 23 is shown in Figure <ref>(a), and examples for X() are shown in Figure <ref>(b). Due to ^*, ⊂ and ^* ∩ = ∅, X() is in all four cases uniquely determined by ', and in all four cases, X() is an element of '. In the following corollary, simple properties of X() and ι() are summarized. It is the inconspicuous first statement which will cause some trouble in Section <ref> because it does not have a counterpart for undirected graphs.
 
Let R and ' as in the choices in Definition <ref>. For every ∈_o(R), π∈(X()), the vertex p is a fixed point of π, and D and U are bijectively mapped to D and U, respectively. In consequence, for all ∈_o(R)

    ι()p     =  , 
    ι() ∘πv     =  π(v)  for all  v ∈ V(X()), π∈( X() ) 
    #( X( ) )      =   ( #_2 ! ) · ( #_3 ! )   =  #ι() ∘ππ∈( X() ) .


For _2, _3 ≠∅, p is the only vertex v of X() with _X()(v), _X()(v) ≠∅ (also in the case of _2 ∩_3 ≠∅, cf. Figure <ref>(b)). Also in the other cases, p provides a unique empty-nonempty-combination of _X()(v) and _X()(v) among the vertices v of X(). Therefore, p is a fixed point of every π∈( X() ), and the rest follows.



In an intuitive sense, X() is the most simple digraph G in the respective class ' providing a ξ∈(G,R) with ξp =. If _2 and _3 are not disjoint (which may happen in the case of R ∈' =, cf. Figure <ref>(b)), then ι() is not one-to-one; however, for our purpose it is enough that it is always strict and fulfills the three equations in Corollary <ref>.



 
Let ⊆' ⊆ and R ∈. For all , ∈_o(R),

    ∈ A( (R)^* )      ⇔  _1 ∈_2  and _1 ∈_3, 
    ∈ A( (R) )      ⇔  _1 _1 ∈ A(R).

ERD and AID hold for ' = and for R ∈⊆'.

Because of Lemma <ref>, we have to show “⇐” only in (<ref>) and (<ref>). Let , ∈_o(R) with _1 ∈_2 and _1 ∈_3. Then _1 ∈_R(_1), hence _1 _1 ∈ A(R^*). We take disjoint isomorphic copies G_ and G_ of X() and X() and connect them to a digraph H ∈ as indicated in Figure <ref>: we identify one of the tentacle-vertices of G_ with the body-vertex w of G_, and we identify one of the leg-vertices of G_ with the body-vertex v of G_. The mapping ξ from V(H) to V(R) indicated in the figure is a strict homomorphism from H to R with vw ∈ A( H^* ), =,  and =, thus ∈ A( (R)^* ).

Let _1 _1 ∈ A(R). We construct G ∈ by adding the loop (p,p) to the arc set of X(), and with (<ref>), we get = Gι()p Gι()p∈ A((R)).

For ' =, ERD is trivial, and for R ∈⊆', ERD holds due to (<ref>). In both cases, AID follows with (<ref>) and Lemma <ref>.



 
Let ' be one of the classes  or ^* and let R ∈'. Then, for all , ∈_o(R),

    ∈ A( (R)^* )      ⇔  ∈_2  and ∈_3,

and ERD and AID hold.

Let ∈ A( (R)^* ). _1 ∈_2 and _1 ∈_3 are due to (<ref>). There exist P ∈', ξ∈(P, R), and vw ∈ A(P^*) with = and =.  The transitivity and antisymmetry of P yield _P(v) ⊆_P(w), hence _2 = ξ[ _P(v) ] ⊆ξ[ _P(w) ] = _2. The proof of _3 ⊆_3 runs similarly.

For the proof of “⇐” in (<ref>), take the digraph H in Figure <ref> and remove #_3 of the free tentacle-vertices originating from v and #_2 of the free leg-vertices leading to w. The transitive hull P of the resulting digraph is an element of ^*, and for R ∈^* and ξ corresponding to the homomorphism in Figure <ref>, we have Pξv = and Pξw = with vw ∈ A(P^*). In the case of R ∈, add a loop to A(P) for every vertex. (<ref>) is now shown for both choices of '.

The transitivity of (R) results with (<ref>). Due to ' ⊂, we have (R) ∈ according  to (<ref>), and (R) is antisymmetric. For R ∈^*, the irreflexivity of (R) is due to (<ref>). For R ∈ and ∈_o(R), we have = Gι()p Gι()p∈ A((R)) due to (<ref>).

Again, AID follows with (<ref>) and Lemma <ref>.





 §.§ The inversion of Theorem <ref>(2) 
 

In this section, we prove that Theorem <ref>(2) can be inverted for the choices of R and ' we are particularly interested in:

 
Let R ∈' =, R ∈⊆' ⊆, or R ∈' = ' with ' = or ' = ^*, and let (R) and (S) be the EV-Systems  of R and S. If ρ is a strong S-scheme from R to S fulfilling (<ref>), then ≡S(R)ρ( ϕ_R ) fulfills Condition <ref>, induces ρ, and is one-to-one.

The theorem extends also to the sub-classes of  mentioned at the end of Section <ref>.

For the constellations of R and ' described in the theorem, ERD and AID are fulfilled according to the Propositions <ref> and <ref>. If ρ fulfills (<ref>), then  fulfills Condition <ref> and induces ρ according to Theorem <ref>(1). What is left to show is that the additional assumption “ρ strong” implies “ one-to-one”.

It is beneficial to replace the description = S(R)ρ( ϕ_R ) by a more intuitive one. We have 

    Rϕ AID=  (<ref>)= RX()ι()p

for every ∈_o(R), hence

    ( )   =  S(R)ρ( ϕ_R )  (<ref>)= SX()ρ(ι())p  for all ∈(R).

This is the description of  we are using in what follows. The point p and the sets D and U have been specified in the definition of X().
 
Let ∈_o(R). Then, for every π∈(X()),

    ρ(ι() ∘π)(v) 
         =  ρ(ι())(π(v))
      for all  v ∈ V(X()),

and

    ρ(ι() ∘π)(p)      =  ()_1, 
    ρ(ι() ∘π)[D]      =  ()_2, 
    ρ(ι() ∘π)[U]      =  ()_3,


Let π∈(X()). According to (<ref>), we have Rι() ∘πv = Rι()π(v) for all v ∈ V(X()). Equation (<ref>) delivers Sρ( ι() ∘π )v = Sρ(ι())π(v) for all v ∈ V(X()), and (<ref>) follows.

p is a fixed point of π according to Corollary <ref>, hence Sρ( ι() ∘π )p = Sρ(ι())p, and the first equation follows. Furthermore

    ρ(ι() ∘π)[D]
         =  ρ(ι() ∘π)(d)  d ∈ D  (<ref>)= ρ(ι())(π(d))  d ∈ D 
         =  ρ(ι())(d)  d ∈ D   =  ρ(ι())[D]
      =  Sρ(ι())p_2
     (<ref>)= (  )_2.

The last equation is proven in the same way.



 
Let ∈_o(R). If ρ is strong, then, for every π∈(X()), the mapping ρ( ι() ∘π) is one-to-one on D and U. In particular, X(  ) ≃ X( (  ) ).

Let ∈_o(R) and π∈(X()). Assume ρ( ι() ∘π)(c) = ρ( ι() ∘π)(d) for c, d ∈ D. We define the automorphism ξ : X() → X() by

    ξ(v)    ≡π(v),    if v ∈ V(X()) ∖{ c, d }; 
    π(d),    if v = c; 
    π(c),    if v = d.

According to (<ref>), we have ρ(ι() ∘π)(v) = ρ(ι())(π(v))
and ρ(ι() ∘ξ)(v) = ρ(ι())(ξ(v)) for all v ∈ V(X()). Thus, for every vertex v ∈ V( X() ) ∖{ c, d },

    ι() ∘ξv    =  ι()ξ(v)  =  ι()π(v)
        =  ι() ∘πv. 
    
    Furthermore,  ι() ∘ξc    =  ι()ξ(c)  =  ι()π(d)
        =  ι() ∘πd  =  ι() ∘πc . 
    
    and similarly  ι() ∘ξd    =  ι() ∘πd,

hence ρ(ι() ∘ξ) = ρ(ι() ∘π). Because ρ is strong, we have ι() ∘ξ = ι() ∘π, thus c = d, because all three mappings are one-to-one on D. In the same way we see that ρ( ι() ∘π) is one-to-one on U. Now the equations (<ref>) yield X() ≃ X(()).



The following lemma finishes the proof of Theorem <ref>:

 
If ρ is strong, then  is one-to-one.
 
Let , ∈(R) with (  ) = (  ). According to Lemma <ref>, we have X() ≃ X(()) = X(()) ≃ X(). X() and X() are thus isomorphic, and due to X(), X() ∈', we have X() = X(). Let G ≡ X() and

    ()     ≡ ι() ∘ππ∈(G), 
    ()     ≡ ι() ∘ππ∈(G) .

With m ≡#_2, n ≡#_3, (m !) · (n !) is according to (<ref>) the cardinality of ( G ), (), and (). ≡() ∪() is a subset of (G, R) with #≥ (m !) · (n !); equality holds iff =. 

ρ_G[  ] is a subset of (G,S), and due to Corollary <ref> and Lemma <ref>, we have #ρ_G[  ] = #(G) = (m !) · (n !) (also in the case of ()_2 ∩()_3 ≠∅). Because ρ is strong, we have # = #ρ_G[  ],  hence =.



Theorem <ref> provides more than the pure inversion of Theorem <ref>(2): it states “ is one-to-one”, whereas in Theorem <ref>(2), the weaker condition “() = (  ) ⇒_1 = _1” is used. The reason is that in the situation of Theorem <ref>, the extremely simple (and thus: powerful) objects X() belong to ': it are the properties of X() and ι() summarized in Corollary <ref> which yield the stronger result.



 §.§ The replacement of Condition <ref>
 

We have introduced Condition <ref> in order to close the gap left by Proposition <ref> to η being strong. However, Condition <ref> is unwieldy to check because it refers to how Gξv looks for all . It is desirable to have more handy conditions referring to the homomorphism : (R) →(S) only. We need

 
Let R, S ∈, ' ⊆. If : (R) →(S) is a strict homomorphism between the EV-systems of R and S, then

    Sη(ξ)v_2 ⊆(  )_2      and Sη(ξ)v_3 ⊆(  )_3,

for all , where η(ξ) ∈(G,S) is defined as in Definition <ref>. 

Let a ∈_2. There exists a w ∈_G(v) with η(ξ)(w) = a. We have ∈ A( (R)^* ), hence (  ) (  ) ∈ A( (S)^* ), and (<ref>) yields a = η(ξ)(w) = (  )_1 ∈(  )_2. The second inclusion is shown in the same way.



Now we can prove

 
Let R, S ∈, ' ⊆, and let : (R) →(S) be a strict homomorphism between the EV-systems of R and S. Assume that for ∈_o(R)

    #(  )_2     ≤ #_2, 
    #(  )_3     ≤ #_3,

and

    ∀ , ∈_(R)(  ) : (  )_1 = (  )_1     ⇒ _1 = _1, 
    ∀ , ∈_(R)(  ) : (  )_1 = (  )_1     ⇒ _1 = _1.

Then = (  ) for all  with =. In particular,  fulfills Condition <ref> if (<ref>) and (<ref>) hold for all ∈_o(R).

Let  with =. For every w ∈_G(v), we have ∈_(R)(  ) due to the definition of A( (R) ), hence

    #_2        =  #ξ( w )  w ∈_G(v)  (<ref>)≤ #(  )_1  w ∈_G(v) 
           =  # w ∈_G(v)   =  #_2 
       (<ref>)≤ #(  )_2
     (<ref>)≤ #_2,

thus #_2 = #(  )_2. Now (<ref>) delivers _2 = (  )_2.
The proof of _3 = (  )_3 is similar, and = (  ) is shown. The addendum is clear.





As an application, Figure <ref> shows digraphs R and S together with their EV-systems with respect to . A homomorphism  between the EV-systems is indicated by corresponding bold and dotted shafts of the arrows. The homomorphism fulfills (<ref>) and (<ref>) for all ∈_o(R), hence Condition <ref>. Because it is additionally one-to-one, it induces a strong S-scheme from R to S with respect to   fulfilling (<ref>) which can be extended to a strong Γ-scheme from R to S (Theorem <ref>(2)). At the end of Section <ref>, we will take the example up again.

Let us examine the assumptions in Proposition <ref> more closely! If  fulfills Condition <ref>, then η fulfills (<ref>) according to Theorem <ref>(1). Looking at the second and third equation in (<ref>) with π = 𝕀_V(X()), we conclude that (<ref>) is necessary for Condition <ref> for the choices of R and ' we are mainly interested in. However,  (<ref>) is not necessary, as we will show now.

For every flat poset Q, we have _2 = ∅ or _3 = ∅ for every ∈(Q), and (Q) is a flat poset, too. Let R be a flat connected poset with at least three points, and let C be the two-element chain with V(C) = { 0, 1 } and A(C) = { (0,0), (0,1), (1,1) }. Every strict homomorphism : (R) →(C) sends the “basement” and the “upper floor“ of (R) to the basement and the upper floor of (C), respectively. Following this rule, we define : (R) →(C) by

    (  )    ≡
    (0, ∅, { 1 } ),    if _3 ≠∅ (basement to basement); 
    
    (1, { 0 }, ∅ ),    if _2 ≠∅ (upper floor to upper floor); 
    
    (0, ∅, ∅),    otherwise(isolated points to an isolated point).

 is a strict homomorphism fulfilling (<ref>) for all ∈(R). But because R is connected and contains at least three points,  violates (<ref>). However, for all P ∈, ξ∈(P,R), v ∈ V(P),

    _2     = (  )_1  w ∈_P(v) 
        = 
    ∅,    if _P(v) = ∅; 
    { 0 },    otherwise
        = (  )_2.

_3 = (  )_3 is shown in the same way, and  fulfills Condition <ref>.



§ THE REARRANGEMENT METHOD
 

In <cit.>, the author has developed a method how to rearrange a digraph R in such a way that the relation R  S with respect to  holds for the digraph S resulting from the rearrangement. In Section <ref>, we see that ρ is in fact induced by a strict homomorphism : (R) →(S) between the EV-systems of R and S. We describe  and analyse its properties. In  Section <ref>, we discuss as examples the pairs of posets in Figure <ref>(a)-(b) under these view points.



 §.§ ρ as an induced S-scheme
 



The concept of the rearrangement method is illustrated in Figure <ref>. We have a digraph R and sets X, Y, M ⊆ V(R) with X ∩ M = ∅, Y ∩ M = ∅. We build a new digraph S by replacing all arcs between M and X in R by arcs between M and Y. In detail:

 
We agree on the following:


  * R = (Z, A(R)) is a digraph.

  * We have disjoint subsets X and M of Z.

  * There is a subset Y ⊆ Z with

    M ∩ Y     = ∅ , 
    
    M ∩ N_R(y)     = ∅ for all  y ∈ Y,

and β : X → Y is a mapping.

  * We define S as the digraph with V(S) = Z and 

    A(S)    ≡   A_r  ∪  A_d  ∪   A_u 
    where  A_r    ≡  A(R) ∖( ( M × X ) ∪ ( X × M ) ), 
    
    A_d    ≡  m β(x)  m x ∈ A(R) ∩ ( M × X ), 
    
    A_u    ≡ β(x) m  x m ∈ A(R) ∩ ( X × M ).




 
For every G ∈ and every ξ∈(G,R), we define the mapping ρ_G(ξ) : V(G) → Z by

    ∀ v ∈ V(G) : ρ_G(ξ)(v)    ≡   β(),    if  v ∈ B_ξ, 
    ,    otherwise.

where

    B_ξ ≡  v ∈ V(G) ∈ X and ξ[ N_G(v) ] ∩ M ≠∅,

Assume additionally to the assumptions in Definition <ref>, that β : R |_X → R |_Y is a bijective homomorphism and

    ∀ x ∈ X : _R(x) ∖ M ⊆_R(  β(x) )  and _R(x) ∖ M⊆_R( β(x) ).

Then ρ is a strong S-scheme from R to S with respect to  which can be extended to a strong Γ-scheme ρ' with ρ'_G |_(G,R)^(G,S) = ρ_G for all G ∈. 


It is = (, ξ[ _G(v) ], ξ[ _G(v) ]) which determines  for every . Therefore, (<ref>) holds, and because ERD and AID are fulfilled for  and R according to Proposition <ref>, ρ is according to Theorem <ref> induced by

    : (R)    →(S), 
       ↦S(R)ρ(ϕ).

We want to describe (  ) explicitely. We have

    B_ϕ   =   ∈(R)_1 ∈ X, ϕ[ N_(R)(  )] ∩ M ≠∅,

hence, due to (<ref>),

    (  )_1   =    =   β(_1),    if ∈ B_ϕ, 
    _1,    otherwise.


For the determination of (  )_2 = ρ(ϕ)[ _(P)() ], (<ref>) yields

    _(P)()       =   ∈(P) _1 ∈_2  and _1 ∈_3.

Looking at the definition of B_ϕ and (<ref>), we see  _2 ∖ X ⊆(  )_2. Furthermore,


  * _1 ∈ M: Then every ∈_(P)() with _1 ∈ X belongs to B_ϕ and we conclude (  )_2 = ( _2 ∖ X)  ∪ β[ _2 ∩ X ].

  * _1 ∉ M: Let x ∈_2 ∩ X. We have ( x, ∅, {_1 }) ∈( _(P)() ) ∖ B_ϕ, thus x ∈(  )_2. Additionally, under all elements of _(P)() with first component x, it is (x, _R(x), _R(x)) which has the largest second and third component; therefore, 
β( x ) ∈(  )_2, if the intersection N_R(x) ∩ M is not empty.

Making the same considerations for (  )_3, we get all together

    (  )_1     = , 
    (  )_2     =
    
    ( _2 ∖ X )  ∪ β[ _2 ∩ X ]                    if _1 ∈  M;    
    _2  ∪ β[  x ∈_2 ∩ X  N_R(x) ∩ M ≠∅]   otherwise;    
    (  )_3     =
    
    ( _3 ∖ X )  ∪ β[ _3 ∩ X ]                    if _1 ∈  M;    
    _3  ∪ β[  x ∈_3 ∩ X  N_R(x) ∩ M ≠∅]  otherwise.


Because ρ is induced and strong, Theorem <ref>(1) and Theorem <ref> yield

    fulfills Condition <ref>
    ⇔     ρ fulfills (<ref>)
    ⇒      is one-to-one.

But in many cases, the homomorphism  resulting from the rearrangement method will not be one-to-one, because, in the case of X ∩ Y = ∅, the following lemma states that  will be one-to-one iff every non-isolated x ∈ X is either encapsulated by M or by V(R) ∖ M:

 
Let R, S, and ρ as in Theorem <ref> and ≡α_ρ(ϕ). If 

    ∀  x ∈ X :  N_R(x) ∩ M = ∅    or  N_R(x) ∖ M = ∅.

then  is one-to-one. In the case of X ∩ Y = ∅, the inverse is true, too.

“⇒”: If (<ref>) holds, then the equations (<ref>) become

    (  )_1     = , 
    (  )_2     =
    
    ( _2 ∖ X )  ∪ β[ _2 ∩ X ]    if _1 ∈  M; 
     _2    otherwise;
    
    (  )_3     =
    
    ( _3 ∖ X )  ∪ β[ _3 ∩ X ]    if _1 ∈  M; 
     _3    otherwise.

Let ∈_o(R). If (  )_1 ∈ M, then _1 = (  )_1 due to (<ref>), and _2 ∩ Y = ∅ = _3 ∩ Y due to (<ref>). Therefore,

    _2      =  ( (  )_2 ∖ Y )  ∪ β( (  )_2 ∩ Y ), 
    _3      =  ( (  )_3 ∖ Y )  ∪ β( (  )_3 ∩ Y ).

If (  )_1 ∉ M, then _1 ∉ M and ()_2 = _2, ()_3 = _3. If the set ( _2 ∪_3 ) ∩ M is empty, then the triplet  cannot be an element of B_ϕ, hence _1 = ( _1 ). And in the case of ( _2 ∪_3 ) ∩ M ≠∅, we have _1 = β( (  )_1 ) for (  )_1 ∈ Y (use (<ref>)) and _1 = (  )_1 for (  )_1 ∉ Y.

“⇐”: Assume that (<ref>) does not hold for x ∈ X. Select a vertex v ∈ N_R(x) ∖ M. In the case of v ∈_R(x), define

    ≡  ( v, ∅, { x } ), 
        ≡  ( v, ∅, { x, β(x) } ).

Then ∈_o(R), and due to v ∈_R( x ) ∖ M (<ref>)⊆_R( β(x) ), we also have ∈_o(R). Due to X ∩ Y = ∅, we have ≠, but the formulas in (<ref>) yield (  ) = ( v, ∅, { x, β(x)} ) = (  ) (for the latter equality, we need X ∩ Y = ∅ again). In the case of v ∈_R(x), work with ≡ ( v, { x }, ∅ ), ≡ ( v, { x, β(x)}, ∅ ).



The condition X ∩ Y = ∅ cannot easily be skipped in this Lemma. For X = Y and β being the identity mapping of X, the rearrangement method delivers S = R, ρ is the trivial Γ-scheme with ρ_G = 𝕀_(̋G,R) for all G ∈, and  is the identity mapping of _o(R) according to (<ref>) and (<ref>).  is thus one-to-one, whatever the structure of R is.

We want to show that the digraph S in Figure <ref> in Section <ref> cannot be constructed by the rearrangement of the digraph R in the figure. Due to (<ref>) and (<ref>), neither the set M nor the set Y can contain the vertex 1. These sets must be singletons, one of them containing the vertex 0, the other one the vertex 2. If the set X contains 1, the rearrangement of R results in a digraph with V-shaped or Λ-shaped diagram (and Theorem <ref> cannot be applied because (<ref>) is violated). And in the case of 1 ∉ X, we have X = ∅ or X = Y, and the rearrangement method produces nothing than R.

On the one hand, we have thus a rearrangement method producing induced strong S-schemes ρ for which  does not fulfill Condition <ref> in many cases, and on the other hand, we have Theorem <ref>(2) which states that many homomorphisms  fulfilling Condition <ref> induce a strong S-scheme ρ. There is still something to do in characterizing digraphs R and S with a strong induced S-scheme between them.



 §.§ Examples
 



Figure <ref> shows the Hasse-diagrams of eight pairs of posets R and S for which R  S has been shown in <cit.> by means of the rearrangement method described in the previous section. The respective one-element vertex sets X, Y, and M are marked. In all cases, the respective strong S-scheme ρ from R to S is induced by the strict homomorphism : (R) →(S) described by the equations (<ref>).



Figure <ref> shows the Hasse-diagrams of the posets R and S from Figure <ref>(a)-(b), their EV-systems, and the respective strict homomorphism  between them; the pairs are the second and the sixth one in Figure <ref>.

In Figure <ref>(a), the main part of  is indicated by the bold lines in the EV-systems.  is one-to-one and by means of Proposition <ref>, it is easily seen that it fulfills Condition <ref>, too. According to Theorem <ref>, ρ fulfills (<ref>). We have 

    B_ϕ  =  { ( x, ∅, { m } )}

and the total homomorphism is given by


5cm

∈_o(R)     (  ) ∈_o(S) 

( x, ∅, ∅ )    
( x, ∅, ∅ ) 

( x, ∅, { m } )    
( y, ∅, { m } ) 

( p, ∅, { m } )    
( p, ∅, { m } ) 

( p, ∅, { m, y } )    
( p, ∅, { m, y } ) 

( p, ∅, { m } )    
( p, ∅, { m } ) 

( p, ∅, ∅ )    
( p, ∅, ∅ ) 

 
5cm

∈_o(R)     (  ) ∈_o(S) 

( m, ∅, ∅ )     
( m, ∅, ∅ ) 

( m, { x }, ∅ )     
( m, { y }, ∅ ) 

( m, { x, p }, ∅ )     
( m, { y, p }, ∅ ) 

( m, { p }, ∅ )     
( m, { p }, ∅ ) 

( y, { p }, ∅ )     
( y, { p }, ∅ ) 

( y, ∅, ∅ )     
( y, ∅, ∅ ) 

 


The pairs of posets (C1) and (C3)-(C5) in Figure <ref> have the same properties: the respective strong S-scheme ρ fulfills (<ref>) and is induced by a one-to-one homomorphism from (R) to (S) fulfilling Condition <ref>.

For the example in Figure <ref>(b), three point mappings are indicated by arrows. The rest of  is easily seen as follows: The sub-poset of R drawn with bold lines is mapped to the isomorphic bold-lined sub-poset of S, whereas the sub-poset of R drawn with dotted lines is flipped and mapped to the M-shaped dotted sub-poset of S; the two shaded points ( p, { x }, ∅ ) and ( p, { x, y }, ∅ ) of (R) are both mapped to the shaded point ( p, { x, y }, ∅ ) of (S). According to (<ref>),  cannot fulfill Condition <ref> and ρ cannot fulfill (<ref>). The total homomorphism is listed in the following table; we have 

    B_ϕ  =  { ( x, ∅, { m } ), ( x, ∅, { m, p } ) }.

5cm

∈_o(R)     (  ) ∈_o(S) 

( x, ∅, ∅ )    
( x, ∅, ∅ ) 

( x, ∅, { m } )    
( y, ∅, { m } ) 

( x, ∅, { m, p } )    
( y, ∅, { p, m } ) 

( x, ∅, { p } )    
( x, ∅, { p } ) 

( y, ∅, ∅ )    
( y, ∅, ∅ ) 

( y, ∅, { q } )    
( y, ∅, { q } ) 

( y, ∅, { p, q } )    
( y, ∅, { p, q } ) 

( y, ∅, { p } )    
( y, ∅, { p } ) 

 
5cm

∈_o(R)     (  ) ∈_o(S) 

( m, ∅, ∅ )     
( m, ∅, ∅ ) 

( m, { x }, ∅ )     
( m, { y }, ∅ ) 

( p, ∅, ∅ )     
( p, ∅, ∅ ) 

( p, { x }, ∅ )     
( p, { x, y }, ∅ ) 

( p, { x, y }, ∅ )     
( p, { x, y }, ∅ ) 

( p, { y }, ∅ )     
( p, { y }, ∅ ) 

( q, ∅, ∅ )     
( q, ∅, ∅ ) 

( q, { y }, ∅ )     
( q, { y }, ∅ ) 

 


Let ≡ ( p, {x}, ∅ ) ∈_o(R) and ≡ ( p, { x, y }, ∅ ) ∈_o(R). For all points ∈_o(R) ∖{, }, the conditions in Proposition <ref> are fulfilled, but  violates (<ref>) and  violates (<ref>). The points  and  are thus the only points ∈_o(R) for which  may exist with = and ≠(  ).



Figure <ref> shows the Hasse-diagrams of three posets C, V, and N, and for each of them a strict homomorphism to R and its image resulting under η. C is the two-element chain defined in Section <ref>, and V and N are the posets with V- and N-shaped Hasse-diagrams. In the following tables, the objects of interest in (R) and (S) are listed.



v ∈ V(C)          (  ))     ξv

0     ( x, ∅, { p } )     ( x, ∅, { p } )     ( x, ∅, { p } ) 

1     ( p, { x }, ∅ )     ( p, { x, y }, ∅ )     ( p, { x }, ∅ ) 





v ∈ V(V)     ζx     ( ζx )     ζx 

00     ( x, ∅, { m, p } )     ( y, ∅, { p, m} )     ( y, ∅, { p, m} ) 

10     ( m, { x }, ∅ )     ( m, { y }, ∅ )     ( m, { y }, ∅ ) 

01     ( p, { x }, ∅ )     ( p, { x, y }, ∅ )     ( p, { y }, ∅ ) 





v ∈ V(N)     θx     ( θx )     θx 

100     ( y, ∅, { p } )     ( y, ∅, { p } )     ( y, ∅, { p } ) 

001     ( x, ∅, { m, p } )     ( y, ∅, { p, m } )     ( y, ∅, { p, m } ) 

101     ( p, { x, y }, ∅ )     ( p, { x, y }, ∅ )     ( p, { y }, ∅ ) 

011     ( m, { x }, ∅ )     ( m, { y }, ∅ )     ( m, { y }, ∅ ) 




We have thus ξ1 = ζ01 =, but 
(  ) ≠ξ1≠ζ01≠(  ), and we have θ101 =, but θ101≠(  ). 

At the end of this section, we show that no strong S-scheme ρ exists from R to S fulfilling (<ref>). Assume that such a strong S-scheme exists. According to Theorem <ref>, ρ is induced by ≡α_ρ(ϕ). Now let P ≡ R and let ξ≡𝕀_V(R) be the identity mapping of R. For ξx = ( x, ∅, { m, p } ) and ξy = ( y, ∅, { p, q } ), Lemma <ref> delivers #( ξx )_3 = 2 = #( ξy )_3. Because y is the only point v ∈ V(S) with #_S(v) > 1, we conclude

    η(ξ)(x)   =  ( ξx )_1   =   y
       =  ( ξy )_1   =  η(ξ)(y).

Therefore,

    ξp_2   =  η(ξ)[ _G(p) ]   =  η(ξ)[ { x, y } ]   =  { y }.

But for ξp = (p, {x,y},∅), Lemma <ref> delivers #( ξp )_2 = 2. We have thus ξp_2 ≠( ξp )_2, and  does not fulfill Condition <ref>. But due to Theorem <ref>, this is a contradiction to ρ being a strong S-scheme fulfilling (<ref>).

Also for the pairs (C7) and (C8) in Figure <ref>, the respective  is not one-to-one and does not fulfill Condition <ref>, as is easily seen by means of Lemma <ref>. In consequence, the respective S-scheme does not fulfill (<ref>). For the pair R, S in (C7), we see by inspection of 𝕀_V(R) and the consequences for η( 𝕀_V(R) ) that there exists no strong S-scheme from R to S fulfilling (<ref>).



§ UNDIRECTED GRAPHS
 

Let  be a representative system of the non-empty finite symmetric digraphs and  a representative system of the non-empty finite undirected graphs. Already in <cit.>, we have exploited the fact that  and  are perfect twins because every pair (v,w), (w,v) in the arc set of a symmetric digraph corresponds uniquely to the edge {v,w} of an undirected graph and vice versa. In this way, we transferred all concepts and results about directed graphs to undirected graphs, as long as they were compatible with symmetry. Because the class ⊂ refers to antisymmetry, we had to replace it by the class _o ⊂ defined as

    _o  ≡  G ∈ G^*   does not contain a cycle of odd length.

Denoting with _̋u and _u the sets of homomorphisms and of strict homomorphisms of undirected graphs, Theorem <ref> became
 
Let R ∈ and ' ⊆. Then, for all S ∈, the equivalence

    R     S   with respect to '
    ⇔  #_u(G,R)    ≤#_u(G,S)   for all  G ∈',

and the implication

    #_u(G,R)    ≤#_u(G,S)   for all  G ∈' 
    ⇒  #_̋u(G,R)    ≤#_̋u(G,S)   for all  G ∈'

hold if

    R    ∈' = , 
    or   R    ∈_o ⊆' ⊆.



Also for the present article, most of the concepts and results can be directly transferred to undirected graphs just by replacing “digraph” by “undirected graph”, “'” and “” by “' and “”, and “$̋” and “”by “_̋u” and “_u”. In particular, S-schemes, simple S-schemes, induced S-schemes, and Condition <ref> can be defined for undirected graphs in this way, and all results of Section <ref> can stereotypically be translated into results about undirected graphs. This includes in particular the main results of this section: the characterization of induced S-schemes provided in the Theorems <ref> and <ref>.

Also in the Sections <ref> and <ref>, the first step is to replace symbols, but now also the concepts change slightly. The definition of the EV-system for undirected graphs has to be modified in an obvious manner. Using the symbolA(G)also for the edge set of an undirected graphG, we define

Let R be an undirected graph and ' ⊆. We define

    _o(R)    ≡ ( v, D )  v ∈ V(R), D ⊆  N_R(v) .

For ∈_o(R), we refer to the two components of  by _1 and _2, and we define

    ϕ_R : (R)    → R, 
       ↦_1.

Furthermore, for every G ∈', ξ∈_u(G,R), we define the mapping

    RGξ : V(G)    →_o(R), 
    
    v    ↦( , ξ[ N_G(v) ] ).

The  EV-system (R) of R with respect to ' is the undirected graph with vertex set _o(R) and edge set A( (R) ) defined by

    {, }∈ A( (R) ) 
    ≡     ∃  G ∈', ξ∈_u(G,R), {v, w}∈ A(G) :  = ,   = .

Again,αturns out to be a simple S-scheme fromRto(R), and Lemma <ref> becomes

For all , ∈_o(R),

    ∈ A( (R ) )      ⇒  _1 _1 ∈ A(R), 
    ∈ A( (R)^* )      ⇒  _1 _1 ∈ A( R^* ), _1 ∈_2, _1 ∈_2, 
    _1 = _1      ⇒   = .  
    Furthermore,   R ∈_o      ⇒  (R) ∈_o.

(For the proof of(R) ∈_o, start with a walk^0, …, ^Iof odd length in(R)^*, proceed as in the original, and observe, that in the case of^0 = ^I, the sequence^0_1, …, ^I_1is a cycle of odd length inR^*.)

In the following Lemma <ref> and Lemma <ref>, we just have to skip everything indexed with3. Now we define the objectsX() ∈_o:

For every m ∈_0, we define the undirected graph X_m ∈_o by

    V( X_m )     ≡  D ∪{ p }, 
    
    A( X_m )     ≡ { p, d } d ∈ D ,

where D is a set with # D = m and p ∉ D.

Furthermore, for ∈_o(R), we define

    X()  ≡  X_#_2.
ι() : V(X()) → V(R) is a mapping sending p to _1 and D bijectively to _2.

From now on, we have to proceed more carefully. The reason is the undirected graphX_1defined up to isomorphism by

    V(X_1)     ≡ { p, d }with  p ≠ d, 
    
    A(X_1)     ≡ {{ p, d }}.(X_1)contains  two automorphisms𝕀_V(X_1)andχ, the latter one interchangingpandd. The vertexpis not a fixed point ofχ, and we have to introduce a case discrimination in rewriting Corollary <ref>:

Let R and ' as in the choices in Theorem <ref>. For every ∈_o(R), π∈(X()), we have

    ι()p     =  , 
    ι() ∘πv     =  π(v)  for all  v ∈ V(X()), π∈( X() ).

 Furthermore,

    #( X( ) )   =  #ι() ∘ππ∈( X() )   = 
      2    if  X() ≃ X_1, 
    #_2 !    if  X() ≄X_1.

For X() ≄X_1, the vertex p is a fixed point of every π∈(X(), and π maps D bijectively to D.


To point out the difference: Definition <ref> assigns the undirected graphX() = X_1to= ( p, {d}) ∈_o(X_1). However, if we regardX_1as symmetric digraphY_1withV(Y_1) = { p, d },A(Y_1) = { (p,d), (d,p) }, then Definition <ref> assigns to= (p,{d},{d}) ∈_o(Y_1)the  antisymmetric digraphX() ≃X_1^1 ∈with  three vertices and# ( X_1^1) = 1, cf. Figure <ref>(b).

Proposition <ref> remains nearly unchanged:


Let _o ⊆' ⊆ and R ∈. For all , ∈_o(R),

    ∈ A( (R)^* )      ⇔  _1 ∈_2  and _1 ∈_2, 
    ∈ A( (R) )      ⇔  _1 _1 ∈ A(R).

ERD and AID hold for ' =, and for R ∈_o ⊆'.


Now we come to the counterpart of Theorem <ref>, which we get by just replacing symbols:

Let R ∈' = or R ∈_o ⊆' ⊆, and let (R) and (S) be the EV-Systems  of R and S ∈. If ρ is a strong S-scheme from R to S fulfilling (<ref>), then ≡S(R)ρ( ϕ_R ) fulfills Condition <ref>, induces ρ, and is one-to-one.


However, in the proof, we have to take into account the special status ofX_1. Corollary <ref> becomes

Let ∈_o(R). Then, for every π∈(X()),

    ρ(ι() ∘π)(v) 
         =  ρ(ι()(π(v))
      for all  v ∈ V(X()).

In the case of X() ≄X_1, we have

    ρ(ι() ∘π)(p)      =  ()_1, 
    ρ(ι() ∘π)[D]      =  ()_2.

and in the case of X() ≃ X_1, we have (  ) = ( a, { b } ) with ab ∈ A(S^*) and

    a      =  ι()p  =  ι() ∘χ d , 
    
    b      =  ι()d  =  ι() ∘χ p .


Lemma <ref> remains unchanged:

Let ∈_o(R). If ρ is strong, then, for every π∈(X()), the mapping ρ( ι() ∘π) is one-to-one on D. In particular, X(  ) ≃ X( (  ) ).

(ForX() ≄X_1, run the proof as in the original using Corollary <ref>; forX() ≃X_1, the statement aboutDis trivial, and X( ) ≃X( ( ) )holds due to the addendum in Corollary <ref>.)

Finally, in the proof of Lemma <ref>, we have to introduce a case disrimination again:


If ρ is strong, then  is one-to-one.
 Let, ∈(R)with( ) = ( ). According to Lemma <ref>, we haveX() ≃X(()) = X(()) ≃X().X()andX()are thus isomorphic, and due toX(), X() ∈', we haveX() = X(). LetG ≡X()and

    ()     ≡ ι() ∘ππ∈(G), 
    ()     ≡ ι() ∘ππ∈(G) .

ForX() ≄X_1, proceed as in the original. Now assumeX() ≃X_1. According to Corollary <ref>, the cardinality of( G ),(), and()is2.≡() ∪()is a subset of(G, R)with# = 4in the case of{ _1 } ∪_2 ≠ { _1 } ∪_2and# = 2in the case of{ _1 } ∪_2 = { _1 } ∪_2.ρ_G[ ]is a subset of_u(G,S), and due to() = ()and the last two equations in Corollary <ref>, all elements ofρ_G[ ]mapV(G) = { p, d }bijectively to the same two-element-subset{ v, w }ofV(S). We conclude# ρ_G[ ] ≤2, and becauseρis strong, we have# = # ρ_G[ ], hence{ _1 } ∪_2 = { _1 } ∪_2.

Let= ( v, { w } ). If= ( w, { v } ), then∈A((R)^*)according to Proposition <ref> in contradiction to( ) = ( ). Therefore,= .


In Lemma <ref>, everything indexed with3has to be skiped, and the replacement proposition becomes

Let : (R) →(S) be a strict homomorphism between the EV-systems of R and S. Assume that for ∈_o(R)
    #(  )_2     ≤ #_2

and

    ∀ , ∈ N_(R)(  ) : (  )_1 = (  )_1     ⇒ _1 = _1.

Then = (  ) for all G ∈', ξ∈_u(G,R), v ∈ V(G) with =. In particular,  fulfills Condition <ref> if these conditions hold for all ∈_o(R).


We have already seen in <cit.>, that also the rearrangement method recalled in Section <ref> can be rewritten for undirected graphs. ForR ∈with the properties described in Definition <ref>, defineS ∈by

    V(S)    ≡  Z, 
    
    A(S)    ≡ ( A(R) ∖ A_M,X)  ∪  A_b, 
    where     A_M,X   ≡  e ∈ A(R)  e ∩ M ≠∅ and  e ∩ X ≠∅
    and        A_b    ≡  ( e ∩ M ) ∪β[ e ∩ X ]  e ∈ A_M,X.

Then the counterpart of Theorem <ref> deliversR Sif we replace (<ref>) by

    ∀ x ∈ X :     N_R(x) ∖ M ⊆ N_R( β(x) ).

With these modifications, all results and formulas in Section <ref> remain valid if we just make the usual rewritings and skip everything indexed with3.


xxBorgs_etal_2006 C. Borgs, J. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi: Counting Graph Homomorphisms. In: M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr eds.,  Topics in Discrete Mathematics (Algorithms and Combinatorics  26), Springer (2006), 315–371.

Borgs_etal_2008 C. Borgs, J. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi: Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing.  Advances in Mathematics 219 (2008), 1801–1851.

Borgs_etal_2012 C. Borgs, J. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi:  Convergent sequences of dense graphs II. Multiway Cuts and Statistical Physics. Ann. of Math.  176 (2012), 151–219. 

Cai_Govorov_2020 J. Cai and A. Govorov: On a theorem of Lovász that hom(·,H) determines the isomorhphism type of H. ITCS (2020).

aCampo_2018 F. a Campo: Relations between powers of Dedekind numbers and exponential sums related to them.  J. Int. Seq. 21 (2018), Article 18.4.4.

aCampo_toappear_0 F. a Campo: Criteria for the less-equal-relation between partial Lovász-vectors of digraphs. arXiv:2008.03279v2 (2020).

Dvorak_2010 Z. Dvořák: On Recognizing Graphs by Numbers of Homomorphisms.  Journal of Graph Theory 64 (2010), 330–342.

Fisk_1995 S. Fisk: Distinguishing graphs by the number of homomorphisms.  Discussiones
Mathematicae - graph theory 15 (1995), 73–75.

Freedman_etal_2007 M. Freedman, L. Lovász, and A. Schrijver: Reflection positivity, rank connectivity, and homomorphism of graphs.  J. Amer. Math. Soc. 20 (2007), 37–51.

Hell_Nesetril_2004 P. Hell and J. Nešetřil:  Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications  28, Oxford University Press (2004).

Lovasz_1967 L. Lovász: Operations with structures.  Acta Math. Acad. Sci. Hungar. 18 (1967), 321–328.

Lovasz_2006 L. Lovász: The rank of connection matrices and the dimension of graph algebras.  European Journal of Combinatorics 27 (2006), 962–970.

Lovasz_Szegedy_2008 L. Lovász and B. Szegedy. Contractors and connectors of graph algebras.  Journal of Graph Theory 60 (2009), 11–-30.

Schrijver_2009 A. Schrijver: Graph invariants in the spin model.  J. Combin. Theory B 99 (2009), 502–511.

Schroeder_2016 B. Schröder:  Ordered Sets. An Introduction with Connections from Combinatorics to Topology. Birkhäuser (2016).