Polynomials and graph homomorphisms

22 Polynomials and graph homomorphisms Delia Garijo •Andrew Goodall •Jaroslav Neˇsetˇril •Guus Regts Synopsis We develop in the language of graph homomorphisms the connection between the Tutte polynomial and the state models of statistical physics. •The Tutte polynomial and homomorphism numbers. •Spin models and edge coloring models. •Connection matrices and the characterization of graph invariants arising from spin models. •Homomorphism numbers and invariants of the cycle matroid of a graph. •Graph homomorphism numbers as evaluations of graph polynomials. •Other graph polynomials from counting graph homomorphisms such as the independence polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial. 22.1 Introduction Hyperbolas of the form (x−1)(y−1) = qplay a special role in the theory of the Tutte polynomial, especially when qis an integer. For a positive integer q, the Tutte polynomial T(G;x, y) of a graph Galong the hyperbola (x−1)(y−1) = q is equivalent to the partition function of the q-state Potts model on Gsee Chapter 20). We consider more general state models in the setting of graph homomorphisms, namely in the form of homomorphisms from a graph Gto a specified weighted graph Hon qvertices. We situate the Tutte polynomial 405 406 Handbook of the Tutte polynomial and related topics among other polynomial graph invariants derived from such “H-colorings”, such as the independence polynomial and polynomials recently introduced by I. Averbouch et al. [55], and by P. Tittmann et al. [1070]. Agraph homomorphism profile of a graph Gcollects together as a single invariant of Gthe number of the H-colorings of Gfor a family of weighted graphs H. Graph homomorphism profiles play an important role in the recently developed theory of graph limits (see [796]). When restricted to certain families of graphs, such as complete graphs, graph homomorphism profiles may coincide with known polynomial graph invariants, such as the chromatic polynomial. This allows a unifying formulation of seemingly diverse questions such as whether a graph is chromatically unique, Tutte unique or spectrally unique. (See Chapter 6 and Chapter 11 for the topics of graphs uniquely determined, respectively, by their Tutte polynomial and by their chromatic polynomial.) Recently finite model theory has been used for a general construction of polynomial graph invariants from graph homomorphism profiles [561]. The number of H-colorings of a graph Gmay be equivalently formulated as the partition function of a spin model and we sketch the analogous theory for edge coloring models. Graph invariants sharing with the Tutte polynomial the property of being expressible as the partition function of a spin model can be elegantly characterized by means of connection matrices [502, 991]. The ubiquity of the Tutte polynomial in combinatorics is in large part due to it being not only a graph invariant but also an invariant of the graph’s underlying cycle matroid, allowing it to be defined for matroids more generally. Graph invariants obtained from homomorphism numbers that share this property of being a matroid invariant have been characterized [562]. Although polynomial graph invariants different from the Tutte polynomial are known that share the property of being a cycle matroid invariant, it is not yet known how they might be defined on more general classes of matroid than graphic matroids [367, 562]. Another important property of the Tutte polynomial of a graph Gis that it satisfies a deletion–contraction recurrence, in which the terms of the recurrence involve smaller graphs than G. We give some examples of other polynomial graph invariants obtained from graph homomorphism profiles which have similar size-reducing recurrences. However, a general method of constructing by graph homomorphism profiles a polynomial graph invariant with a sizereducing recurrence formula is not known. Homomorphisms are closely related to universal algebra and category theory. Likewise, the theory of invariants and abstract algebra provide a proper setting for many questions related to the Tutte polynomial. We do not pursue these connections here but instead refer to [308, 606, 716, 740, 796]. Polynomials and graph homomorphisms 407 22.2 Homomorphism profiles Definition 22.1. Ahomomorphism from a simple graph Gto a simple graph His a mapping f:V(G)→V(H) such that f(u)f(v)∈E(H) whenever uv ∈E(G). The Hom complex Hom(G, H) is the set of homomorphisms from Gto H. The number of homomorphisms from Gto His denoted by hom(G, H). Homomorphisms are adjacency-preserving mappings but no other condition is imposed: f(u)f(v)∈E(H) need not imply uv ∈E(G), and fneed not be one-to-one. Example 22.2. Every homomorphism from a graph Gto the complete graph Kqcorresponds to a proper vertex q-coloring of G. Thus, hom(G, Kq) is the chromatic polynomial χ(G;x) of Gevaluated at q. (See Chapter 11 for the chromatic polynomial.) When Gand Hare multigraphs (graphs which may have loops or multiple edges), a homomorphism ffrom Gto H, denoted f:G→H, is a pair f= (fV, fE) of functions fV:V(G)→V(H) and fE:E(G)→E(H) with the property that if e∈E(G) has endpoints uand vthen fE(e) has endpoints fV(u) and fV(v). Thus, the function fEmaps parallel edges in Gto parallel edges (possibly the same edge) in H, and loops in Gto loops in H. The notation hom(G, H) extends from simple graphs to multigraphs Gand H, defined as the number of homomorphisms from Gto H. The two definitions of homomorphisms (and thus of hom(G, H)) are equivalent when Gand H are simple loopless graphs. The parameter hom(G, H) can be further extended to weighted multigraphs H, in which weights on vertices and edges of Hbelong to a commutative ring (usually a field such as R). Definition 22.3. Let Hbe a multigraph with a weight α(u) associated with each vertex u∈V(H) and a weight β(e) associated with each edge e∈E(H). The parameter hom(G, H) defined on multigraphs Gis defined by hom(G, H) = X f:G→H homomorphism Y v∈V(G) α(fV(v)) Y e∈E(G) β(fE(e)),(22.1) where the sum is over all homomorphisms f= (fV, fE) from Gto H. If fis a homomorphism mapping a given edge eof Gto an edge e0of H, then so is the mapping that is equal to fwith the sole exception that it maps eto an edge parallel to e0. Consequently, in Definition 22.3 the value of hom(G, H) is unchanged when parallel edges e1, e2, . . . , e`in Hof weights β(e1), β(e2),··· , β(e`) are replaced by a single edge of weight β(e1) + β(e2) + 408 Handbook of the Tutte polynomial and related topics ··· +β(e`). Thus in studying parameters of the form hom(G, H) it suffices to consider Hto be a simple graph possibly with a loop on some vertices. Furthermore, as an edge of weight 0 in Hplays the same role as a non-edge, we can take Hto be a complete graph with a loop on each vertex. In this case the sum in Equation (22.1) need not be restricted to homomorphisms and we have, for Ga multigraph and Ha complete graph with a single loop on each vertex, hom(G, H) = X f:V(G)→V(H)Y v∈V(G) α(f(v)) Y uv∈E(G) β(f(u)f(v)).(22.2) Here, edges of Gare taken with their multiplicity in the product (parallel edges in Gare sent to the same edge in H). When in Hall the vertex weights are 1 and the edge weights are nonnegative integers, Equation (22.2) gives a definition of hom(G, H) equivalent to that given previously for unweighted multigraphs Gand H(as the number of homomorphisms from Gto H) by taking the edge weights of Hto represent edge multiplicities. Equation (22.2) is therefore often taken as the starting definition of hom(G, H). In statistical physics, the quantity hom(G, H) is known as the partition function of a spin model on G. Here the vertices of Hare states of the model, with vertex weight the probability of the state, and edges joining states have weight equal to the interaction energy between the two states, see [368]. (In combinatorics spin models are sometimes called vertex coloring models, for example [502], but we shall use the term spin model, in particular since what are termed edge coloring models in the next section are known as vertex models in statistical physics.) Graph invariants defined by the partition function of a spin model include many graph polynomial invariants such as the Tutte polynomial. In order to make this statement precise we specify how invariants may be compared (so that one invariant may “include” or “specialize to” another). Agraph invariant is a function on graphs invariant under isomorphism. A graph invariant fdefines a partition on graphs in which Gand G0are equivalent when f(G) = f(G0), in which case we write G∼fG0. The partition of graphs by fis a coarsening of the partition of graphs by isomorphism. A graph invariant determines Gup to isomorphism precisely when the equivalence class containing Gunder fis the isomorphism class of G, that is, G∼fG0implies G∼ =G0. The graph Gis then said to be f-unique. The subject of Chapter 6 is Tutte uniqueness, that is, the question of which graphs are uniquely determined up to isomorphism by their Tutte polynomials. A graph invariant gis said to be an f-invariant when G∼fG0implies G∼gG0for all graphs G, G0. For example, the rank r(G) of Gis a Tutte polynomial invariant (since r(G) is the degree of T(G;x, y) as a polynomial in x). If gis an f-invariant and fis a g-invariant then fand ghave the same distinguishing power as each other, and in this case we say that fis equivalent to g(as graph invariants) and write f≃g. The comparative study of graph Polynomials and graph homomorphisms 409 invariants may be viewed as the study of the partial order on graph invariants defined by the relation “gis an f-invariant” (see Chapter 9). Definition 22.4. Let Gbe a family of graphs and Ha family of edge-C-weighted graphs. The right H-profile of G∈ G is the vector (hom(G, H) : H∈ H). The left G-profile of H∈ H is the vector (hom(G, H) : G∈ G). When His a countable family of edge-weighted graphs enumerated as a multisequence (for a d-dimensional sequence the terms are indexed by Nd), the profile of Gby the (q1, . . . , qd)-th term of Hdefines a function g(G;q1, . . . , qd). For example, when His the family of complete graphs written as the sequence (Kq:q∈N), the right profile of Gis the sequence of evaluations of the chromatic polynomial of Gat nonnegative integers, (χ(G;q) : q∈N). When Gis the family of all simple graphs the left G-profile of a graph H is also known as the Lov´asz vector of H, due to its role in the dramatically simple proof of the cancellation law for the product of relational structures (such as graphs) [790, 791]. The Lov´asz vector of Hdetermines Hup to isomorphism [790]. For a given graph invariant f, it is not clear whether there is a family of graphs Hsuch that f(G) = f(G0) if and only if Gand G0have the same right H-profile. (A similar question can be asked for left profiles.) We have just seen that for the trivial graph invariant fdefined by f(G) = f(G0) if and only if G∼ =G0we can take Gto be all simple graphs and the left G-profile is equivalent to f. (L. Lov´asz subsequently showed [794] that when Gis the set of all simple graphs the right G-profile is equivalent to fas well.) The graph parameter |V(G)|is equivalent to the left {K1}-profile, as hom(K1, G) = |V(G)|and is equivalent, for example, to the right {K2}-profile as hom(G, K2) = 2|V(G)|. When fis a graph polynomial whose evaluations at positive integers q count homomorphisms to graphs in a sequence H= (Hq:q∈N) we can by interpolation determine the polynomial ffrom the right H-profile. Therefore the right H-profile in such a case is equivalent to the polynomial invariant f, as illustrated in the following example. Example 22.5. If H={Kq:q∈N}then Gand G0have the same right H-profile if and only if Gand G0are chromatically equivalent (i.e., have the same chromatic polynomial; see Chapter 11). If G={K1}∪{Cq:q∈N}then the left G-profiles of Hand H0are the same if and only if Hand H0are cospectral (i.e., have the same characteristic polynomial) [511]. Definition 22.6. Aq-state Potts model graph, denoted by Kx,y q, is an edgeweighted graph on qvertices in which each pair of distinct vertices are joined by an edge of the same weight xand each vertex has a loop attached of weight y. (Figure 22.1 shows the 4-state Potts model graph Kx,y 4.) 410 Handbook of the Tutte polynomial and related topics xxx x x x yy y y FIGURE 22.1: The 4-state Potts model graph Kx,y 4. In the notation of Definition 22.6, Kq∼ =K1,0 q. The following result was shown in [511]. Theorem 22.7. The right {K1,y q:q≥1, y ∈N}-profile of Gis equivalent as a graph invariant to the Tutte polynomial of G, with hom(G, K1,y q) = qk(G)(y−1)r(G)TG;q−1+y y−1, y. In particular, a graph Gis Tutte-unique if and only if Gis determined by its right {K1,y q:q≥1, y ∈N}-profile. Whether a graph is determined by its right {K1,y q:q∈N}-profile includes the question of chromatic uniqueness by setting y= 0, and flow uniqueness by taking y= 1 −q. On the other hand, the case where yis variable and qfixed gives a right profile determining Z(G;q, y −1) as a polynomial in y, that is, the q-state Potts partition function of G. This leads to the notion of q-state Potts uniqueness [511], for which see Section 6.5.3. 22.3 Edge coloring models Roughly speaking, by interchanging the roles of edges and vertices in (22.2), one obtains the partition function of an edge coloring model. Edge coloring models also originate from statistical physics models, where they are called vertex models, and were introduced to the graph theory community by P. de la Harpe and V. Jones [368]. They form a special case of Holants (see Chapter 21) and they can also be seen as contractions of tensor networks, which originated in the work of R. Penrose [917] and have found applications in areas such as knot theory [683], the theory of Vassiliev invariants [308], quantum computing [818], and even the theory of neural networks [912]. Definition 22.8. Let q∈N. A q-color edge coloring model his a map h:Nq→C. The partition function of his defined as the graph parameter that maps a graph G= (V, E) to the number ph(G) := X φ:E→[q]Y v∈V h(φ(δ(v))),(22.3) Polynomials and graph homomorphisms 411 where δ(v) is the multiset of edges incident with vand we identify the multiset of colors φ(δ(v)) with its incidence vector in Nq. The field Cin this definition can be replaced by an arbitrary commutative ring. Example 22.9. Let q= 2 and let h:N2→Cbe defined for x= (x1, x2)∈N2 by h(x) = 1 if x1≤1 and 0 otherwise. Then ph(G) is equal to the number of matchings of G. Indeed, for every assignment of colors to the edges that gives a nonzero contribution to the sum in (22.3), the edges that receive color 1 together form a matching. Denoting the line graph of a graph Gby L(G), it is not difficult to see that for a fixed graph Hthe parameter G7→ hom(L(G), L(H)) can be expressed as the partition function of an edge coloring model [368]. More surprisingly, it is also possible to express G7→ hom(G, H) as the partition function of an edge coloring model for any weighted graph H, as shown by B. Szegedy [1053]. In particular, taking the q-state Potts model graph H=Kx,y q, the Tutte polynomial along the hyperbola (x−1)(y−1) = qcan be written as the partition function of an edge coloring model, as we now describe. Example 22.10. Let us fix q∈Nand define an edge coloring model h:Nq+1 →Cby for a= (a1, . . . , aq+1)∈Nq+1, h(a) = ((y−x)ai/2·xaq+1/2if aj= 0 for each j /∈ {i, q + 1}, qxaq+1/2otherwise. Then one can verify that for any graph G,ph(G) = hom(G, Kx,y q). Alternatively, this follows from Lemma 22.11 below. The construction of Szegedy, given below, shows that one can in fact find an edge coloring model h0:Nq→Csuch that ph0(G) = hom(G, Kx,y q) for all graphs G. Note that if for example y= 0 and x= 1, in which case hom(G, K1,0 q) is the number of proper q-colorings of G, the edge coloring model his not real-valued. There are in fact no real-valued edge coloring models hfor which ph(G) = hom(G, K1,0 q) for all graphs Gwhen q≥3, as is shown in [956]. We now describe Szegedy’s construction in general. Let Hbe an n-vertex weighted graph with vertex weights given by α∈Cnand edge weights given by a symmetric matrix β∈Cn×n. As βis symmetric we can write β=UTU for some q×n(complex) matrix Ufor some q. (One can take q= rk(β) unless βis the all-zero matrix, see [563, Lemma 5.2.4]; when βis real this follows for example from the spectral theorem.) Let u1, . . . , un∈Cqbe the columns of U. Define the edge coloring model h=hα,β for a∈Nqby h(a) := n X i=1 αi q Y j=1 ui(j)aj,(22.4) where αiis the i-th entry of αand ui(j) is the j-th entry of the column 412 Handbook of the Tutte polynomial and related topics vector ui. In Example 22.10 we have qvectors u1, . . . , uq∈Cq+1, where for i= 1, . . . , q the top q-part of uiis equal to √y−xtimes the i-th unit vector and where ui(q+ 1) is equal to √x. With this, we have the following from [1053]. Lemma 22.11. Let Hbe an n-vertex weighted graph with vertex weights given by α∈Cnand edge weights given by a symmetric matrix β∈Cn×n, and let hbe the edge coloring model in (22.4). Then hom(G, H) = ph(G)for every graph G. The weighted graphs Hfor which the corresponding edge coloring model hcan be taken to be real-valued are characterized in [956]. For example, if the matrix βis real and positive semidefinite, and the vector αis real, then obviously hcan be taken to be real-valued. The complex orthogonal group, Oq, is the group of q×qcomplex-valued matrices Asuch that ATAis equal to the identity matrix. There is a natural action of Oqon edge coloring models that leaves the partition function invariant. We give an example before embarking on the general case. For A∈Oq, let hAbe the edge coloring model as defined in (22.4) with each uireplaced by Aui. Then, as (AU)TAU =β, Lemma 22.11 implies that for any graph G we have ph(G) = phA(G). In the general case, we can view any edge coloring model has a linear map C[x1, . . . , xq]→Cby identifying the monomials in C[x1, . . . , xq] with their coefficient vectors in Nq. As Oqhas a natural action on this polynomial ring, it also acts naturally on edge coloring models. Thus, for any A∈Oq and h:Nq→Cwe can associate another edge coloring model hAand just as above we have that ph(G) = phA(G) for all graphs G. A proof of this fact can be found in for example [419, 1053]. This orthogonal group invariance can lead to interesting representations of certain counting problems, as in Chapter 21. Partition functions of edge coloring models may also be defined for directed graphs [419], in which case they are invariant under an action of the general linear group. See [957] for partition functions related to invariant theory of the symplectic group. 22.4 Connection matrices For a positive integer `, an `-labeled graph is a graph Gtogether with an injective map λ: [`]→V(G); a 0-labelled graph is unlabelled. Two `-labeled graphs are isomorphic if there is a label-preserving isomorphism between them. Definition 22.12. The gluing product G1t`G2of two `-labeled graphs G1 and G2is the `-labeled graph obtained by taking the disjoint union of G1and G2and then identifying vertices with the same label. The product G1t0G2 is disjoint union. Polynomials and graph homomorphisms 413 Let fbe a graph invariant, which we extend to `-labeled graphs by forgetting the labels. Definition 22.13. For nonnegative integer `, the `-th connection matrix of f, denoted by M(f, `), has rows and columns indexed by `-labeled graphs. The entry of M(f, `) in the intersection of the row corresponding to G1and the column corresponding to G2is f(G1t`G2). A graph invariant fis multiplicative (over disjoint unions) if f(G1tG2) = f(G1)f(G2) for all graphs G1, G2and f(∅) = 1, where ∅denotes the empty graph (no vertices or edges). The graph invariant defined by G7→ hom(G, H) for a fixed weighted graph His multiplicative. The following result is a variation on [502, Proposition 2.1]. Proposition 22.14. Let fbe a graph invariant not identically zero. Then f is multiplicative if and only if f(∅)=1and M(f, 0) is of rank 1. M. Freedman et al. [502] proved that the connection matrices M(f, `) when f(G) = hom(G, H) for a fixed graph Hhave special properties, and in fact give the following characterization. Theorem 22.15. Let fbe a real-valued graph invariant defined on loopless graphs. Then there is a finite weighted graph Hwith real edge weights and positive real vertex weights such that f(G)is equal to hom(G, H)for all Gif and only if for each `∈Nthe connection matrix M(f, `)is positive semidefinite and there exists q > 0such that rk(M(f, `)) ≤q`for each `∈N. T. Kotek and J. Makowsky [712, Theorem 9] give a characterization in terms of monadic second order logic for polynomial graph invariants fall of whose evaluations have connection matrices of finite rank. In [502, 795, 796] explicit formulas for the rank of connection matrices of various graph invariants are given, from which we highlight the following (from [502, 796]): Example 22.16. Let fbe the graph invariant defined by f(G) = T(G;x, y) for a fixed point (x, y) on the hyperbola (x−1)(y−1) = q, and let `∈N. Then rk(M(f, `)) = (Pq i=1 ` iq∈N, B`otherwise, where ` iis the number of partitions of [`] into isubsets and B`=P` i=1 ` i. Thus the rank is the exponentially bounded number of partitions of [`] into at most qsubsets when q∈N, and is equal to the superexponential Bell number B`when q6∈ N. Example 22.16 includes as a special case f(G) = χ(G;q), the evaluation of the chromatic polynomial at q. 420 Handbook of the Tutte polynomial and related topics Kx KxKxKx Kx FIGURE 22.2: The graph Hx,5. The loop on each Kxindicates that there is a loop on each of its xvertices (making the graph K1,1 x). Graph polynomial Graph sequence chromatic Kq flow K1,1−q q Tutte K1,` q independence K1,1 1+Kq Averbouch–Godlin–Makowsky K1,1 q−`+Km,1 ` Tittmann–Averbouch–Makowsky K1,1 1+Kq[K`] TABLE 22.1: Table of graph sequences (Hq) for which hom(G, Hq) = p(G;q) for a polynomial p(G) satisfying a size-reducing recurrence formula. (Some are double or triple sequences indexed by q, ` and m.) Tittmann et al. in [1070], where the above recurrence formula was also shown, proved that the polynomial Q(G;x, y) is universal with respect to its defining recurrence relation. Further they showed that the subgraph component polynomial Q(G;x, y) for x∈Rand y∈Ncan be viewed as a partition function by counting homomorphisms to a vertexand edge-weighted graph, relating it thereby to the Widom–Rowlinson model of statistical physics [1165] (see also, for example, [432]). Let Hx,y with x, y ∈Nbe the graph K1,1 1+Ky[K1,1 x], comprising the star K1,y with a loop on its central vertex and each leaf replaced by a copy of K1,1 x, each completely joined to the central vertex (see Figure 22.2). Then it is not difficult to see [1070] that hom(G, Hx,y) = Q(G;x, y), and a converse result holds [511]: Theorem 22.31. Let Hbe an edge-C-weighted graph and x, y ∈C. Then hom(G, H) = Q(G;x, y)for all G∈ {Kn,0 1, K0,n 2, K1,n, Cn:n∈N}if and only if x, y ∈Nand H∼ =Hx,y. In Table 22.1 we summarize the graph polynomials with size-reducing recurrence formulas that are determined by counting homomorphisms to graphs; Polynomials and graph homomorphisms 421 for example, the fourth line means that the independence polynomial of Gis determined by the homomorphism profiles of the graphs K1,1 1+Kq, as witnessed by the equation hom(G, K1,1 1+Kq) = I(G;q). Some other graph polynomials that have a size-reducing recurrence formula and that are missing from Table 22.1 include the interlace polynomial [48] and the domination polynomial [46]. However, we do not know if either of these polynomials is equivalent to the right homomorphism profile by some sequence (Hq). In [512] a broad family of graph sequences is produced using the encoding of graphs by rooted tree models (an example of a rooted tree model for graphs is the cotree encoding of cographs). This family of graph sequences produces by graph homomorphism profiles all the graph polynomials described in this section (see [512, Figure 5] for cotree representations of the graphs in Table 22.1 above). This family of graph sequences made by using rooted tree models is in turn a special case of the general finite model theory construction of [561] described briefly in Section 22.6 above. 22.8 Open problems Theorem 22.18 characterizes graph invariants obtained from homomorphism numbers that depend on the underlying cycle matroid alone; such graph invariants may be extended to a wider class of matroids in a similar way to the Tutte polynomial, and are therefore of great potential interest. Such invariants include G7→ |A|−k(G)hom(G, Γ(A, B)), defined by homomorphisms to a Cayley graph on an abelian group A. As explained in Example 22.19, the graph invariant in this case can be interpreted in terms of the cycle matroid alone via tensions. In other cases it seems challenging to discover such a formulation [367]: Problem 22.32. For Ha generalized Johnson graph or Grassmann graph, give an interpretation to the parameter G7→ |V(H)|−k(G)hom(G, H) in terms of the cycle matroid of Galone. In Problem 22.32, it may be that some additional structure on the cycle matroid of Gis needed (like the orientation of edges that is required for defining tensions and flows). This additional structure must be defined with reference to the cycle matroid alone and the value of the graph invariant should ultimately not depend on this additional structure (as for tensions and flows, where the choice of orientation does not matter). For orientable matroids with more than one orientation class, the number of nowhere-zero tensions or flows 422 Handbook of the Tutte polynomial and related topics is not properly a matroid invariant but an invariant of the oriented matroid with specified orientation class [544]. The next problem (formulated in [561, Problem 8.1]) is perhaps the main open problem related to polynomials defined by homomorphism numbers. See the end of Section 22.6 for a discussion of graph interpretations. Problem 22.33. Suppose (Hq) is a sequence of simple graphs with the property that for each graph Gthere is a polynomial p(G) such that hom(G, Hq) = p(G;q) for all q∈N. Can (Hq) be obtained from disjoint unions of transitive tournaments plus unary relations by a quantifier-free interpretation scheme? Roughly speaking, the interpretation scheme mentioned in Problem 22.33 converts a relational structure Σ (such as a disjoint union of transitive tournaments with further unary relations) to a graph Hby taking vertices of H to be tuples of elements in the domain of Σ and using the relations of Σ to define the edges of H; that it is a quantifier-free interpretation scheme means that edges of Hare defined only by a quantifier-free formula in the language of Σ. The chromatic polynomial, Tutte polynomial, independence polynomial and other polynomials that we have seen to be determined by right homomorphism profiles are all definable by subgraph expansions in which the range of summation is defined by a predicate expressible in the language of graphs using monadic second-order logic (MSOL). See for example [712] for MSOLdefinable graph polynomials. While the interlace polynomial of a graph [48] is MSOL-definable [712], it is not known whether it can be determined by right homomorphism profiles in this way. This prompts the following question: Problem 22.34. Is every MSOL-definable univariate graph polynomial equivalent to some right (Hq)-profile for some sequence of graphs (Hq)? From Example 22.5, the left profile by cycles (plus K1) is equivalent to the characteristic polynomial; Problem 22.34 includes the question whether the characteristic polynomial is equivalent to some right profile as well. Finally, the deletion–contraction relation for the Tutte polynomial is an example of a size-reducing recurrence formula: the Tutte polynomial of a graph Gis expressed in terms of smaller graphs obtained by modifying Glocally (remove an edge, contract an edge). We have also seen that the Tutte polynomial of a graph Gis determined by the right profile of Gby the sequence of q-state Potts model graphs (K1,` q)q,`∈N. In Section 22.7 we give some other examples of graph polynomials determined in a similar way by right profiles and which have a size-reducing recurrence formula. However, a general construction is lacking: Problem 22.35. For which weighted graph sequences (Hq) defining a graph polynomial p(G;q) = hom(G, Hq) is there a size-reducing recurrence formula, that is, a recurrence formula for p(G) expressing it in terms of its values on a finite number of graphs smaller than G?