WEB WORLDS, WEB-COLOURING MATRICES, AND WEB-MIXING MATRICES MARK DUKES, EINAN GARDI, EINAR STEINGR´IMSSON, AND CHRIS D. WHITE Abstract. We introduce a new combinatorial object called a web world that consists of a set of web diagrams. The diagrams of a web world are generalizations of graphs, and each is built on the 3 same underlying graph. Instead of ordinary vertices the diagrams have pegs, and edges incident 1 to a peg have different heights on the peg. The web world of a web diagram is the set of all web 0 diagrams that result from permuting the order in which endpoints of edges appear on a peg. The 2 motivation comes from particle physics, where web diagrams arise as particular types of Feynman n diagrams describing scattering amplitudes in non-Abelian gauge (Yang-Mills) theories. To each a web world we associate two matrices called the web-colouring matrix and web-mixing matrix. The J entriesofthesematricesareindexedbyorderedpairsofwebdiagrams(D1,D2),andarecomputed 8 fromthosecolouringsoftheedgesofD thatyieldD underatransformationdeterminedbyeach 2 1 2 colouring. We show that colourings of a web diagram (whose constituent indecomposable diagrams are all ] O unique) that lead to a reconstruction of the diagram are equivalent to order-preserving mappings ofcertainpartiallyorderedsets(posets)thatmaybeconstructedfromthewebdiagrams. Forweb C worlds whose web graphs have all edge labels equal to 1, the diagonal entries of web-mixing and . h web-colouring matrices are obtained by summing certain polynomials determined by the descents t inpermutationsintheJordan-Ho¨ldersetofalllinearextensionsoftheassociatedposet. Wederive a m tri-variategeneratinggeneratingfunctionsforthenumberofwebworldsaccordingtothreestatistics andenumeratethenumberofdifferentwebdiagramsinawebworld. Threespecialwebworldsare [ examined in great detail, and the traces of the web-mixing matrices calculated in each case. 1 v 1. Introduction 6 7 In this paper we study combinatorial objects called web worlds. A web world consists of a set 5 6 of diagrams that we call web diagrams. The motivation for introducing these comes from particle . physics, where web diagrams arise as particular types of Feynman diagrams describing scattering 1 0 amplitudes of quantum fields in non-Abelian gauge (Yang-Mills) theories. These structures, which 3 do not seem to have been studied previously from the purely combinatorial point of view, may be 1 thought of as generalisations of simple graphs where each edge has a height associated to each of its : v endpoints. To avoid confusion with proper graphs, the vertices of our web diagrams will be referred i X to as pegs. The different edges that connect onto a given peg are strictly ordered by their heights r as illustrated in the example in Figure 1. The web world of a web diagram is the set of all web a diagrams that result from permuting the order in which endpoints of edges appear on a peg, that is, the heights of the edges incident with that peg. To each web world we associate two matrices, M(x) and R, which are called the web-colouring matrix and web-mixing matrix, respectively. The entries of these matrices are indexed by ordered pairs of web diagrams, and are computed from those colourings of the edges of one of the two web diagrams that yield the other one under a certain transformation (Definition 2.11) determined by each colouring. Web diagrams, web worlds and their web-mixing matrices play an important role in the study of scattering amplitudes in quantum chromodynamics (QCD) [7, 10, 9, 8]. While not essential for the combinatorial aspects dealt with here, we briefly describe the physics context in which they arise. Key words and phrases. web diagram, web world, edge colouring, reconstruction, poset. MD & ES: The work presented here was supported by grant no. 090038013 from the Icelandic Research Fund. 1 2 M.DUKES,E.GARDI,E.STEINGR´IMSSON,ANDC.D.WHITE In general, in perturbative quantum field theory, Feynman diagrams provide means of com- • puting scattering amplitudes: each diagram corresponds to an algebraic expression depend- ing on the momenta and other quantum numbers of the external particles. Specifically in QCD these diagrams describe the collisions of energetic quarks and gluons (generically re- ferred to as partons, the constituents of protons and neutrons); these carry a matrix-valued Yang-Mills charge belonging respectively to the fundamental or adjoint representations of the SU(N) group. These matrices do not commute, hence the name non-Abelian gauge theory. The perturbation expansion of a scattering amplitude, formally a power series in the cou- • pling constant (the strength of the interaction) amounts to a loop expansion: the leading term is the sum of all diagrams having a tree topology connecting all external particles, while an n-th order term in the loop expansion corresponds to the sum of all diagrams involving n loops, which is obtained by dressing a tree diagram by n additional gluon ex- changes. In a non-Abelian theory gluons may connect to each other via 3 and 4 gluon vertices. A salient feature of scattering amplitudes is that starting at one loop they involve long- • distance(“soft”)singularities. Inordertostudythestructureofthesesingularitiesonemay consideranEikonalamplitude,whichisasimplifiedversionoftheQCDscatteringamplitude that fully captures its singularities. This simplification is ultimately a consequence of the factthatallsingularitiesarisedueto“soft”(lowenergy)fields,andthequantum-mechanical incoherence of “soft” and “hard” (high energy) fields. Eikonal amplitudes are formed by representingeachexternalpartonbyanEikonalline(or“Wilsonline”),asinglesemi-infinite line extending from the origin to infinity in the direction fixed by the momentum of the external parton, and which carries the same matrix-valued Yang-Mills charge. Eikonalamplitudesexponentiate: theycanbewrittenasanexponentialwheretheexponent • takes a particularly simple form. Web diagrams arise as a direct Feynman–diagrammatic descriptionofthisexponent[7,10],namely,theydefinethecoefficientsintheloopexpansion of the exponent of the Eikonal amplitude. In these diagrams the Eikonal lines are the pegs introduced above. Loops are then formed by connecting additional gluons between these Eikonal lines: these are the edges mentioned above. Physically, the latter represent “soft” fields whose energy is small compared to energies of the external partons. Since each gluon emission along a given Eikonal line is associated with a non-commuting SU(N) matrix, the order of these emissions (corresponding to the height of the edge on the peg in the above terminology) is important, and distinguishes between different web diagrams belonging to the same web world. Following [8] we consider in this paper a particular subset of the web diagrams, those generated by any number of single gluon exchanges between the Eikonal lines. We thus exclude from the present discussion any web diagrams that includes 3 or 4 gluon vertices, as well as ones where a gluon connects an Eikonal line to itself. The generalization to these cases is interesting and will be addressed by the authors in a future paper. The present paper is a first combinatorial study of these web worlds and proves several general results. One of our results provides a rich connection between those colourings of a web diagram that lead to a unique reconstruction of the diagram on one hand, and order-preserving mappings of certain posets (partially ordered sets) on the other. This connection is then used to show that the diagonal entries of a web-mixing matrix are obtained by summing certain polynomials determined by the descents in permutations in the Jordan-H¨older set of all linear extensions of the associated poset. As for results on the enumeration of web worlds we give two tri-variate generating functions, recording statistics that keep track of the number of pegs, the number of edges and the number of pairs of pegs that are joined by some edge. We give a generating function for the number of proper WEB WORLDS, WEB-COLOURING MATRICES, AND WEB-MIXING MATRICES 3 web worlds in terms of three different statistics. We also obtain an expression for the number of different web diagrams in a given web world, in terms of entries of a matrix that represents the web world. Three special cases of web worlds are examined in great detail, and the traces of the web-mixing matrices calculated in each case. The first of these cases concerns web worlds whose web diagrams are uniquely encoded by permutations, because each peg, except for the last one, contains the left endpoint of a unique edge and all right endpoints are on the last peg. In this case we give exact values for entries of the web-mixing matrices in terms of a permutation statistic on the pair of permutations that index each entry. The other two cases are very different from the first, but quite similar to each other. Namely, these are web worlds where each pair of adjacent pegs has a unique edge between them and there are no other edges. They differ in that in one case we look at the sequence of pegs cyclically and demand that one edge join the first and the last peg. Despite the small difference in definition, the cyclic setup changes the trace of the resulting web-mixing matrices greatly. Generalising the last two cases just mentioned we define a class of web worlds that we call transitive web worlds. Remarkably, the set of transitive web worlds is in one-to-one correspondence with the (2 + 2)-free posets. It seems likely that this connection will engender some interesting results, given the fast growing literature on these posets (see [1, 2, 4, 6, 5] for references). Theoutlineofthispaperisasfollows. Section2defineswebdiagrams,webworldsandoperations on web diagrams such as colourings and how the partitioning of a web diagram induced by a colouring describes the construction of another web diagram. This section also defines the web- colouring, M(x), and web-mixing, R, matrices. Section 3 looks at colourings of a web diagram whose corresponding reconstructions result in the same web diagram. Section 4 gives generating functions for web worlds in terms of three statistics; the number of pegs, the number of edges, and the number of pairs of pegs that have at least one edge between them. It also gives an expression for the number of different web diagrams arising from a web world. Section 5 is an interlude on some material that will be used for determining web mixing matrices for particular classes of web worlds in Sections 6 to 8 In Section 6 we study a certain web world on n+1 pegs whose diagrams are uniquely encoded by permutations of the set 1,...,n . Sections 7 and 8 look at two web worlds with vastly different { } properties from that of Section 6, but closely related to one another, where each pair of adjacent pegs is connected by a unique edge. Section 9 defines transitive web worlds which are shown to be in one-to-one correspondence with (2+2)-free posets and thus with a host of other families of combinatorial structures. The paper ends with some challenging open problems in Section 10. 2. Web-diagrams Intuitively, a web diagram consists of a sequence of pegs and a set of edges, each connecting two pegs, as illustrated in the example in Figure 1. In the following formal definition of a web diagram D, a 4-tuple (x ,y ,a ,b ) D will represent an edge whose left vertex has height a on peg x j j j j j j ∈ and whose right vertex has height b on peg y . j j Definition 2.1. A web diagram on n pegs having L edges is a collection D = e = (x ,y ,a ,b ) : j j j j j { 1 j L of 4-tuples that satisfy the following properties: ≤ ≤ } (i) 1 x < y n for all j 1,...,L . j j ≤ ≤ ∈ { } (ii) For i 1,...,n let p (D) be the number of j such that x or y equals i, that is, the i j j ∈ { } number of edges in D incident with peg i. Then b : y = i a : x = i = 1,2,...,p (D) . j j j j i { }∪{ } { } We write Pegs(D) = (p (D),...,p (D)). Condition (ii) says that the labels of the p (D) vertices 1 n i on peg i, when read, say, from top to bottom, are a permutation of the set 1,...,p (D) . i { } 4 M.DUKES,E.GARDI,E.STEINGR´IMSSON,ANDC.D.WHITE 1 2 2 7 2 2 1 1 1 2 4 2 1 1 2 2 4 2 6 4 3 1 2 3 1 2 3 3 3 2 2 2 4 1 2 1 1 1 1 1 1 1 2 3 4 5 6 7 5 4 Figure 1. In the diagram on the left the indices of the pegs are shown at the bottom. The heights of the endpoints of the edges are shown in italics at each endpoint. The unique edge between pegs 3 and 6 is represented by the 4-tuple (3,6,2,4) since the left endpoint of the edge (on peg 3) has height 2 and the right endpoint of the edge (on peg 6) has height 4. The diagram on the right is the Feynman diagram illustration of the web diagram. Given a web diagram D = e = (x ,y ,a ,b ) : 1 j L , let j j j j j { ≤ ≤ } PegSet(D) = x ,...,x ,y ,...,y , 1 L 1 L { } EdgeSet(D) = D, PegpairsSet(D) = (x ,y ),...,(x ,y ) . 1 1 L L { } Example 2.2. The web diagram given in Figure 1 is D = (1,2,1,1),(1,7,2,2),(2,4,2,3),(3,4,1,1),(3,6,2,4),(4,6,2,3),(4,6,4,2),(5,6,1,1),(5,7,2,1) . { } The number of vertices on each peg is Pegs(D) = (2,2,2,4,2,4,2). Also, PegSet(D) = 1,2,3,4,5,6,7 , { } PegpairsSet(D) = (1,2),(1,7),(2,4),(3,4),(3,6),(4,6),(5,6),(5,7) . { } Notice that in this particular example PegpairsSet(D) has size one less than EdgeSet(D) since there are two edges that connect pegs 4 and 6. We now define the sum of two web diagrams. Definition 2.3. Let D = e = (x ,y ,a ,b ) : 1 j L and D(cid:48) = e(cid:48) = (x(cid:48),y(cid:48),a(cid:48),b(cid:48)) : 1 j { j j j j j ≤ ≤ } { j j j j j ≤ ≤ L(cid:48) be two web diagrams with PegSet(D),PegSet(D(cid:48)) 1,...,n . The sum D D(cid:48) is the web } ⊆ { } ⊕ diagram obtained by placing the diagram D(cid:48) on top of D; D⊕D(cid:48) = D∪{(x(cid:48)j,yj(cid:48),a(cid:48)j +px(cid:48)j(D),b(cid:48)j +pyj(cid:48)(D)) : 1 ≤ j ≤ L(cid:48)}. If there exist two non-empty web diagrams E and F such that D = E F then we say that D is ⊕ decomposable. Otherwise we say that D is indecomposable. Example 2.4. Consider the following two web diagrams: D = (1,4,1,1),(2,6,1,2),(2,6,2,1) 1 { } and D = (1,2,1,1),(3,5,1,1),(5,6,2,1) . For D we have (p (D ),...,p (D )) = (1,2,0,1,0,2) 2 1 1 1 6 1 { } WEB WORLDS, WEB-COLOURING MATRICES, AND WEB-MIXING MATRICES 5 2 4 2 2 3 3 2 2 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Figure 2. The transformation X rel(X). → and so D D 1 2 ⊕ = (1,4,1,1),(2,6,1,2),(2,6,2,1) (1,2,1+p (D ),1+p (D )), 1 1 2 1 { } ∪ { (3,5,1+p (D ),1+p (D )),(5,6,2+p (D ),1+p (D )) 3 1 5 1 5 1 6 1 } = (1,4,1,1),(2,6,1,2),(2,6,2,1) (1,2,1+1,1+2),(3,5,1+0,1+0),(5,6,2+0,1+2) { } ∪ { } = (1,4,1,1),(2,6,1,2),(2,6,2,1),(1,2,2,3),(3,5,1,1),(5,6,2,3) . { } Definition 2.5. Let D be a web diagram and X D. Let rel(X) be the web diagram that results ⊆ from re-labeling the third and fourth entries of every element of X so that the set of labels of points on a peg i of rel(X) are 1,2,...,(cid:96) for some (cid:96) , and for all pegs. We call rel(X) a subweb diagram i i { } of D. Note that we do not remove empty pegs. The reason we do not remove them is that we will be defining an operation which combines subweb diagrams of a diagram. This will be made clear in Definitions 2.11 and 2.12. Example 2.6. Let D be the web diagram in Figure 1. Let X = (1,7,2,2),(3,6,2,4),(4,6,2,3),(5,6,1,1) . { } Then rel(X) = (1,7,1,1),(3,6,1,3),(4,6,1,2),(5,6,1,1) . See Figure 2. { } Definition 2.7. Suppose that D = (x ,y ,a ,b ) : 1 j L is a web diagram on n pegs. Let j j j j { ≤ ≤ } Pegs(D) = (p (D),...,p (D)). Let π = (π(1),...,π(n)) be a sequence of permutations where π(i) 1 n is a permutation of the set 1,...,p (D) . Let π(D) be the web diagram that results from moving i { } the vertex at height j on peg i to height π(i)(j), for all j and i. Finally let W(D) = π(D) : π { ∈ Pegs(D) , the set of all possible web diagrams that can be obtained from D. We call W(D) the } web world of D. Example2.8. IfD = (1,2,1,2),(1,2,2,1) thenW(D) = D,E whereE = (1,2,1,1),(1,2,2,2) . { } { } { } In terms of physics, a particular subset of web worlds are of interest. Definition 2.9. Let W be a web world and D = (x ,y ,a ,b ) : 1 i L W. Let i i i i { ≤ ≤ } ∈ G(W) = (V,E,(cid:96)) be the edge-labeled simple graph where V = PegSet(D), E = x ,y , x ,y ,..., x ,y 1 1 2 2 L L {{ } { } { }} and (cid:96)( x,y ) = 1 i L ; x = min(x,y) and y = max(x,y) i i { } |{ ≤ ≤ }| for all x,y E. We call G(W) the web graph of the web world W. { } ∈ 6 M.DUKES,E.GARDI,E.STEINGR´IMSSON,ANDC.D.WHITE The web graph is the graph that results from ‘forgetting’ the heights of all endpoints of edges in a web diagram. Another way to say this is that this is the graph one sees by looking down onto a web diagram, so that the pegs appear as points, and where each edge of G(W) is weighted by the number of edges between the two pegs containing its endpoints in the original diagram. For example, the web graph corresponding to the web world generated by the diagram in Figure 1 is: 1 1 1 7 2 1 1 1 6 3 2 1 1 5 4 Definition 2.10. A web world W is called proper if the web graph G(W) is connected. Proper web worlds have been called ‘webs’ in references [7, 8, 9, 10]. Their significance is that they contribute to the exponent of an Eikonal amplitude, while web worlds corresponding to disconnected web graphs do not. The three web worlds we look at later on is this paper are proper web worlds. We now introduce colouring and reconstruction operations on our web diagrams. Definition 2.11. Suppose that D = e = (x ,y ,a ,b ) : 1 i L is a web diagram on n pegs, i i i i i { ≤ ≤ } and (cid:96) L a positive integer. A colouring c of D is a surjective function c : 1,...,L 1,...,(cid:96) . ≤ { } → { } Let D (j) = e D : c(i) = j for all 1 j (cid:96), the set of all those edges of D that are coloured c i { ∈ } ≤ ≤ j. The reconstruction Recon(D,c) W(D) of D according to the colouring c is the web diagram ∈ Recon(D,c) = rel(D (1)) rel(D (2)) rel(D ((cid:96))). c c c ⊕ ⊕···⊕ Definition 2.12. Let D be a web diagram on n pegs, and let c be an (cid:96)-colouring of D. We say that the colouring c is self-reconstructing if Recon(D,c) = D. Given W = W(D) for some web diagram D on n pegs, and D ,D W(D), let 1 2 ∈ F(D ,D ,(cid:96)) = (cid:96)-colourings c of D : Recon(D ,c) = D 1 2 1 1 2 { } and f(D ,D ,(cid:96)) = F(D ,D ,(cid:96)) . Let M(W)(x) be the matrix whose (D ,D )-entry is 1 2 1 2 1 2 | | M(W) (x) = (cid:88)x(cid:96)f(D ,D ,(cid:96)). D1,D2 1 2 (cid:96)≥1 We call this matrix the web-colouring matrix. From a physics perspective, another matrix is of more immediate interest. Let R(W) be the matrix whose (D ,D ) entry is 1 2 R(W) = (cid:88) (−1)(cid:96)−1f(D ,D ,(cid:96)). D1,D2 (cid:96) 1 2 (cid:96)≥1 We call R(W) the web-mixing matrix of W. It is straightforward to show that the (D ,D ) entries 1 2 of M(W)(x) and R(W) are related via the following formula: (cid:90) 0 M(W) (x) (cid:90) 1 M(W) ( x) R(W) = D1,D2 dx = D1,D2 − dx. (1) D1,D2 x − x −1 0 In the present paper, the basic problems we consider are as follows: Given a web world W, (i) What can we say about the matrices M(W)(x) and R(W), their entries, trace and rank? (ii) Can we determine the entries of M(W)(x) and R(W) for special cases? WEB WORLDS, WEB-COLOURING MATRICES, AND WEB-MIXING MATRICES 7 In Gardi and White [9] it was shown that Theorem 2.13. [9] Let W be a web world. (i) The row sums of R(W) are all zero. (ii) R(W) is idempotent. In the next section we look at diagonal entries of the matrices M(W)(x) and R(W). The following theorem is the M-analogue to Theorem 2.13(i). We omit the proof as it is rather elementary. Theorem 2.14. Let D be a web diagram with m = D edges. The row sums M(W)(x) are all the | | same and given by the ordered Bell polynomials m (cid:26) (cid:27) (cid:88) m (x) = x(cid:96) (cid:96)! m ℵ (cid:96) (cid:96)=1 where (cid:8)m(cid:9) are the Stirling numbers of the 2nd kind. (cid:96) Using the recursion (cid:8)m+1(cid:9) = (cid:8) m (cid:9)+(cid:8)m(cid:9) in the definition of (x) above, one finds that the (cid:96) (cid:96)−1 (cid:96) ℵm+1 polynomials (x)satisfythedifferentialequationx(d/dx)((x+1) (x)) = (x). Equivalently, m m m+1 ℵ ℵ ℵ (cid:88) 1 (x)tm = . ℵm xt m≥0 1 − (x+1)t 1 − 2xt 1 − 2(x+1)t 1 − 1 ... − 3. Self-reconstructing colourings and order-preserving maps In this section we will study those colourings of a web diagram D that reconstruct D. This is to gain insight into the diagonal entries of the matrices M(W)(x) and R(W) and thus their traces. Since R(W) is idempotent (Theorem 2.13), its trace is also its rank, which plays an important role inthephysicscontext[7]. InwhatfollowswewillseethateverywebdiagramD canbedecomposed and written as a sum of indecomposable subweb diagrams. A poset (partially ordered set) P on the set of these indecomposable subweb diagrams is then formed. Self-reconstructing colourings of D are then shown to correspond to linear extensions of P, to be explained below. Definition 3.1. Let W be a web world and D W. Suppose that D = E E E 1 2 k ∈ ⊕ ⊕ ··· ⊕ where each E is an indecomposable web diagram. Define the partial order P = (P, ) as follows: i (cid:22) P = (E ,...,E ) and E E if 1 k i j (cid:22) (a) i < j, and (b) there is an edge e = (x,y,a,b) in E and an edge e(cid:48) = (x(cid:48),y(cid:48),a(cid:48),b(cid:48)) in E such that an i j endpoint of e is below an endpoint of e(cid:48) on some peg. We call P(D) the decomposition poset of D. Example 3.2. Consider the diagram D given in Figure 1. The poset P(D) we get from this dia- gram is illustrated as follows: 8 M.DUKES,E.GARDI,E.STEINGR´IMSSON,ANDC.D.WHITE D P ( D ) E 7 E E 5 7 E 5 E E E E 4 6 4 6 E E E E E E 1 2 3 2 1 3 Note that E = (1,2,1,1) , E = (3,4,1,1) , E = (5,6,1,1) , E = (2,4,2,3),(4,6,2,3), 1 2 3 4 { } { } { } { (4,6,4,2) , E = (3,6,2,4) , E = (5,7,2,1) , and E = (1,7,2,2) . 5 6 7 } { } { } { } Before we explain the relation between the linear extensions of P(D) and self-reconstructing colourings we need some background. Given any two posets P and Q, a map f : P Q is → order-preserving if, for all x and y in P, x y implies f(x) f(y). Let p be the number of P Q (cid:22) (cid:22) elements in a poset P. A linear extension of P is an order-preserving bijection f : P [p] where → [p] = 1,...,p is equipped with the usual order on the integers. Each linear extension of P can { } be represented by a permutation of the elements of P, where the first element in the permutation is that element x of P for which f(x) = 1 and so on. The set of these permutations is called the Jordan-H¨older set of P, and denoted (P). L Recall that a descent in a permutation π = a a ...a is an i such that a > a , and let des(π) 1 2 n i i+1 be the number of descents in π. The first part of the following lemma is from [11, Theorem 3.15.8]. The second part follows from the first part using the inclusion-exclusion principle. Lemma 3.3. Let P be a poset with p elements, and let Ω(P,m) be the number of order preserving maps σ : P [m]. Then → (cid:88) 1 (cid:88) Ω(P,m)xm = x1+des(π). (1 x)p+1 m≥0 − π∈L(P) Let Θ(P,m) be the number of surjective order-preserving maps from P to [m]. Define Θ(P,0) = Ω(P,0) = 0. Then we have (cid:18) (cid:19) (cid:18) (cid:19) (cid:88) m (cid:88) m Ω(P,m) = Θ(P,k), Θ(P,m) = ( 1)m−kΩ(P,k). k k − k k From now on, we will assume that, as in Example 2.4, we have labeled the elements of P = P(D) naturally, that is, so that if E < E in P then i < j. In a permutation π = E E ...E in (P), i j i1 i2 ip L declare k to be a descent if and only if i > i . k k+1 Theorem 3.4. Let D be a web diagram with D = E ... E where the entries of the sum are 1 k ⊕ ⊕ all indecomposable web diagrams. Let P = P(D) and p = P(D) . If every member of the sequence | | (E ,...,E ) is distinct then 1 k (cid:88) M(W)(x) = x1+des(π)(1+x)p−1−des(π) (2) D,D π∈L(P) and (cid:88) ( 1)des(π) R(W) = − . (3) D,D p(cid:0) p−1 (cid:1) π∈L(P) des(π) WEB WORLDS, WEB-COLOURING MATRICES, AND WEB-MIXING MATRICES 9 Proof. The number f(D,D,(cid:96)) defined in Section 2 is the number of surjective order-preserving maps from P(D) to 1,...,(cid:96) . By Lemma 3.3 we get { } (cid:18) (cid:19)1+des(π) (cid:88) (cid:88) x Θ(P,m)xm = (1+x)p = M(W)(x). 1+x D,D m≥0 π∈L(P) Let B(x,y) = (cid:82)1tx−1(1 t)y−1dt be the beta function. For the diagonal terms of the web mixing 0 − matrix we have (cid:88) (cid:90) 0 (cid:16) (cid:17) R(W) = dx xdes(π)(1+x)p−1−des(π) D,D −1 π∈L(P) (cid:88) = ( 1)des(π)B(des(π)+1,p des(π)) − − π∈L(P) (cid:88) ( 1)des(π) = − . (cid:3) p(cid:0) p−1 (cid:1) π∈L(P) des(π) By Theorem 3.4, computing the diagonal entries of our matrices is thus equivalent to computing the descent statistic on the Jordan-H¨older set of the corresponding poset. Example 3.5. Let D be the following web diagram: E 3 E 2 E 1 1 2 3 4 Since each of the web diagrams (E ,E ,E ) are distinct, Theorem 3.4 may be applied. The 1 2 3 poset P = P(D) is the poset on E ,E ,E with relations E < E ,E . We find that (P) = 1 2 3 1 2 3 { } L E E E ,E E E , with des(E E E ) = 0 and des(E E E ) = 1. Consequently we have 1 2 3 1 3 2 1 2 3 1 3 2 { } M(W(n))(x) = x(1+x)2+x2(1+x) = x+3x2+2x3 D,D and R(W) = ( 1)0/3+( 1)1/3(cid:0)2(cid:1) = 1/6. D,D − − 1 Given a web world W, let AllPosets(W) = P(D) : D W . For P AllPosets(W), let { ∈ } ∈ multip (P) = D W : P(D) = P . Using this notation we have W |{ ∈ }| Corollary 3.6. Suppose that W is a web world whose graph G(W) = (V,E,(cid:96)) is such that (cid:96)(e) = 1 for all e E. Then ∈ (cid:88) trace(M(W)(x)) = M(W)(x) D,D D∈W (cid:88) (cid:88) = multip (P) x1+des(π)(1+x)|P|−1−des(π) (4) W P∈AllPosets(W) π∈L(P) and trace(R(W)) = (cid:88) R(W) D,D D∈W (cid:88) (cid:88) ( 1)des(π) = multip (P) − (5) W p(cid:0) p−1 (cid:1) P∈AllPosets(W) π∈L(P) des(π) 10 M.DUKES,E.GARDI,E.STEINGR´IMSSON,ANDC.D.WHITE Note that, owing to the idempotence of web mixing matrices (Theorem 2.13), the trace of a web mixing matrix is equal to its rank. A corollary is that the trace must be a positive integer number. In the physics context of reference [7] this invariant represents the number of independent contributionstotheexponentofanEikonalscatteringamplitudefromthecorrespondingwebworld. We illustrate the above calculations in the following two examples. In the first example posets on a different number of elements emerge. However, in the second example only posets on three elements emerge. The second example is a special case of the web world that will be discussed later in Case 2 in Section 7. Example 3.7. The web world W(D) of the web diagram D = (1,2,1,1),(2,3,2,1),(3,4,2,1) { } contains four web diagrams. AllPosets(W) contains three posets; the chain 3 arises twice; the wedge poset arises once, as does the V-shaped poset . Thus multip (3) = 2 and multip ( ) = ∧ ∨ W W ∧ multip ( ) = 1. We have (3) = (1,2,3) and ( ) = ( ) = (1,2,3),(1,3,2) . Thus, W ∨ L { } L ∨ L ∧ { } trace(M(W)(x)) = 2(x1(1+x)2)+1(x1(1+x)2+x2(1+x))+1(x1(1+x)2+x2(1+x)) = 6x3+10x2+4x and trace(R(W)) = 2(1/3)+1(1/6)+1(1/6) = 1. (See Figure 3.) 4. The number of web worlds In this section we present some results on the number of web worlds with prescribed sizes of the sets PegSet, EdgeSet, and PegpairsSet. If W is a web world and D ,D are two web diagrams 1 2 in W, then PegSet(D ) = PegSet(D ), EdgeSet(D ) = EdgeSet(D ), and PegpairsSet(D ) = 1 2 1 2 1 PegpairsSet(D ). We will use PegSet(W), EdgeSet(W), and PegpairsSet(W) to refer to these 2 numbers without having to refer to diagrams of the web world. A web world W is uniquely specified by its web graph G(W) = (V,E,(cid:96)). An equivalent specifi- cation is by a square matrix Represent(W) of integers whereby (cid:26) (cid:96)(i,j) if i < j and i,j E, Represent(W)i,j = 0 otherwise. { } ∈ Theorem 4.3 gives the generating function for the number of web worlds according to these three statistics. Web-worldswhichcontainpegsthathavenoincidentedges,equivalenttoisolatedvertices when one talks of graphs, have little relevance in the corresponding physics model. Theorem 4.4 gives the generating function for the number of web worlds with no isolated pegs, according to the three statistics. Theorem 4.6 gives the generating function for the number of proper web worlds according to the same three statistics as Theorem 4.4. Theorem 4.7 gives an expression for the number of different diagrams in a web world in terms of the values in the matrix Represent(W). Let W be a web world and D a web diagram in W. Define the web diagram matrix of a web diagram D to be a matrix WDM(D) whose entries are sets: (a ,b ) WDM(D) for all (x ,y ,a ,b ) D. j j ∈ xj,yj j j j j ∈ Example 4.1. Consider the web diagram D in Figure 1. The set of 4-tuples for that web diagram is (1,2,1,1),(1,7,2,2),(2,4,2,3),(3,4,1,1),(3,6,2,4),(4,6,2,3),(4,6,4,2),(5,6,1,1),(5,7,2,1) . { }