On the number of B-flows of a graph

On the number of B-flows of a graph Delia Garijo a, Andrew Goodall b, Jaroslav Nešetřil b a University of Seville, Seville, Spain b Charles University, Prague, Czech Republic abstract We exhibit explicit constructions of contractors for the graph parameter counting the number of B-flows of a graph, where B is a subset of a finite Abelian group closed under inverses. These constructions are of great interest because of their relevance to the family of B-flow conjectures formulated by Tutte, Fulkerson, Jaeger, and others. 1. Introduction This paper is a sequel to our previous article [4], where we answer a question raised by Lovász and B. Szegedy in [9] asking for a simple explicit construction for a contractor for the number of B-flows, where Bis a subset of a finite Abelian group Γclosed under inverses. Here we present some applications of our result for choices of Abelian group Γand subset Bthat are of interest because of their relevance to long-standing open problems in graph theory. Contractors for graph parameters were introduced by Lovász and B. Szegedy in [9] as a generalization of the deletion–contraction identity for the Tutte polynomial and, in particular, for the chromatic polynomial and flow polynomial. Contractors were defined in the context of graph algebras, introduced by Freedman, Lovász and Schrijver in [3] to study homomorphism functions. Using the notion of a contractor, Lovász and B. Szegedy give a new characterization of those graph parameters that can be realized as the number of homomorphisms to an edge-weighted graph (also known as a partition function). Our main result in [4] uses the duality between flows and tensions in the context of finite Fourier analysis to provide a new and constructive proof for the existence of a contractor for the graph parameter counting the number of B-flows of a graph. This contractor is a linear combination of digons (forming a ‘‘quantum digon’’). Dually, a contractor for the graph parameter counting the number of B-tensions of a graph is a linear combination of paths (forming a ‘‘quantum path’’). E-mail addresses: [email protected] (D. Garijo), [email protected] (A. Goodall), [email protected] (J. Nešetřil). Our proof in [4] is based on the following ideas that will also be of relevance here. First, the number of B-tensions of a graph can be written in terms of homomorphisms to an edge-weighted Cayley graph Hon vertex set Γ. Second, using the Fourier transform on Γ, the sum of values of a function on the set of tensions of a graph is equal to the sum of values of a related function on the set of flows. This allows us to also express the number of B-flows in terms of the number of homomorphisms to an edgeweighted Cayley graph  Hon Γ, which is related to the graph Hby taking the Fourier transform of its edge weights. Finally, we apply the general characterization by Lovász and Szegedy [9] of contractors for graph parameters counting the number of homomorphisms to an edge-weighted graph to our case of the edge-weighted Cayley graph H. This yields an explicit expression for a contractor for the number of B-flows of a graph. In this paper, we present a series of concrete instances of contractors for B-flows. These are chosen on account of their relevance to such problems as the Cycle Double Cover Conjecture, Fulkerson’s Conjecture, the Petersen Flow Conjecture and related conjectures which were reformulated by Jaeger [7] as B-flow problems. Also we consider the example B= {−1,+1}in the additive group Znof integers modulo n, because in this case the number of B-flows of a graph Gwith vertex degrees belonging to {0,1,...,n−1,n+1}is equal to the number of Eulerian orientations of G. As shown in [8], the number of Eulerian orientations of a graph cannot be expressed as the number of homomorphisms to a finite edge-weighted graph H, and therefore does not have a contractor [9, Example 2.6]. The interesting question arises of whether there is a ‘‘limiting contractor’’ for Eulerian orientations by taking contractors for {−1,+1}-flows modulo nas ntends to infinity. The explicit constructions of contractors presented in this paper are contained in Section 3. We use a number of definitions and results from [4], which are introduced in Section 2. 2. Preliminaries and known results 2.1. Homomorphism functions Given two graphs G=(V(G), E(G)) and H=(V(H), E(H)), a homomorphism from Gto H, written as ψ:G→H, is a mapping ψ:V(G)→V(H)such that ψ(u)ψ(v) ∈E(H)whenever uv∈E(G). The graph parameter hom(G,H)counting the number of homomorphisms from Gto Hcan be generalized to edge-weighted graphs Has follows. Let Hbe a graph with a real weight βH(ij)associated with each edge ij ∈E(H)and let Gbe an unweighted graph. The homomorphism function hom(G,H)is defined by hom(G,H)= ψ:V(G)→V(H) uv∈E(G) βH(ψ(u), ψ(v)). Note that if we fix U⊆V(G)and define for every function φ:U→V(H)the weight homφ(G,H)= ψ:V(G)→V(H) ψ|U=φ uv∈E(G) βH(ψ(u), ψ(v)), then hom(G,H)=φ:U→V(H)homφ(G,H). 2.2. Flows and tensions Let G=(V,E)be a graph with an arbitrary fixed orientation of its edges. Denote by c(G)the number of connected components of G, and let Γbe an additive Abelian group. AΓ-flow of Gis a function g:E→Γsuch that for each vertex v∈V,  e=uv vhead of e g(e)− e=uv vtail of e g(e)=0. If B= −Bis a subset of Γthen a B-flow of Gis a Γ-flow taking values in B. In particular, when B=Γ\ {0}aB-flow is called a nowhere-zero Γ-flow of G. AΓ-tension g :E→Γarises from a vertex Γ-colouring f:V→Γof G, by setting g(e)=f(v) − f(u)for each edge ewith tail uand head v. A B-tension of Gis a Γ-tension of Gtaking values in B. Note that, to define Γ-flows and Γ-tensions all that is needed is the structure of Γas an additive Abelian group. In [4], we impose the extra ring structure on Γin order to connect flows and tensions in the context of finite Fourier analysis. Here we only present the definitions needed to state this connection. Let Γbe a finite additive Abelian group of order n. A character of Γis a (group) homomorphism χ:Γ→C×, where C×is the multiplicative group of the field of complex numbers. The set of characters of Γform a group  Γunder pointwise multiplication which is isomorphic to Γ. For each x∈Γ, let χxdenote the image of xunder a fixed isomorphism Γ→ Γ. In particular, the trivial character χ0is defined by χ0(y)=1 for all y∈Γ, and χ−x(y)=χx(y), the bar denoting complex conjugation. Denote by CΓthe vector space over Cof all functions from Γto C. This is an inner product space with Hermitian inner product defined for α, β ∈CΓby ⟨α, β⟩ =  x∈Γ α(x)β(x). For α∈CΓ, the Fourier transform α∈CΓis defined for y∈Γby α(y)= ⟨α, χy⟩ =  x∈Γ α(x)χy(−x). (1) The set {δx:x∈Γ}of indicator functions defined by δx(y)=1x=y, 0x= y, form an orthonormal basis for CΓ, with ⟨δx, δy⟩ = δx(y). We extend the indicator function notation to subsets Bof Γ, defining δB=x∈Bδx. Lemma 2.1 ([4]).Let B = −B be a subset of an additive Abelian group Γ. Let H =Cayley(Γ,B)be the graph on vertex set Γwith an edge joining vertices i and j if and only if j −i∈B, and let  H be the edge-weighted Cayley graph on vertex set Γwith edge ij having weight  δB(j−i). Then the number of B-tensions of a graph G =(V,E)is equal to |Γ|−c(G)hom(G,H)and the number of B-flows of G is equal to |Γ|−|V|hom(G, H). 2.3. Contractors A 2-labelled graph G is a finite graph (without loops but possibly having multiple edges) in which two vertices are labelled by numbers 1 and 2 (in [3] this notion is defined in general for k-labelled graphs, k≥0). Lovász and Szegedy [9] (see also [3]) restrict labels to be on distinct vertices, but we shall follow Schrijver [10] and allow a vertex to have both labels. When referring to 2-labelled graphs, we denote by Knthe 2-labelled complete graph on n≥2 vertices with labels located at two distinct vertices, and Knits complement, consisting of nisolated vertices (two of them labelled). Let K1be a single vertex carrying both labels 1 and 2. A 2-labelled quantum graph is a formal linear combination of 2-labelled graphs with coefficients in R. Let G2denote the set of 2-labelled quantum graphs and G0 2the subset of 2-labelled quantum graphs whose labelled vertices are independent. For two 2-labelled graphs Xand Y, the product XY is defined by taking the disjoint union of X and Yand then identifying vertices which share the same label [9]. The product is associative and commutative, and extends linearly to G2. The identity for this multiplication on G2is K2. Definition 2.2 ([9]).Let hbe a graph parameter. A 2-labelled quantum graph Z∈G2is a contractor for hif for all X∈G0 2we have h(XZ)=h(XK1). The graph K1when applied as a product with X(giving the graph XK1) identifies the vertices labelled 1 and 2 in X. Thus, informally, attaching a contractor Zat two non-adjacent vertices acts like identifying these vertices as far as the value of the graph parameter his concerned. Lemma 2.4 below is a fundamental tool for finding contractors for homomorphism functions. It uses the following matrix associated to every 2-labelled graph. Let Hbe an edge-weighted graph with adjacency matrix A=(β(ij)). To every X∈G2assign aV(H)×V(H)-matrix M(X)=MH(X)with (i,j)-entry equal to homφ(X,H)where φ(1)=iand φ(2)=j. For instance, M(K1)=Iwhere Iis the identity matrix and M(K2)=Jwhere Jis the all-one matrix. Lemma 2.3 ([4]).If H has adjacency matrix A then M(Pk)=Akwhere Pkdenotes the path on k edges with endpoints labelled 1and 2. Lemma 2.4 ([9]).A2-labelled quantum graph Z is a contractor for hom(·,H)if and only if M(Z)=I. Example 2.5. Suppose His a strongly regular graph with parameters (n,k, λ, µ), i.e., a k-regular simple graph on nvertices such that any two adjacent (resp. non-adjacent) vertices of Hhave exactly λ(resp. µ) common neighbours. The adjacency matrix Aof Hsatisfies A2+(µ −λ)A+(µ −k)I=µJ. In this case Lemmas 2.3 and 2.4 give the following contractor Zfor hom(·,H), (µ −k)Z=µK2−(µ −λ)P1−P2. Compare [1, Proposition 8], giving a recursive method for computing hom(G,H)when Gis series–parallel. Suppose now that the adjacency matrix Aof Hhas rows and columns indexed by an additive Abelian group Γof order nand has (i,j)-entry equal to (β(i−j)), where β∈CΓsatisfies β(−i)=β(i). Thus Ais the adjacency matrix of an edge-weighted Cayley graph on Γ. The matrix Ahas eigenvectors (χi(j))j∈Γfor each i∈Γwith corresponding eigenvalue  β(i). Define  Ato be the matrix with (i,j)- entry the Fourier transform  β(i−j). Let us call a matrix Γ-circulant if, like the matrix A, it takes the form (α(i−j)) for some function α∈CΓ. Theorem 2.6 ([4]).Suppose that H is a connected graph with adjacency matrix a Γ-circulant matrix A and let  H be the edge-weighted graph on vertex set Γwith adjacency matrix  A. Suppose further that A has eigenvector 1with eigenvalue λ1, has minimum polynomial pA(t), and that pA(t) t−λ1=q(t)=q0+ q1t+ · · · + qℓ−1tℓ−1. Then a contractor for hom(·, H)is given by Z=1 q(λ1) 0≤k≤ℓ−1 qkPk 1. In [4], we obtain an explicit construction for a contractor for the number of B-flows by applying Lemma 2.1 and Theorem 2.6 to H=Cayley(Γ,B)(for additive Abelian group Γ, and where B⊆Γ\0 satisfies −B=B). In this case, the adjacency matrix Aof Hhas (i,j)-entry δB(i−j)and eigenvalues  δB(i)for i∈Γ. The minimum polynomial pA(t)of Ahas degree ℓequal to the number of distinct values of  δB(c)for c∈Γ. The largest eigenvalue of Ais  δB(0)= |B|, belonging to the eigenvector 1, and pA(t) t− |B|=q(t)=q0+q1t+ · · · + qℓ−1tℓ−1.(2) Theorem 2.7 ([4]).Let Γbe an additive Abelian group of order n and suppose H =Cayley(Γ,B)is a connected graph with adjacency matrix A. Let  H be the edge-weighted graph on vertex set Γwith adjacency matrix A. Then, with the polynomial q(t)defined as in Eq. (2) above, (i) a contractor for the number of B-flows is given by Z=n q(|B|) 0≤k≤ℓ−1 qkPk 1; (ii) a contractor for nc(G)times the number of B-tensions of G is given by Z=1 q0q(|B|) nK2− 1≤k≤ℓ−1 qkPk. Theorem 2.8 ([4]).Let Γbe an additive Abelian group of order n and suppose H =Cayley(Γ,B)has adjacency matrix A, and that q(t)is defined as in Eq. (2) above. Suppose H has r isomorphic connected components, i.e., its adjacency matrix A is permutation-equivalent to a matrix of the form I ⊗A1for r ×r identity matrix I and some n/r×n/r matrix A1. Then, a contractor for the number of B-flows is given by Z=n rq(|B|) 0≤k≤ℓ−1 qkPk 1. 3. Explicit constructions of contractors for B-flows In this section, we apply Theorems 2.7 and 2.8 to obtain concrete instances of contractors for the graph parameter counting the number of B-flows of a graph. In order to do this we need to find the ℓ distinct eigenvalues of the adjacency matrix of Cayley(Γ,B)(the values  δB(x)for x∈Γ), discard the largest one (|B|), and then the kth elementary symmetric functions of the remaining ℓ−1 eigenvalues form the coefficients in the expression for a contractor as a linear combination of graphs Pℓ−1−k 1(two vertices joined by ℓ−1−kedges). We begin with two easy applications of Theorem 2.7: proper vertex colourings and nowhere-zero flows. 3.1. Proper vertex colourings and nowhere-zero flows When the Abelian group Γis order nand B=Γ\ {0}, the graph H=Cayley(Γ,B)is isomorphic to the complete graph Kn. The adjacency matrix of His A=J−Iand has minimum polynomial pA(t)=(t+1)(t−n+1). Then q(t)=pA(t)/(t−n+1)=1+twhich gives q(|B|)=nand q0=q1=1. It is well known that homomorphisms of a graph Gto Knare just the n-colourings of G(see [5]). By Theorem 2.7(ii), the quantum graph K2−P1is a contractor for nc(G)times the number of B-tensions of Gwhich is exactly the same as counting homomorphisms from Gto Kn. Therefore, K2−P1is a contractor for the number of proper vertex colourings (which amounts to the deletion–contraction identity for the chromatic polynomial). Theorem 2.7(i) gives the quantum graph K2+P1as a contractor for the number of nowhere-zero Γ-flows (that this is the case amounts to the deletion–contraction identity for the flow polynomial). Note that these contractors are also obtained applying Lemmas 2.1,2.3 and 2.4 since A=J−I, ˆ A=nI −Jand M(K2)=J(for proper vertex colourings only Lemmas 2.3 and 2.4 are needed). 3.2. Cycle double covers Acycle double cover of a graph Gis a family of cycles of Gsuch that every edge appears in exactly two cycles of this family. (As usual in this paper, by a cycle is meant an even subgraph.) A cycle double cover is said to be d-colourable (d≥2) if its cycles can be coloured with dcolours in such a way that not only is each edge contained in exactly two cycles but these cycles have different colours. The Cycle Double Cover Conjecture says that every bridgeless graph has a cycle double cover. This conjecture was reformulated by Jaeger in [7] in terms of B-flows as follows. Let ∆be an additive group of melements, and ∆dthe d-fold Cartesian product. The Hamming weight |x|of a given element x=(x1,...,xd)∈∆dis defined by |x| = #{i:xi= 0}. The sets Sd r= {x∈∆d: |x| = r}are called shells (of radius r). We consider m=2 (∆=F2). Let FSd r(G)denote the number of Sd r-flows of G, where Sd ris the shell of radius rin Fd 2, i.e., the set of vectors in Fd 2with exactly rnon-zero coordinates. Conjecture 3.1 (Flow Version of the Double Cover Conjecture [7]).For every bridgeless graph there exists d≥2such that FSd 2(G)= 0. Jaeger also mentions the stronger 5-colourable Cycle Double Cover Conjecture, i.e., that FS5 2(G)= 0 for every bridgeless graph G. We now proceed to exhibit contractors for the number of d-colourable cycle double covers. To do this we need to compute the values  δSd 2(x)for x∈Fd 2. In general, the values  δSd r(x)for x∈∆dare given (see e.g. [6]) by evaluations of the Krawtchouk polynomial Kr(w;d,m)of degree r, defined for 0≤r, w ≤dby Kr(w;d,m)= [zr](1+(m−1)z)d−w(1−z)w= 0≤i≤r (−1)i(m−1)r−iw id−w r−i. In particular, K0(w;d,m)=1,K1(w;d,m)=(m−1)d−mwand Kd(w;d,m)=(−1)w(m−1)d−w. The Fourier transform of the indicator function δSd rof a shell of radius ris given by  δSd r(x)=Kr(|x|; d,m). When m=2 (∆=F2), Kr(w;d,2)= 0≤i≤r (−1)iw id−w r−i. As a warm-up we begin with a simple illustration of Theorem 2.8, which includes the case of 2-colourable cycle double covers on setting d=2. The set Sd d⊆Fd 2consists of just a single element, namely the all-one vector of Hamming weight d. The graph H=Cayley(Fd 2,Sd d)comprises 2d−1copies of K2. Here  δSd d(x)=Kd(|x|; d,2)=(−1)|x|, from which we find q(t)=t+1, and a contractor for the number of Sd d-flows is given by Theorem 2.8 as Z=2d 2d−1q(1)P1 1+P0 1=P1+K2. This, as it should be, is also a contractor for the number of nowhere-zero F2-flows. 3.2.1. 3-colourable cycle double covers Let S3 2⊆F3 2. Then H=Cayley(F3 2,S3 2)consists of 2 connected components isomorphic to K4(hence there are S3 2-tensions of Gif and only if there are F4-tensions of G). The adjacency matrix of Hhas eigenvalues δS3 2(x)∈ {3,−1}, giving q(t)=t+1. Thus, Theorem 2.8 gives the following contractor for the number of S3 2-flows, Z=8 2·q(3)[P1 1+P0 1] = P1+K2. Again, this is as it should be as S3 2-flows are in one-to-one correspondence with nowhere-zero F4-flows (truncate the elements of S3 2⊆F3 2in the last position; conversely, to a nowhere-zero F2 2-flow add a parity check digit to make a S3 2-flow). 3.2.2. 4-colourable cycle double covers Let S4 2⊆F4 2. Then H=Cayley(F4 2,S4 2)consists of 2 isomorphic connected components, each a regular graph of degree 4 2=6 on 8 vertices (i.e., K8minus a perfect matching). The adjacency matrix of Hhas eigenvalues  δS4 2(x)∈ {6,0,−2}, giving q(t)=t(t+2). Then, by Theorem 2.8, a contractor for the number of S4 2-flows is given by Z=16 2·q(6)[P2 1+2P1 1] = 1 6[C2+2P1]. 3.2.3. d-colourable cycle double covers We now consider the general case of d-colourable cycle double covers. In this case we have  δSd 2(x)=K2(|x|; d,2) =d− |x| 2− |x|(d− |x|)+|x| 2 =d 2+2|x|(|x| − d). The adjacency matrix Aof the Cayley graph H=Cayley(Fd 2,Sd 2)has ⌈d+1 2⌉distinct eigenvalues, namely d 2+2w(w −d)for 0 ≤w≤ ⌊ d 2⌋. The largest eigenvalue d 2= |Sd 2|belongs to the eigenvector 1. In the notation of Theorem 2.8, q(t)= 1≤w≤⌊d/2⌋t−d 2+2w(d−w), and qd 2=2d/2−1d!deven, 2(d−1)/2(d−1)!dodd. Since the elements of Sd 2generate precisely the even-weight vectors in Fd 2, the graph H= Cayley(Fd 2,Sd 2)has 2 connected components. This allows us to explicitly construct a contractor for FSd 2(G), as we have done for d∈ {2,3,4}and we now do for the case d=5. 3.2.4. 5-colourable cycle double covers Let Abe the adjacency matrix of Cayley(F5 2,S5 2), which has 2 connected components, eigenvalues 10,2,−2, and q(t)=(t−2)(t+2)=t2−4, i.e., q0= −4,q1=0,q2=1, and q(10)=96. We also have n=25=32 and so Theorem 2.8 gives the following contractor for FS5 2(G), Z=32 2·q(10)[P2 1−4P0 1] = 1 6C2−4K2. Thus we have FS5 2(XK1)=FS5 2(XZ)=1 6FS5 2(XC2)−4 6FS5 2(XK2)for every X∈G0 2. If we write G=XP1 and let e∈E(G)be the edge with endpoints labelled 1 and 2, then XK2=X=G\eand XK1=G/e. Suppose we write G∥efor the operation that inserts an extra edge parallel to e∈E(G). Then XC2=XP2 1=G∥e. In this notation, FS5 2(G∥e)=4FS5 2(G\e)+6FS5 2(G/e). (3) 3.3. Fulkerson flows Fulkerson’s Conjecture is that in every bridgeless cubic graph Gthere is a family of six perfect matchings such that each edge appears in exactly two of them. Jaeger [7, Theorem 6.1] shows that Fulkerson’s Conjecture is equivalent to the assertion that a bridgeless cubic graph has a S6 4-flow, where S6 4⊆F6 2comprises those vectors containing exactly four 1s. We follow [2] and call these types of flow ‘‘Fulkerson flows’’. Let Abe the adjacency matrix of H=Cayley(F6 2,S6 4), which has 2 connected components, eigenvalues 15,−5,−1,3, and q(t)=(t+5)(t+1)(t−3)=t3+3t2−13t−15, i.e., q0= −15,q1= −13,q2=3,q3=1 and q(15)=20 ·16 ·12,n=26. Hence, by Theorem 2.8 a contractor for FS6 4(G)is given by Z=64 2·q(15)[P3 1+3P2 1−13P1 1−15P0 1] = 1 120 P3 1+3C2−13P1−15K2. 3.4. Petersen flows The Petersen Flow Conjecture of Jaeger [7] states that every bridgeless graph has a Petersen flow. As explained in e.g. [2], this conjecture implies the 5-colourable cycle double conjecture and other long-standing conjectures. Petersen flows are defined as follows. Take Γ=F6 2. Let C1,...,C6be a basis of the cycle space of the Petersen graph P=(V,E)and let g1,...,g6be the corresponding indicator vectors in FE 2(where |E| = 15), which we shall regard as the rows of a matrix (gi,e)1≤i≤6,e∈E. Let B= {(g1,e,...,g6,e)T:e∈E} ⊆ F6 2. Then |B| = 15 since for every pair of distinct edges there is a cycle in the basis which contains exactly one of them. The indicator function δBhas Fourier transform  δB(a1,...,a6)= e∈E (−1)a1g1,e+···+a6g6,e =#{e:a1g1,e+ · · · + a6g6,e=0} − #{e:a1g1,e+ · · · + a6g6,e=1} = |E| − 2|C|, where Cis the cycle with indicator vector a1g1+ · · · + a6g6. Since a cycle of the Petersen graph has length 0,5,6,8 or 9, it follows that H=Cayley(F6 2,B)has eigenvalues 15, 5,3, −1 and −3. Thus q(t)=(t+1)(t2−9)(t−5)=t4−4t3−14t2+36t+45, and n=64,q(15)=34 560. Since Bcontains a set of generators for F6 2, the graph Cayley(F6 2,B)is connected. Hence Theorem 2.7 gives a contractor Zfor the number of B-flows, Z=64 34 560 P4 1−4P3 1−14P2 1+36P1+45K2, the fraction simplifying to 1 540 . This construction of a contractor for Petersen flows extends more generally to B-flows when Bis defined in a similar way via a basis for the cycle space of a graph Q=(V,E). Suppose that Qis a graph of nullity k= |E|−|V| + c(Q), having cycle space basis vectors g1,...,gk∈FE 2, rows of the matrix (gi,e)1≤i≤k,e∈E. Let B= {(g1,e,...,gk,e)T:e∈E} ⊆ Fk 2, i.e., B is the set of columns of the matrix (gi,e). Claim. If Q is edge-3-connected then the vectors (g1,e,...,gk,e), e∈E, are distinct, so that |B|=|E|. Proof of Claim. Suppose e,f∈E(Q)are such that (g1,e,...,gk,e)=(g1,f,...,gk,f). Suppose that Q−e−fis connected and let e=uv. Then there is a path joining uand vin Q−e−f, which together with the edge eforms a cycle in Qnot containing f, contrary to hypothesis. Therefore Q−e−fmust be disconnected, yet this contradicts the fact that Qis edge 3-connected. Hence (g1,e,...,gk,e)= (g1,f,...,gk,f)when e= f. By a calculation similar to that carried out above for the Petersen graph, when Qis edge-3- connected the eigenvalues of Cayley(Fk 2,B)are equal to |E| − 2|C|for cycles Cof Q. Since the row rank of the matrix (gi,e)is equal to k, the column rank of (gi,e)is equal to k. Therefore Cayley(Fk 2,B)has just 1 component, the set Bspanning Fk 2. If 0 <c1<· · · <crare the sizes of cycles in Q, we have q(t)= 1≤j≤r (t− |E| + 2cj), and q(|B|)=2r1≤j≤rcj. By Theorem 2.7, a contractor for the number of B-flows is given by Z=2k−r c1c2· · · cr 0≤j≤r qjPj 1, where qr−i=(−1)i S⊆{1,...,r} |S|=i s∈S (|E| − 2cs). Table 1 Contractors for the number of nowhere-zero n,1-flows for n ≤ 9. n q(t)Contractor for nowhere-zero n,1-flows 3 1 +t K2+P1 4 2t+t2P1+1 2P2 1 5−1+t+t2−K2+P1+P2 1 6−2−t+2t2+t3−K2−1 2P1+P2 1+1 2P3 1 7−1−2t+t2+t3−K2−2P1+P2 1+P3 1 8−4t−2t2+2t3+t4−2P1−P2 1+P3 1+1 2P4 1 9 1 −2t−3t2+t3+t4K2−2P1−3P2 1+P3 1+P4 1 3.5. Nowhere-zero n,1-flows We finish our selection of explicit constructions of contractors with a sequence of graph parameters whose limit is the graph parameter counting Eulerian orientations. The number of Eulerian orientations is mentioned by Lovász and Szegedy [8] as an example of a graph parameter not expressible as the number of homomorphisms to a finite edge-weighted graph but which is expressible via graph limits as a homomorphism into a measurable function on the unit square (what might be called a ‘‘graphon parameter’’). Let us take Γ=Zn, the integers modulo n, and B= {−1,+1}. The set of B-flows of a graph Gis in one–one correspondence with the set of orientations of Gin which at each vertex the indegree is congruent to the outdegree modulo n(also known as a nowhere-zero n,1-flow). When n=3,B-flows are nowhere-zero Z3-flows and as we have seen earlier a contractor is given by K2+P1. In case Gis a 4-regular graph, B-flows of Gcorrespond to Eulerian orientations of G. More generally, for arbitrary n,B-flows of a graph Gall of whose vertex degrees belong to {0,1,2,...,n−1,n+1}correspond to Eulerian orientations of G. The indicator function of Bhas Fourier transform  δB(a)=ζa+ζ−a, where ζ=e2πi/n. When n=4 these eigenvalues are 2,0,−1 and we find that q(t)=t(t+2). By Theorem 2.7,1 2P2 1+P1is a contractor for the number of B-flows modulo 4. When n=5 we have q(t)=(t−ζ−ζ−1)(t−ζ2−ζ−2)=t2+t−1, and Theorem 2.7 implies that P2+P1−K2is a contractor for the number of B-flows modulo 5. After similar calculations we obtain contractors for the number of nowhere-zero n,1-flows for n≤9, as displayed in Table 1. Generally, for B-flows modulo nwe have q(t)= a∈{1,...,⌊n/2⌋} (t−ζa−ζ−a). When nis odd, q(2)= a∈1,..., n−1 2(1−ζa)(1−ζ−a)= a∈{1,...,n−1} (1−ζa)=n, and when nis even q(2)=2n. Since  a∈{1,...,n−1} (t−ζa)=tn−1+ · · · + t+1, we have  A⊆{1,...,n−1} |A|=k ζa∈Aa=(−1)k.(4) What we would like is a similar closed-form expression for the coefficients of q(t). This will yield an explicit expression for a contractor for the number of nowhere-zero n,1-flows.