{'fraction_non_alphanumeric': 0.03522316330414922, 'fraction_numerical': 0.010575275980205558, 'mean_word_length': 4.135935972629521, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Topological Graph Polynomials and Quantum Field Theory, Part I: Heat Kernel Theories

We investigate the relationship between the universal topological polynomials for graphs in mathematics and the parametric representation of Feynman amplitudes in quantum field theory. In this first paper we consider translation invariant theories with the usual heat-kernel-based propagator. We show how the Symanzik polynomials of quantum field theory are particular multivariate versions of the Tutte polynomial, and how the new polynomials of noncommutative quantum field theory are particular versions of the Bollob\'as-Riordan polynomials.


Introduction
Quantum field theory lies at the root of modern physics. After the success of the standard model in describing particle physics, one of the most pressing open question is how to derive an extended version of field theory which encompasses the quantization of gravity. There are several attempts for this, among which string theory, loop gravity and noncommutative geometry are the best known. In each of these attempts one of the key problem is to relax the constraints that formulate quantum field theory on a particular space-time geometry.
What is certainly more fundamental than geometry is topology and in particular discrete structures on finite sets such as the species of combinatorists [1]. The most prominent such species in field theory is the species of Feynman graphs. They were introduced by Feynman to label quantum field perturbation theory and to automatize the computation of connected functions. Feynman graphs also became an essential tool in renormalization, the structure at the heart of quantum field theory.
There are two general canonical operations on graphs namely the deletion or contraction of edges. Accordingly perhaps the most important quantity to characterize a graph is its Tutte polynomial [2,3]. This polynomial obeys a simple recursion rule under these two basic operations. It exists in many different variations, for instance multivariate versions, with possible decorations at vertices. These polynomials have many applications, in particular to statistical physics. For recent reviews see [4,5,6].
In recent years the Tutte polynomial has been generalized to the category of ribbon graphs, where it goes under the name of the Bollobás-Riordan polynomial [7,8,6]. Around the same time physicists have increasingly turned their attention to quantum field theory formulated on noncommutative spaces, in particular flat vector spaces equipped with the Moyal-Weyl product [9]. This type of quantum field theory is hereafter called NCQFT. It happens that perturbation theory for such NCQFT's is no longer labeled by ordinary graphs but by ribbon graphs, suggesting a possible connection to the work of Bollobás-Riordan.
Quantum field perturbation theory can be expressed in several representations. The momentum representation is the most common in the text books. The direct space representation is closer to physical intuition. However it is the parametric representation which is the most elegant and compact one. In this representation, after the integration of internal position and/or momentum variables has been performed explicitly, the result is expressed in terms of the Symanzik polynomials. There is an extensive literature on these polynomials (see e.g. [10,11] for classical reviews). These polynomials only depend on the Schwinger parameters. Space time no longer enters explicitly into that representation except through its dimension which appears simply as a parameter.
This observation is crucial for several key applications in QFT which rely on dimensional interpolation. Dimensional regularization and renormalization was a crucial tool in the proof by 't Hooft and Veltmann that non-Abelian gauge theories are renormalizable [12]. The Wilson-Fisher expansion [13] is our best theoretical tool to understand three dimensional phase transitions. Dimensional regularization is also used extensively in the works of Kreimer and Connes [14,15] which recast the recursive BPHZ forest formula of perturbative renormalization into a Hopf algebra structure and relate it to a new class of Riemann-Hilbert problems [16].
Following these works, renormalizability has further attracted considerable interest in the recent years as a pure mathematical structure. The renormalization group ambiguity reminds mathematicians of the Galois group ambiguity for roots of algebraic equations [17]. Hence the motivations to study quantum field theory and renormalization come no longer solely from physics but also at least partly from number theory.
The fact that the parametric representation is relatively independent of the details of space time makes it also particularly appealing as a prototype for the tools we need in order to quantize gravity. The point of view of loop gravity is essentially based on the diffeomorphism invariance of general relativity. In the spin foam or group field theory formalism amplitudes are expressed as discrete sums associated to combinatoric structures which generalize Feynman graphs. They are in fact generalizations of ribbon graphs. To extend the parametric representation and eventually the theory of renormalization to this context is a major challenge, in which some preliminary steps have been performed [18].
In this paper we uncover the relationship between universal polynomials of the Tutte and Bollobás-Riordan type and the parametric representation in quantum field theory. The Symanzik polynomials that appear in ordinary commutative QFT are particular multivariate versions of Tutte polynomials. The relation between Bollobás-Riordan polynomials and the non commutative analogs of the Symanzik polynomials uncovered in [19,20,21] is new. This establishes a relation between NCQFT, combinatorics and algebraic topology. Recently the relation between renormalization and topological polynomials was explored in [22], and in [23]. We intend also to explore in the future the relation between Feynman amplitudes and knot polynomials.
The plan of this paper is as follows. In the next section we give a brief introduction to graph theory and to Tutte-like polynomials. In the third section we derive the parametric representation of Feynman amplitudes of QFT and give a new method to compute the corresponding Symanzik polynomials. The deletion/contraction property (2.11) of these polynomials is certainly not entirely new [24,25]. But our method which starts from the phase-space representation of Feynman amplitudes is inspired by earlier work on NCQFT [20,21] and introduces two main technical improvements. One is the use of Grassmann variables to exploit the quasi-Pfaffian structure of Feynman amplitudes. This quasi-Pfaffian structure was discovered in [20] in the context of NCQFT but to our knowledge was never applied to the simpler case of ordinary QFT. The second improvement is that we do not factor out as usual the delta functions expressing global momentum conservation, because this requires a noncanonical choice of a root for every connected graph. Instead we introduce an infrared regularization in the form of a small harmonic potential at each vertex which leads to more elegant and canonical formulas. The corresponding generalized Symanzik polynomials obey a transparent deletion/contraction relation which allows to identify them with particular multivariate Tutte polynomials. These polynomials are close but not identical to the polynomials of [4]; we show how they both derive from a more general "categorified" polynomial. The usual Symanzik polynomials are simply recovered as the leading terms when the small harmonic potentials tend to zero.
For completeness we also include a more standard way to compute the Symanzik polynomials through x space representation and the tree matrix theorem.
In the fourth section we introduce ribbon graphs and Bollobás-Riordan polynomials. In the fifth and last section we define the first and second Symanzik polynomials of NCQFT and relate them to the Bollobás-Riordan polynomials, using again the Pfaffian variables. Formulas for such polynomials were first sketched in [19], but without proofs, nor relation to the Bollobás-Riordan polynomials.
In a companion paper we shall discuss generalizations of the Tutte and Bollobás-Riordan polynomials that occur for non-translation invariant theories with propagators based on the Mehler rather than the heat kernel. These theories appeared as the first examples of renormalizable NCQFT's [26,27,28,29,31] and they are the most promising candidates for a fully non-perturbative construction of a field theory in four dimensions [32,33,34,35]. In this case the harmonic potentials on the vertices are no longer needed as the Mehler kernel already contains an harmonic potential for the propagators of the graphs.

Graph Theory, Notations
A graph G is defined as a set of vertices V and of edges E together with an incidence relation between them. The number of vertices and edges in a graph will be noted edge flag self−loop Figure 1: Basic building blocks of a graph also V and E for simplicity, since our context always prevents any confusion. Graph theorists and field theorists usually have different words for the same objects so a little dictionary may be in order. We shall mostly use in this review the graph theorists language. In subsection 2.4 we introduce also some enlarged notion of graphs, with decorations called flags which are attached to the vertices of the graph to treat the external variables of physicists, plus other decorations also attached to vertices called (harmonic) weights to regularize infrared divergences. Generalizations to ribbon graphs will be described in section 4. Edges in physics are called lines (or propagators). Edges which start and end at the same vertex are definitely allowed, and called (self)-loops in graph theory and tadpoles in physics. A proper graph, i.e. a graph G without such self-loops, together with an arrow orienting each edge, can be fully characterized through its incidence matrix ve . It is the rectangular E by V matrix with indices running over vertices and edges respectively, such that It is also useful to introduce the absolute value η ve = | ve | These quantities can be then generalized to graphs with self-loops by defining ev = 0 for any self-loop e and vertex v but η ev = 2 for a self-loop attached at vertex v and η ev = 0 otherwise. The number of half-edges at a vertex v is called the degree of v in graph theory, noted d(v). Physicists usually call it the coordination number at v. A self-loop counts for 2 in the degree of its vertex, so that d(v) = e η ev .
An edge whose removal increases (by one) the number of connected parts of the graph is called a bridge in graph theory and a one-particle-reducible line in physics.
A forest is an acyclic graph and a tree is a connected forest. A cycle in graph theory is a connected subset of n edges and n vertices which cannot be disconnected by removing any edge. It is called a loop in field theory.
Physicists understood earlier than graph theorists that half-edges (also called flags in graph theory [36]) are more fundamental than edges. This is because they correspond to integrated fields through the rule of Gaußian integration, which physicists call Wick's theorem. Feynman graphs form a category of graphs with external flags decorating the vertices. They occur with particular weights, in physics called amplitudes. These weights depend on the detail of the theory, for instance the spacetime dimension. A quantum field theory can be viewed the generating functional for the species of such weighted Feynman graphs. In this paper we shall reserve the convenient word flag exclusively for the "external fields" decorations and always use the word half-edge for the "internal half-edges".
An edge which is neither a bridge nor a self-loop is called regular. We shall call semi-regular an edge which is not a self-loop, hence which joins two distinct vertices.
There are two natural operations associated to an edge e of a graph G, pictured in Figure 2: • the deletion, which leads to a graph noted G − e, • the contraction, which leads to a graph noted G/e. If e is not a self-loop, it identifies the two vertices v 1 and v 2 at the ends of e into a new vertex v 12 , attributing all the flags (half-edges) attached to v 1 and v 2 to v 12 , and then it removes e. If e is a self-loop, G/e is by definition the same as G − e.
A subgraph G of G is a subset of edges of G, together with the attached vertices. A spanning forest of G is an acyclic subgraph of G that contains all the vertices of G. If G is connected a spanning forest is in fact a tree of G and any such spanning tree has |V | − 1 vertices.
As explained in the introduction a topological graph polynomial is an algebraic or combinatoric object associated with a graph that is usually invariant under at least graph homeomorphism. It encodes information of the graph and so enables combinatoric and algebraic method to deal with graphs. The Tutte polynomial [2] is one of the most general polynomial to characterize a graph. It is defined under a simple rule through the deletion and contraction of edges. It can be generalized to the larger theory of matroids [37].
The original Tutte polynomial which is a function of two variables can be generalized in various ways to multi-variable polynomials which have many applications, in particular in statistical mechanics where it evaluates the Potts model on graphs [4,5,6]. These applications shall not be reviewed here.
We present first the two main equivalent definitions of the Tutte polynomial. One direct way is to specify its linear recursion form under contraction of regular  (which are neither loops nor bridges), together with an evaluation on terminal forms solely made of bridges and self-loops. Another definition is as a rank-nullity generating function. By induction these definitions can be proved equivalent.

Tutte Polynomial
The definition through a recursion relation is a reduction rule on edges together with an evaluation for the terminal forms. The Tutte polynomial may be defined by such a linear recursion relation under deleting and contracting regular edges. The terminal forms, i.e. the graphs without regular edges are forests (i.e. graphs made of bridges) decorated with an additional arbitrary number of self-loops at any vertex. The Tutte polynomial evaluated on these terminal forms simply counts separately the number of bridges and loops: is a graph, and e is a regular edge, then For a terminal form G with m bridges and n self-loops the polynomial is defined by It is not obvious that Definition 2.1 is a definition at all since the result might depend on the ordering in which different edges are suppressed through deletion/contraction, leading to a terminal form. The best proof that T G is unique and well-defined is in fact through a second definition of the Tutte polynomial as a global sum over subgraphs. It gives a concrete solution to the linear deletion/contraction recursion which is clearly independent on the order in which edges are suppressed: Definition 2.2 (Sum overs subsets) If G = (V, E) is a graph, then the Tutte polynomial of G, T G (x, y) has the following expansion: where r(A) = |V | − k(A) is the rank of the subgraph A and n(A) = |A| + k(A) − |V | is its nullity or cyclomatic number. In physicists language n(A) is the number of independent loops in A.
Remark that r(A) is the number of edges in any spanning forest of A, and n(A) is the number of remaining edges in A when a spanning forest is suppressed, so it is the number of independent cycles in A.
Theorem 2.1 These two definitions are equivalent.
One can show that the polynomial defined by the sum over subsets obeys the deletion-contraction recursion. One can also evaluate it directly and show that it coincides with the first definition on the terminal forms with only loops and bridges.
There is a third definition of the Tutte polynomial through spanning trees (see eg [5]). This third definition involves ordering the edges of the graph. We think it may be also relevant in the context of field theory, in particular in relation with the ordered trees or forests formulas of constructive theory [38,39,40], but this point of view will not be developed here.

Multivariate Tutte polynomials
Multivariate Tutte polynomials can also be defined through linear recursion or global formulas.
The ordinary multivariate Tutte polynomial Z G (q, {β}) has a different variable β e for each edge e, plus another variable q to count vertices. We also write it most of the time as Z G (q, β) for simplicity. It is defined through a completely general linear deletion-contraction relation: (

2.4)
This relation together with the evaluation on terminal forms completely defines Z G (q, β), since the result is again independent of the order of suppression of edges. The terminal forms are graphs without edges, and with v vertices; for such graphs Z G (q, β) = q v .
We can also define Z G (q, β) as a sum over subsets of edges: Definition 2.4 (Sum over subsets)

5)
where k(A) is the number of connected components in the subgraph (V, A).
One can prove as for the two variables Tutte polynomial that this definition is equivalent to the first. In [4] this multivariate polynomial is discussed in detail.
To understand the relation between this multivariate and the ordinary Tutte polynomial with two variables we multiply Z G by q −V , we set β e = y − 1 and q = (x − 1)(y − 1) and get (2.6) We consider also q −k(G) Z G (q, β). (2.7) Taking the limit q → 0 that is retaining only the constant term in q we obtain a sum over maximally spanning subgraphs A, that is subgraphs with k(A) = k(G): If we now retain only the lowest degree of homogeneity in β we obtain a sum over maximally spanning graphs with lowest number of edges, ie maximally spanning acyclic graphs or spanning forests of G.
Finally if we divide F G (β) by e∈E β e and change variables to α e = β −1 e we obtain the "(Kirchoff-Tutte)-Symanzik" polynomial. This polynomial is usually defined for connected graphs, in which case the sum runs over spanning trees T of G. for any regular edge e, together with the terminal form evaluation for any G solely made of self-loops and bridges. The deletion-contraction (2.11) can be extended to general edges if we define U for disconnected graphs as the product over the connected components of the corresponding U 's and put the contraction of any self-loop to 0.
The polynomial U appears in a key computation of QFT, namely that of the parametric representation of the Feynman amplitude associated to the graph G. We give a proof of this fact based on a new Pfaffian representation of Feynman amplitudes together with harmonic weights at vertices so as to make the deletion/contraction rule (2.11)-(2.12) particularly transparent.
But to define the second (Kirchoff-Tutte)-Symanzik polynomial as well as to make the computation of the first Symanzik polynomial more canonical, we need first to enlarge slightly our category of graphs to include some decorations at the vertices.

Decorated graphs
Decorations are essential in physics to represent the concept of external variables, which are ultimately those connected to actual experiments and observations. Graphs with integers attached to each vertex and their corresponding multivariate polynomials W G (α e , N v ) have been considered in [43]. But to represent external variables we need to replace the integer N v by a set of N v disjoint objects 1 , hereafter called flags (see subsection 2.1).
Each flag is attached to a single vertex. A momentum variable p f in R d is associated to each such flag. The incidence matrix can be extended to the flags, that is we define f v as +1 if the flag f is associated to the vertex v and 0 otherwise. The total momentum incident to a subset S of the graph is then defined as f v∈S f v p f . Remark that this momentum is defined for subgraphs S which may contain connected components reduced to single vertices. For translation invariant QFT's, global momentum conservation means that the condition p G = 0 must be fulfilled.
Similarly we attach to each vertex a number q v > 0 called the (harmonic) weight of the vertex. The total weight of a subgraph S is v∈S q v .
The deletion/contraction relation is then extended to this category of graphs. The deletion is easy but the contraction is a bit non trivial. For a semi-regular edge joining vertices v 1 and v 2 it collapses the two vertices into a single one v 12 , attaching to v 12 all half-edges of v 1 and v 2 . But it also attaches to v 12 the union of all the flags attached to v 1 and v 2 , so that the total momentum incoming to v 12 is the sum of the momenta incoming to v 1 and to v 2 . Finally the new weight of v 12 is the sum q v 1 + q v 2 of the weights of v 1 and v 2 .
These decorated graphs are the natural objects on which to define generalized Symanzik polynomials in field theory.
Remaining for the moment in the context of graph theory we can define the second (Kirchoff-Tutte)-Symanzik polynomial for a connected graph as where a two tree T 2 means a tree minus one edge, hence a forest with two disjoint connected components G 1 and G 2 ; the separation condition means that v and v must belong one to G 1 the other to G 2 .
For any pair of distinct vertices v and v we can build a canonical graph G(v, v ) first by joining vertices v and v in G with a new edge and then contracting that edge. This operation could be called the contraction of the pair of vertices v and v . The following result goes back to Kirchhoff [41].
The second Symanzik polynomial is a quadratic form in the total momenta p v at each vertex, whose coefficients are the U G(v,v ) polynomials: (2.14) Proof The graph G(v, v ) has V − 1 vertices, hence its spanning trees have V − 2 edges. They cannot make cycles in G because they would make cycles in G(v, v ). They are therefore two-trees in G, which must separate v and v , otherwise they would make a cycle in G(v, v ). 2 On the submanifold of flag variables satisfying the momentum conservation condition p G = f p f = 0 there is an alternate less symmetric definition of a similar polynomial: where T 2 is again a two-tree with two disjoint connected components G 1 and G 2 .
Indeed this is an unambiguous definition. On the submanifold p G = 0 we have p G 1 = −p G 2 , hence equation (2.15) does not depend of the choice of G 1 rather than G 2 .
Proposition 2.2 On the manifold of flag variables satisfying the momentum conservation condition p G = f p f = 0 one has V G (α, p) =V G (α, p).
Proof We simply commute the sums over v, v and T 2 in (2.13). For a given T 2 the condition that v and v are separated allows to separate the p v with v ∈ G 1 from the p v with v ∈ G 2 ; one gets therefore − 1 2 2p G 1 · p G 2 which is nothing but p 2 G 1 or p 2 G 2 on the manifold p G = 0.
2 We shall give in subsection 3.4 a definition of generalized first and second Symanzik polynomials for any graph, connected or not from which U G , V G orV G can be easily derived in certain limits. Before actually performing these computations we include a brief interlude on Grassmann representation of determinants and Pfaffians. The reader familiar with this topic can jump directly to the next section.

Grassmann representations of determinants and Pfaffians
Independent Grassmann variables χ 1 , ..., χ n satisfy complete anticommutation relations so that any function of these variables is a polynomial with highest degree one in each variable. The rules of Grassmann integrations are then simply The determinant of any n by n matrix can be then expressed as a Grassmann Gaußian integral over 2n independent Grassmann variables which it is convenient to name asψ 1 , . . . ,ψ n , ψ 1 , . . . , ψ n , although the bars have nothing yet at this stage to do with complex conjugation. The formula is The Pfaffian Pf(A) of an antisymmetric matrix A is defined by

Proposition 2.3
We can express the Pfaffian as: Performing the change of variables (which a posteriori justifies the complex notation) whose Jacobian is i −n , the new variables χ and ω are again independent Grassmann variables. Now a short computation using A ij = −A ji gives where we used that n = 2p has to be even and that a factor (−1) p is generated when Proof The proof consists in performing the change of variables (2.22) and canceling carefully the i factors. 2

Tree-Matrix Theorem
Let A be an n × n matrix such that Obviously det A = 0. The interesting quantities are eg the diagonal minors det A ii obtained by deleting the i-th row and the i-th column in A. The "Kirchoff-Maxwell" matrix tree theorem expresses these minors as sums over trees: where the sum is over spanning trees on {1, ...n} oriented away from root i.
Proof We give here a sketch of the Grassmann proof given in [49]. We can assume without loss of generality that i = 1. For any matrix A we have: The trick is to use (2.25) to writē by the Grassmann rules. We now expand to get where G is any subset of [n] × [n], and we used the notation Then the theorem follows from the following Lemma 2.2 Ω G = 0 unless the graph G is a tree directed away from 1 in which case Ω G = 1.
Proof Trivially, if (i, i) belongs to G, then the integrand of Ω G contains a factor ψ i −ψ i = 0 and therefore Ω G vanishes. But the crucial observation is that if there is a loop in G then again Ω G = 0. This is because then the integrand of Ω F ,R contains the factor (2.32) Inserting this telescoping expansion of the factorψ τ (k) −ψ τ (1) into the integrand of Ω F ,R , the latter breaks into a sum of (k − 1) products. For each of these products, there exists an α ∈ Z Z/kZ Z such that the factor (ψ τ (α) −ψ τ (α−1) ) appears twice : once with the + sign from the telescopic expansion of (ψ τ (k) −ψ τ (1) ), and once more with a + (resp. −) sign if (τ (α), τ (α − 1)) (resp. (τ (α − 1), τ (α))) belongs to F. Again, the Grassmann rules entail that Ω G = 0. 2 To complete the proof of (2.26) every connected component of G must contain 1, otherwise there is no way to saturate the dψ 1 integration.
This means that G has to be a directed tree on {1, ...n}. It remains only to see that G has to be directed away from 1, which is not too difficult.
2 The interlude is over and we now turn to perturbative QFT and to the parametric representation of Feynman amplitudes.

Parametric Representation of Feynman Amplitudes
In this section we will give a brief introduction to the parametric representation of ordinary QFT on a commutative vector space R d . We may take the example of φ 4 bosonic theory but the formalism is completely general.

Green and Schwinger functions in QFT
In particle physics the most important quantity is the diffusion matrix S whose elements or cross sections can be measured in particle experiments. The S matrix can be expressed from the Green functions through the reduction formulas. Hence they contain all the relevant information for that QFT. These Green functions are time ordered vacuum expectation values of the fields φ, which are operator-valued and act on the Fock space: Here ψ 0 is the vacuum state and the T -product orders φ(z 1 )...φ(z N ) according to increasing times. In the functional integral formalism the Green functions can be written as: Here L = L 0 + L int is the full Lagrangian of the theory. The Green functions continued to Euclidean points are called the Schwinger functions and are given by the Euclidean Feynman-Kac formula: For instance for the φ 4 theory, L int = λ 4! φ(x) 4 and we have where • λ is the (bare) coupling constant, which characterizes the strength of the interaction, the traditional factor 1/4! is inessential but slightly simplifies some computations.
• m is the (bare) mass, • Z is the normalization factor, • Dφ is an ill-defined "flat" product of Lebesgue measures x dφ(x) at each space time point.
The coefficient of the Laplacian is set to 1 in (3.5) for simplicity. Although this coefficient actually in four dimensions flows through renormalization, it is possible to exchange this flow for a rescaling of the field φ.
To progress towards mathematical respectability and to prepare for perturbation theory, we combine the e − R L (φ(x))dx Dφ and the free normalization factor Z 0 = e − R L (φ(x))dx Dφ into a normalized Gaußian measure dµ C (φ) which is well-defined on some subspace of the Schwartz space of distributions S (R d ) [44]. The covariance of this measure is the (free) translation invariant propagator C(x, y) = φ(x)φ(y)dµ C (φ), which by slight abuse of notation we also write as C(x − y) and whose Fourier transform is In this way the Schwinger functions are rewritten as However this expression is still formal for two reasons; for typical fields the interaction factor is not integrable over R d so that R d L int (φ) is ill-defined (infrared or thermodynamic problem) and in dimension more than 2 even when the interaction factor is restricted to a finite volume it is still ill-defined because for typical distributions φ, products such as φ 4 (x) are also ill-defined. This is the famous ultraviolet problem which requires renormalization (see [45]), but this problem is not addressed here, as we discuss solely the structure of the integrands in Feynman parametric representations, not the convergence of the integrals. The reader worried by ill-defined integrals in the rest of this paper for space-time dimension d larger than 2 should impose a ultraviolet regulator. This means he should replace replace C(p) by a better behaved C κ (p) such as We now turn to perturbation theory in which the factor e − R R d L int (φ) is expanded as a power series. This solves the thermodynamic problem, at the cost of introducing another problem, the divergence of that perturbation expansion. This divergence which in the good cases can be tackled by constructive field theory [44,46,47,48] will not be treated in this paper.

Perturbation theory, Feynman Graphs
Wick theorem is nothing but the rule of pairing which computes the moments of a Gaußian measure. It allows to integrate monomials of fields where the sum over G is over all contraction schemes (i.e. pairings of the fields) and C(x ie , x je ) is the propagator kernel joining the arguments of the two fields φ(x ie ) and φ(x je ) paired into the edge e by the contraction scheme G. It was Feynman's master stroke to represent each such contraction scheme by a particular graph in which edges represent pairs of contracted fields and vertices stand for the interaction.
In the case of a φ 4 theory, remark that these interaction vertices have degree 4. Indeed the Schwinger functions after perturbative expansion are The pairings of Wick's theorem therefore occur between n internal vertices each equipped with four fields and N external vertices or sources corresponding to the single fields φ(z 1 ), ... , φ(z N ). Schwinger function are therefore expressed as sums over Feynman graphs of associated quantities or weights called the Feynman amplitudes. In this position space representation the Feynman graphs have both n internal vertices corresponding to the L int factors, plus N external vertices of degree 1 corresponding to the fields φ(z 1 ), ..., φ(z N ). In the case of the φ 4 theory each internal vertex has degree 4.
The Feynman amplitudes are obtained by integrating over all positions of internal vertices the product of the propagator kernels for all the edges of the graphs (3.13) where the product v runs over the internal vertices v.
The quantities that are relevant to physical experiments are the connected Schwinger functions which can be written as: where S(G) is a combinatoric factor (symmetry factor). The momentum space representation corresponds to a Fourier transform to momenta variables called p 1 , ..., p N : where the factor 2 is convenient and we forget inessential normalization factors. This is a distribution, proportional to a global momentum conservation δ( N f =1 p f ). From now on we use an index f to label external momenta to remember that they are associated to corresponding graph-theoretic flags. Usually one factors out this distribution together with the external propagators, to obtain the expansion in terms of truncated amputated graphs: In this sum we have to describe in more detail the truncated graphs G with N external flags. Such truncated graphs are connected, but they may contain bridges and selfloops. They no longer have external vertices of degree 1. Instead, they still have N external variables p f , no longer associated to edges but to flags (N in total), which decorate the former internal vertices. For instance for the φ 4 theory the degree of a truncated graph G is no longer 4 at each internal vertex. It is the total degree, that is the number of half-edges plus flags which remains 4 at every vertex.

Parametric representation
We shall first consider a fixed truncated oriented diagram G and compute the corresponding contribution or amplitude A T G as given by Feynman rules. We denote again by E and V the number of edges and vertices respectively, and by N the number of flags. Since G is connected its incidence matrix has rank V − 1.
Now consider a Feynman graph G contributing to some truncated Schwinger function Γ T (p 1 , ..., p N ). The usual way to take into account the global δ function in (3.16) is to restrict to configurations such that f p f = 0. Extraction of this global delta function in (3.16) for the amplitude of a particular graph can be done provided we do not integrate the position of one of the vertices in (3.13), but rather fix it at an arbitrary point, eg the origin. From now on we suppose this vertex isv the one with last index. It provides a root in the graph G. However this standard procedure requires the non-canonical choice of that root vertex, and the final result does not depend on that choice.
Another possibility is to modify the interaction λφ 4 (x) into λe −qx 2 φ 4 (x), in which case there is no longer global momentum conservation. One can compute modified amplitudes B T G (p 1 , ...p N ; q) without factoring out the global δ( N f =1 p f ) factor, so that The momentum conserving usual amplitudes are recovered when q → 0: This is the procedure we shall follow in subsection 3.4, because it avoids the choice of a noncanonical root. But for the moment let us complete the standard presentation of A T G (p 1 , ..., p N ).
The momentum representation of A T G , forgetting from now on inessential factors of 2π, is: . (3.19) in which we use the convention that repeated indices are summed, so that f v p f + ev k e stands for the total momentum f f v p f + e ev k e incoming at vertex v.
To obtain the parametric representation we have first to rewrite the propagators as : 1 (3.20) We obtain the momentum parametric representation Fourier transforming the V − 1 Dirac distributions into oscillating integrals we obtain, up to some inessential global factors the phase-space parametric representation v=1 k e ev x v etc, and the factor 2 is convenient. Finally integrating out the edge momenta whose dependence is Gaußian leads to the x or direct space parametric representation: Remember this amplitude is only defined on the submanifold p G = 0, because it is only there that the formula gives a result independent of the choice of the root not integrated out in (3.23) The parametric representation consists in integrating out fully the x or p variables in (3.21), (3.22) or (3.23). One obtains the parametric representation, which is an integral on α parameters only: where U G and V G are called the first and second Symanzik's polynomials. .24) is the multivariate Tutte polynomial (2.10). On the submanifold p G = 0, the only one where it is unambiguously defined, the second polynomial V G of (3.24) coincides with (2.13) and (2.15).
We are going to give two proofs of this classic theorem of quantum field theory, one relying directly on contraction-deletion and on the phase-space representation (3.22) the other more standard and relying on the direct representation (3.23) and on the tree-matrix theorem.
Indeed in order to compute the Symanzik's polynomials, let us remark first that the momentum representation mostly used in textbooks is not very convenient. To use (3.21) we should "solve" the δ functions, that is rewrite each edge momentum in terms of independent momenta for cycles. In physics this is called a momentum routing. But such a momentum routing is linked to the choice of a particular spanning tree of G. The momenta of the edges not in this tree are kept as independent variables and the tree edges momenta are recursively computed in terms of those by progressing from the leaves of the tree towards the root which is the fixed vertex v n . This is not a canonical prescription, as it depends on the choice of the tree.
The representations (3.22) or (3.23) are more convenient to integrate the space or momentum variables because the dependence in variables x and k is Gaußian so that the result is a determinant to a certain power times a Gaußian in the external variables. In fact (3.22) is the best as we shall argue below. However there is still a small noncanonical choice, the one of the root. This is why we prefer to compute the regularized amplitudes and to deduce the ordinary amplitudes from a limit q → 0. The last modification we perform is to attribute a different weight q v to each vertex regulator. This is more natural from the point of view of universal polynomials. So we define (3.26) These amplitudes are Gaußian in the external variables p f and no longer involve any noncanonical choice. We shall now compute their generalized Symanzik polynomials and deduce the ordinary Symanzik polynomials from these as leading terms when all q v 's are sent to 0.

Generalized Symanzik Polynomials
We consider the phase space representation (3.26). We have to perform a Gaußian integral in E + V variables (each of which is d-dimensional). We consider these momentum and position variables as a single vector. We also forget the label T for truncation as it is no longer needed in this section. The graph we consider may be connected or not.
We introduce the condensed notations: where α e and q v are short notations for diagonal matrices α e δ e,e and q v δ v,v . Y is an We can further decompose X G as the real rectangular N by E + V matrix made of a dN by dE zero block and the dN by dV "incidence flag" matrix µ f v . The dimensional indices µ being quite trivial we no longer write them down from now on.
Note P the line p f , hence the last part of the line Y . Gaußian integrations can be performed explicitly and the result is a Gaußian in external variables. Therefore up to inessential constants for some polynomial U G in α's and q's and a quadratic form in the p variable V G with polynomial coefficients in α's and q's.
These polynomials can be computed explicitly:

34)
where the sum over F runs over all forests of the graph, and the indices C and C means any connected component of that forest (including isolated vertices if any).
The variables p C and q C are the natural sums associated to these connected components.
In order to prove this theorem we introduce now the quasi-Grassmann representations of U G and V G of Lemma 2.1.
Let's calculate first U, hence the determinant of Q G . Factoring out powers of i we get: which can be written as sum of a diagonal matrix D, with coefficients D ee = α e and D vv = q v and of an antisymmetric matrix A with elements ev , that is, Q = D + A.
Similarly V which is a minor related to the Q G matrix is given by a Grassmann integral but with sources and canceled out the χ v χ v + ω v ω v term which must vanish by symmetry and the i factors.
Now we can prove directly that these polynomials obey a deletion-contraction rule.

Theorem 3.3 For any semi-regular edge
Moreover we have the terminal form evaluation for G solely made of self-loops attached to isolated vertices.
Proof If G is not a terminal form we can pick up any semi-regular edge e connecting vertices v 1 and v 2 with v 1 = +1, v 2 = −1. We expand For the first term, since we must saturate the χ e and ω e integrations, we must keep the χ e (χ v 1 − χ v 2 ) term in e P v χe ev χv and the similar ω term, hence we get a contribution Performing the trivial triangular change of variables with unit Jacobian: 44) and the same change for the ω variables we see that the effect of the ( term is simply to change the v 1 label into v 2 and to destroy the edge e and the vertex v 1 . This is exactly the contraction rule, so det Q G,e,1 = det Q G/e . The second term det Q G,e,2 with the α e ω e χ e factor is even easier. We must simply put to 0 all terms involving the e label, hence trivially det Q G,e,2 = α e det Q G−e . Remark that during the contraction steps the weight factor That's why we get the new weight q v 1 + q v 2 for the new vertex v 2 which represent the collapse of former vertices v 1 and v 2 .
Note that the source terms in V do not involve χ e and ω e variables. Therefore the argument goes through exactly in the same way for the second polynomials. The only remark to make is that like weights, flag momenta follow contraction moves.
The evaluation on terminal forms is easy. For a graph with only vertices and selfloops the matrix Q G is diagonal, because ev is always 0. Hence U G is the product of the diagonal elements e α e v q v . The second polynomial can be analyzed through the Grassmann representation, but it is simpler to use directly (3.32) and the fact that Q G is diagonal to get (3.41). This completes the proof of Theorem 3.3, hence also of Theorem 3.2.
2 We turn now to the limit of small regulators q v to show how for a connected graph G the ordinary amplitude δ( f p f )A G and the ordinary polynomials U G and V G emerge out of the leading terms of the regularized amplitude B G and the generalized polynomials U G and V G .
When all q's are sent to zero there is no constant term in U G but a constant term in V G . Up to second order in the q variables we have: where the sum over T runs over trees and the sum over T 2 runs over two trees separating the graph into two connected components G 1 and G 2 . Hence we find Up to inessential normalization factors the first term tends to δ(p G ) and the second one tends to , that is if we use the delta distribution to cancel the p 2 G O(1) term and to simplify (p 2 This proves (3.18). The U G and V G polynomials are in fact easy to recover simply from the U G polynomial alone: On the submanifold p G = 0 we further have Proof It is an easy consequence of Theorem 3.2. 2 We can also prove an analog of Proposition 2.1 between V G and U G(vv ) but only on the submanifold p G = 0.

Relation to discrete Schrödinger Operator
As an aside, it is worthwhile to notice that there is a relation with discrete Schrödinger operators on graphs [53]. Recall that given a graph G = (V, E), the discrete Laplacian is defined as follows. We first introduce the 0-forms Ω 0 (G) = R V as the real functions on the set of vertices and 1-forms Ω 0 (G) = R E as functions on the edges. Then, the discrete differential d : Ω 0 (G) → Ω 1 (G) is defined as where we recall the convention that for a self-loop ev = 0 and an arbitrary orientation is chosen on the edges. Next, given strictly positive weights β e associated to the edges, we define d * : Note that d * is precisely the adjoint of d for the scalar product on R E defined by the weights β e and the Euclidean one on R V . Accordingly, the 0-form Laplacian ∆ : Ω 0 (G) → Ω 0 (G) is ∆ = d * d, (3.52) or, in terms of its action on functions ψ ∈ R V , Note that there is exactly one zero mode per connected component, as follows from the equivalence between ∆ψ = 0 and dψ = 0. Finally, the weights q v associated to the vertices 2 define a function V from the vertices to R acting multiplicatively on Ω 0 (G) so that we define the discrete Schrödinger operator (Hamiltonian in the quantum mechanics language) on the graph by Turning back to the parametric representation, if we perform the Gaußian integration over the momenta we are left with with weights β e = 1 αe . In particular, the first Symanzik polynomial with regulators q v is expressed in terms of the determinant of H, with ψ v , ψ v Grassmann variables. By the same token, the ratio appearing in the Feynman amplitude is expressed in terms of its inverse G (Green's function in the quantum mechanics language), where the Green's function can also be expressed using Grassmann integrals. As a byproduct, it turns out that it can also be computed by contraction/deletion.

Categorified Polynomials
We have up to now considered two seemingly unrelated graph polynomials obeying contraction/deletion rules, the multivariate Tutte polynomial Z G (β e , q) and U G (α e , q i ), from which the Symanzik polynomials can be recovered by various truncations. Therefore, it is natural to wonder wether there is a single graph polynomial, obeying contraction/deletion rules too, from which both Z G (β e , q) and U G (α e , q i ) can be recovered. In this subsection for simplicity we shall consider only the first Symanzik polynomial, and the flags considered in this subsection no longer bear external momenta, but an abstract index. Such a polynomial is an invariant of graphs with flags, i.e. labeled half-edges attached to the vertices. In order to make the contraction possible, it is necessary to allow each vertex to have several flags, all carrying distinct labels. The requested polynomial, W G (β e , q I ) depends on edge variables β e as well as on independent variables q I for each non empty subset I of the set of labels of the flags, with the proviso that, for each vertex, the subsets I contain all the flags attached to the vertex or none of them. Thus, for a diagram with V vertices carrying flags there are 2 V − 1 variables q I . For example, for the bubble graph on two vertices with two edges between these vertices and flags 1, 2 attached to one of vertex, and flag 3 to the other one, we have W G (β e , q I ) = (β 1 β 2 + β 1 + β 2 )q 123 + q 12 q 3 . (3.59) Since the variables q I are defined using the flags, the contraction/deletion rule for W G (β e , q I ) requires us to properly define how the flags follow the contraction/deletion rule for any edge of G − e and G/e. Because the vertices and the flags of G − e are left unchanged, the same variables q I appear in G and G − e. For G/e, we restrict the q I to those associated with subsets that contain either all the flags attached to the two vertices merged by the contraction of e, either none of them. This is best formulated using flags: the new vertex simply carries the flags of the two vertices that have been merged. Then, the contraction/deletion identity simply follows from grouping the terms in W G (β e , q I ) that contain β e and those that do not.

Proposition 3.1
The polynomial W G (β e , q I ) obeys the contraction/deletion rule for any edge W G (β e , q I ) = β e W G/e (β e =e , q I | G/e ) + W G−e (β e =e , q I ). (3.60) The multivariate Tutte polynomial is easily recovered by setting q I = q for any I, Z G (β e , q) = W G (β e , q I = q). (3.61) In this case, all the information about the flags is erased and so that the latter may be omitted. To recover U G (α e , q i ), it is convenient to introduce as an intermediate step the polynomial where as before I n are the flags included in the connected component C n of the spanning graph (V, A). By its very definition, Υ G (α e , q i ) is related to W G (β e , q I ) by setting q I = i∈I q i , Then, the polynomial U G (α e , q i ) is obtained from Υ G (α e , q i ) by keeping only the highest degree terms in the α e 's for each term in Cn i∈In q i . Indeed, U G (α e , q i ) is obtained from Υ G (α e , q i ) by truncating its expansion to those subsets A ⊂ E that are spanning forests, i.e. that obey 0 = |A| − V + k(A). Since the number of connected components k(A) is fixed by the global degree in the q i 's, the forests are obtained with |A| minimal, so that the global degree in the α e 's must be maximal. Note that a truncation to the spanning forests may also be performed at the level of the multivariate Tutte polynomial by restricting, at fixed degree in q, to the terms of minimal degree in the β e 's. This yields an expansion over spanning forests [4] (see also [42]). This, as well as the relation to the Symanzik polynomial, is conveniently summarized by the following diagram. where α e = 1/β e .
Alternatively, the polynomial W G (α e , q I ) can be seen as an extension of the polynomial W G (ξ a , y) introduced by Noble and Welsh in [43]. Definition 3.3 For a graph with weights ω v ∈ N * assigned to the vertices, the W polynomial is defined as with a n = v∈Cn ω v the sum of the weights of the vertices in the connected component C n .
This polynomial also obeys the contraction/deletion rule if we add the weights of the two vertices that are merged after the contraction of an edge. Alternatively, weights may be assigned to flags, with the convention that the weight of a vertex is the sum of the weights of the flags attached to it. Then, W (ξ a , y) is naturally extended to diagrams with flags and results from a simple substitution in W G (ξ a , y). with a I = i∈I ω i the sum of the weights of the flags in I.
The polynomial W G (ξ a , y) only encodes the sum of the weights of the flags in each connected component and erases information about their labels. In particular, if we weight each flag by ω i = 1, then the expansion of W only counts the number flags per component whereas that of W G (β e , q I ) keeps track of the associated set of labels. In a more sophisticated language, the latter may be considered as the simplest categorification of the former: integers, understood as finite sets up to isomorphisms, have been replaced by the category of finite sets.

Symanzik Polynomials through the tree matrix theorem in x-space
In this section we provide a sketch of a more standard proof of Theorem 3.1 through the x space representation and the tree matrix theorem. The reason we include it here is for completeness and because we have not been able to find it in the existing literature, in which the same computation is usually performed through the Binet-Cauchy theorem. The V × V matrix Q G (α) analog in this case of (3.29) is defined as Therefore by the tree matrix theorem the determinant of the (V − 1) × (V − 1) matrix Q G (α) defined as its principal minor with the line and column for the root vertex number V deleted is: where the sum is over all trees of G. Since every tree of G has V − 1 edges, ∆ G is clearly a homogenous polynomial in the α −1 e . For α > 0, ∆ is positive. The remaining (V − 1) vectors z may then be integrated over and the result is This formula expresses A G (p) as a function of the invariant scalar product of external momenta p v · p v . The denominator is a homogenous polynomial of degree V −1. This gives an alternative proof of (3.24). The second Symanzik polynomial can also be obtained through this method and the corresponding computation is left to the reader. Of course harmonic regulators can also be included if one wants to avoid the noncanonical choice of a root, but the Pfaffian structure of the phase space representation is lost. Also this x-space method does not generalize easily to noncommutative field theory to which we now turn our attention.

Ribbon graphs
A ribbon graph G = (V, E) is an orientable surface with boundary represented as the union of V closed disks, also called vertices, and E ribbons also called edges, such that: • the disks and the ribbons intersect in disjoint line segments, • each such line segment lies on the boundary of precisely one disk and one ribbon, • every ribbon contains two such line segments.
So one can think of a ribbon graph as consisting of disks (vertices) attached to each other by thin stripes (edges) glued to their boundaries (see . For any such ribbon graph G there is an underlying ordinary graphḠ obtained by collapsing the disks to points and the ribbons to edges. Two ribbon graphs are isomorphic if there is a homeomorphism from one to the other mapping vertices to vertices and edges to edges. A ribbon graph is a graph with a fixed cyclic ordering of the incident half-edges at each of its vertices.
A face of a ribbon graph is a connected component of its boundary as a surface. If we glue a disk along the boundary of each face we obtain a closed Riemann surface whose genus is also called the genus of the graph. The ribbon graph is called planar if that Riemann surface has genus zero.
Generalized ribbon graphs that can also incorporate Moebius strips and correspond to nonorientable surface can be defined but will not be considered in this paper.
There is a duality on ribbon graphs which preserves the genus but exchanges faces and vertices, keeping the number of edges fixed. It simply considers the disks glued along faces as the vertices of a dual graph and changes the ends of each ribbon into borders of the dual ribbon.
Extended categories of ribbon graphs with flags can be defined. Flags can be represented as ribbons bordered by dotted lines to distinguish them from ordinary edges (see . Beware that the cyclic ordering of flags and half-edges at each vertex is very important and must be respected under isomorphisms. The genus of an extended graph is defined as the genus of the graph obtained by removing the flags and closing the corresponding segments on their vertices. The number of broken faces is the number of faces which do contain at least one flag. It is an important notion in noncommutative field theory.
We define for any ribbon graph • V (G) as the number of vertices; • E(G), the number of edges, • k(G), the number of connected components, • n(G) = E(G) − r(G), the nullity of G, • bc(G) = F (G), the number of components of the boundary of G 3 , • g(G) = k − (V − E + bc)/2 is the genus of the graph, • f (G) the number of flags of the graph.
A graph with a single vertex hence with V = 1 is called a rosette.
A subgraph H of a ribbon graph G is a subset of the edges of G. The Bollobás-Riordan polynomial, which is a generalization of Tutte polynomial, is a algebraic polynomial that is used to incorporate new topological information specific to ribbon graphs, such as the genus and the number of "broken" or "external" faces. It is a polynomial invariant of the ribbon graph.    The relation to the Tutte polynomial for the underlying graphḠ is

Bollobás-Riordan Polynomial
When H is a spanning graph of G, we have k(H) − k(G)=r(G) − r(H). So we can rewrite the R polynomial as: so that M (H) depends only on H but not on G.

Deletion/contraction
The deletion and contraction of edges in a ribbon graph are defined quite naturally: the deletion removes the edge and closes the two scars at its end; the contraction of a semi-regular edge creates a new disk out of the two disks at both ends of the ribbon with a new boundary which is the union of the boundaries of the two disks and of the ribbon (see Figure 10). An interesting property is that deletion and contraction of edges are exchanged in the dual graph. The deletion of a self-loop is standard. However the natural contraction of a self-loop creates a surface with a new border. Iterating, we may get surfaces of arbitrary genus with an arbitrary number of disks removed, a category also called disk-punctured surfaces. The ribbons can now join any puncture to any other. For instance the contraction of the self-loop on the graph G 1 of Figure 7 leads to a cylinder ie to a single vertex which is a sphere with two disks removed. The contraction of the two self-loops in graph G 2 of Figure 8 corresponds to the cylinder with a ribbon gluing the two ends, hence to a torus. Deletion and contraction defined in this extended category of graphs can be iterated until the graph has no longer any edge, ie is a collection of disk-punctured Riemann surfaces. These punctured Riemann surfaces are very natural objects both in the context of string theory and in NCQFT. However we do not consider them in this paper.
In this paper we remain in the category of ordinary ribbon graphs with disk-like vertices. The contraction/deletion of semi-regular edges leads to rosettes as terminal forms. To treat them we introduce the notion of double contraction on nice crossings.

Nice crossings were introduced in [20]:
Definition 4.2 A nice crossing pair of edges in a rosette is a pair of crossing edges e 1 and e 2 which are adjacent on the cycle of the rosette. Adjacency means that one end of e 1 is consecutive with an end of e 2 (see Figure 9).
It is proved in [20] that any rosette R of genus g > 0 contains at least one nice crossing.
The double contraction of such a nice crossing pair consists in deleting e 1 and e 2 and interchanging the half-edges encompassed by e 1 with the ones encompassed by e 2 , see Figure 9. This double contraction was defined in [20] under the name of "3rd Filk move". It decreases the genus by one and the number of edges by 2.
In the next section iterating this double contraction until we reach planarity allows us to compute the U Symanzik polynomial by remaining in the category of ordinary ribbon graphs.
(4.4) Figure 9: When deleting the two edges of a nice pair crossing on some contracted vertex, one also needs to interchange the half-edges encompassed by the first edges with those encompassed by the second one. Beware that the horizontal line in this picture is a part of the rosette cycle. for every ribbon graph G and any regular edge e of G and for every bridge of G.
Therefore the R polynomial satisfy contraction-deletion relations as the Tutte polynomial. However to complete its definition we also need to define the R polynomial for single vertex graphs, namely the rosettes, which can be read off from (4.3). For such a rosette R, k(R) = V (R) = k(H) = V (H) = 1, so that the R polynomial does not depend on x and (4.6) For z = 1 we recover R R (y − 1, 1) = y E(R) .

The multivariate Bollobás-Riordan polynomial
Like in the case of Tutte polynomial, we can generalize the Bollobás-Riordan polynomial to a multivariate case. As before,we associate to each edge e a variable β e . It obeys again a deletion/contraction relation similar to Theorem (4.1) for any semi-regular edge.

Motivation
Noncommutative quantum field theory, hereafter called NCQFT, has a long story. Schrödinger, Heisenberg [54] and Yang [55] tried to extend the noncommutativity of phase space to ordinary space. Building on their ideas Snyder [56] formulated quantum field theory on such noncommutative space in the hope that it might behave better than ordinary QFT in the ultraviolet regime.
Right from the start another motivation to study noncommutative quantum field theory came from the study of particles in strong magnetic fields. It was early recognized that non zero commutators occur for the coordinates of the centers of motion of such quantum particles, so that noncommutative geometry of the Moyal type should be the proper setting for many body quantum physics in strong external field. This includes in condensed matter the quantum Hall effect (see the contribution of Polychronakos in [57]), or other strong field situations.
An other motivation comes from particle physics. After initial work by Dubois-Violette, Kerner and Madore, Connes, Lott, Chamseddine and others have forcefully advocated that the classical Lagrangian of the current standard model arises naturally on a simple noncommutative geometry. For a review see Alain Connes's contribution in [57] and references therein.
Still an other motivation came from the search of new regularizations of non-Abelian gauge theories that may throw light on their difficult mathematical structure. After 't Hooft proposed the large N limit of matrix theory, in which planar graphs dominate, as relevant to the subject [58], the Eguchi-Kawai model was an important attempt for an explicit solution. These ideas have been revived in connection with the ultraviolet behavior of NCQFT on the Moyal-Weyl geometry, which also leads to the domination of planar graphs. Seiberg and Witten proposed in [59] a mapping between ordinary and noncommutative gauge fields which does not preserve the gauge groups but preserve the gauge equivalent classes.
The interest for non commutative geometry also stems from string theory. Open string field theory may be recast as a problem of noncommutative multiplication of string states [60]. It was realized in the late 90's that NCQFT is an effective theory of strings [61]. Roughly this is because in addition to the symmetric tensor g µν the spectrum of the closed string also contains an antisymmetric tensor B µν . There is no reason for this antisymmetric tensor not to freeze at some lower scale into a classical field, inducing an effective non commutative geometry of the Moyal type. There might therefore be some intermediate regime between QFT and string theory where NCQFT is the relevant formalism. The ribbon graphs of NCQFT may be interpreted either as "thicker particle world-lines" or as "simplified open strings world-sheets" in which only the ends of strings appear but not yet their internal oscillations.

Scalar models on the Moyal space
The noncommutative Moyal space is defined in even dimension d by where Θ is an antisymmetric d/2 by d/2 block-diagonal matrix with blocks: and we have denoted by the Moyal-Weyl product Note that in the limit θ → 0 this product becomes the ordinary commutative product of functions.

The "naive" model
The simplest field theory on this space consists in replacing the ordinary commutative local product of fields by the Moyal-Weyl product In momentum space the action (5.4) writes where V (φ, θ) is the corresponding potential. An important consequence of the use of the non-local product is that the interaction part no longer preserves the invariance under permutation of external fields. This invariance is restricted to cyclic permutations. Furthermore, there exists a basis -the matrix base -of the Moyal algebra where the Moyal-Weyl product takes the form of an ordinary (infinite) matrix product. For these reasons the associated Feynman graphs are ribbon graphs, that is propagators should be drawn as ribbons.
In [62] several contractions on such a Feynman graph were defined. In particular the "first Filk move" is the contraction introduced in subsection 4.3. Repeating this operation for the V − 1 edges of a spanning tree, one obtains a rosette (see Figure  11).
Note that the number of faces or the genus of the graph does not change under contraction. There is no crossing between edges for a planar rosette. The example of Figure 11 corresponds thus to a non-planar graph (one has crossings between the edges k 1 and k 2 ). This pair is called a nice crossing pair.  Figure 11: An example of a rosette with two flags. The crossings of edges k 1 and k 2 indicate the non trivial genus (here g = 1).
The notions expressed in the previous section (namely the Green and Schwinger functions or the perturbation theory concepts) remain the same as in QFT. Usual Feynman graphs are simply replaced by ribbon Feynman graphs.
Recall that this "naive model" (5.4) is not renormalizable in d = 4. This is due to a new type of non-local divergence at the level of the 2−point function -the UV/IR mixing [19].

A translation-invariant renormalizable scalar model
In order to restore renormalizability at d = 4, the propagator can be modified in the following way [63] where a is some dimensionless parameter which is taken in the interval 0 < a ≤ 1 4 θ 2 m 4 . The corresponding propagator writes in momentum space (5.7) In [63], this model was proved to be renormalizable at any order in perturbation theory. Furthermore, its renormalization group flows [64] were calculated; a mechanism for taking the commutative limit has been proposed [65] (for a review on all these developments, see [66]).

The NC Parametric representation
In this subsection we present the implementation of the parametric representations for the noncommutative scalar models introduced in the previous subsection.
To keep track of the cyclic ordering at the vertex it is convenient to detail the incidence matrix ε ev into a more precise incidence tensor ε v ei where i = 1, ..., 4 indexes the four corners of the Moyal vertex. As before it is 1 if the edge e starts at corner i of vertex v, -1 if it exits at that corner, and 0 otherwise.
To implement the parametric representation we follow subsection 3.3. The propagator remains the same as in QFT, but the contribution of a vertex v now corresponds to a Moyal kernel. In momentum space it writes using again summation over repeated indices By k i Θk j we denote k µ i Θ µν k ν j . The δ−function appearing in the vertex contribution (5.8) is nothing but the usual momentum conservation. It can be written as an integral over a new variablex v , called hyperposition. One associates such a variable to any Moyal vertex, even though this vertex is non-local: where σ is a d/2 by d/2 block-diagonal matrix with blocks: Note that to pass from the first to the second line in (5.9), the change of variables ix v =x v σ has Jacobian 1.

The "naive" model
Putting now together the contributions of all the internal momenta and vertices, one has the following parametric representation: where we have denoted by K T G some inessential normalization constant. Furhermore note that in the integrand above we have denoted, to simplify the notations, by k e or k e momenta which can be both internal or external.

The translation-invariant model
The parametric representation of the model (5.6) was analyzed in [67]. This representation is intimately connected to the one of the model (5.4) (see the previous subsubsection) for the following reason. One can rewrite the propagator (5.7) as (5.14) Thus, the propagator (5.7) writes where −m 2 1 and −m 2 2 are the roots of the denominator of the second term in the LHS (considered as a second order equation in p 2 , namely −θ 2 m 2 ± √ θ 4 m 4 −4θ 2 a 2θ 2 < 0. Note that the form (5.15) allows us already to write an integral representation of the propagator C(p, m, θ). Nevertheless, for the second term one would need a triple integration over some set of Schwinger parameters: Instead of that one can use the following formula: ). (5.15) This allows to write the propagator (5.15) as ). (5.16) This form finally allows to write down the following integral representation: Let us also remark that the noncommutative propagator C GM RT is bounded by the "usual" commutative propagator C(p, m) C GM RT ≤ C(p, m). (5.17) Using now (5.15), the parametric representation of the model (5.6) is thus a sum of 2 E terms coming from the development of the E internal propagators. Each of these terms has the same form of the one of polynomials in the previous subsection. The only differences comes from • the proper substitution of the set of Schwinger α parameters • the mass part.

Deletion/contraction for the NC Symanzik polynomials
In this subsection we give some results relating the Bollobás-Riordan polynomial and the parametric representations of the noncommutative scalar models introduced here.

The "naive" model
As in the commutative case, we have to perform a Gaußian integral in a d(E + V − 1) dimensional space. Consider a ribbon graph G with a rootv. We introduce the condensed notations analog to (3.27)-(3.29) Q is an d(E + V − 1)-dimensional square matrix. We have denoted by p e the external momenta and byxv the hyperposition associated to the root vertexv. The matrix R is a d(N + 1) × d(E + V − 1) dimensional matrix and M is a d(N + 1) dimensional square matrix representing the Moyal couplings between the external momenta and the root vertex. Gaußian integration gives, up to inessential constants: where P is a line matrix regrouping the external momenta (and the hyperposition associated to the root vertex). The determinant of the matrix Q defines therefore the first Symanzik NC-polynomial U and the product of the matrices R and inverse of Q defines the quotient of the second Symanzik polynomial V by U where the star recalls the Moyal product used to define this NCQFT.
Let us calculate first the determinant of Q. One has where D is a diagonal matrix with coefficients D ee = α e , for e = 1, . . . , E and D vv = 0 for the rest, v = 1, . . . , V − 1. A is an antisymmetric matrix. In [20] it was noted that, for such a matrix det Q = det(D + A) d . (5.15) This implies, as in the commutative case, that Factoring out powers of i one has The difference with the commutative case comes from the non-trivial antisymmetric coupling between the E edges variables. It corresponds to an E dimensional square matrix F with matrix elements Note that the last term above represents the difference with the commutative case.
We have the exact analog of Theorem 3.3 to prove a deletion-contraction rule. leading to two contributions, which we denote respectively by det Q G,e,1 and det Q G,e,2 . For the first term, since one must saturate the χ e and ω e integrations, one has to keep the χ e (χ v 1 − χ v 2 + ẽ f eẽ χẽ) term and the similar ω term. Note that the sum is done on all the edgesẽ hooking to any of the vertices v 1 and v 2 and with whom the edge e has no trivial Moyal oscillation factor. One has As in the commutative case, we now perform the trivial triangular change of variables with unit Jacobian: 17) and the same change for the ω variables. What happens now is analogous to the commutative case, with the difference that the last term in the definition ofχ v 1 will lead to the reconstruction of the Moyal oscillation factors of the edges hooking to v 1 with the edges hooking to v 2 . This completes the ribbon contraction, thus det Q G,e,1 = det Q G/e . The second term det Q G,e,2 with the α e ω e χ e factor is even easier. We must simply put to 0 all terms involving the e label, hence trivially det Q G,e,2 = α e det Q G−e . 2 We need now to compute U on terminal forms after contracting/deleting all semi-regular edges, that is compute U on a rosette graph R. This is done by using the double contraction introduced in the previous section.
Consider a nice crossing of R between two edges e 1 and e 2 with parameters α 1 and α 2 . It leads to a contribution where we recall that the contracted rosette R/e 1 e 2 is obtained by deleting e 1 and e 2 from R and interchanging the half-edges encompassed by e 1 with the ones encompassed by e 2 , see Figure 9. The procedure can be iterated on R/e 1 e 2 until after g(R) double contractions a planar rosette with 2E(R) − 2g(R) is reached, for which F = 0 and for which the terminal form is e α e as in the commutative case. Remark that the main difference with the commutative case is the inclusion of the θ 2 term in the terminal form evaluation (5.18). This type of genus-term has no analog in the commutative case.
Example 5.1 Consider the graph of Figure 12. Its first Symanzik polynomial is [67] Choosing α 3 as a regular edge leads to a contracted graph where the pair of edges α 1 and α 2 realizes a nice crossing. We thus have a contribution to the first polynomial Figure 12: An example of a non-planar graph, g = 1.
The deleted part then follows as in the commutative case leading to a contribution Let us now give the following definition: Definition 5.1 A -tree of a connected graph G is a subset of edges with one boundary.
This definition allows to write a -tree in some graph of genus g as an ordinary tree plus at most g pairs of "genus edges" (where by "genus edges" we understand pairs of edges which make a recursive succession of nice crossings under double contractions on the rosette obtained after contracting the edges of the tree in the graph). In [19], the following general expression for the first polynomial U of the "naive" noncommutative model was given where we have denoted by the number of loops of G. Note that the factor 2 above is the one which matches our conventions.
Let us now give a proof of the formula (5.22). Consider the following lemma: where AK is the matrix obtained from A by deleting the lines and columns with indices in K.
The particular form (5.14) of the matrix Q allows thus to use this Lemma to calculate its determinant (i.e. the polynomial U ). Factoring out θ 2 on the first E lines and then 2 θ on the last V − 1 columns, one has Note that the set K on which one sums up corresponds to a set of edges of the graph; this comes from the fact that the last V − 1 entries on the diagonal of the matrix A are equal to 0. In [20] (see Lemma III.4) it is proven, using a non trivial triangular change of Grassmanian variables that a determinant of type AK is not vanishing if and only if it corresponds to a graph with only one face. This means that the complement of the subset of edges K must be a −tree,K = T * . Furthermore, one has T α e = e / ∈T α e . (5.26)

The translation-invariant model
The relation of the parametric representation of the model (5.6) to the Bollobás-Riordan polynomials follows the one of the "naive" model (5.4) presented above. This is an immediate consequence of the intimate relationship between the parametric representation of these two noncommutative models, a relationship explained in the previous subsection.

The second polynomial for NCQFT
In this section we prove the form of the second polynomial for the model (5.4) (both its real and imaginary part, as we will see in the sequel). We then relate this second polynomial to the Bollobás-Riordan polynomial. From (5.13) it follows directly that where we have left aside the matrix M coupling the external momenta to themselves. Note that the matrix R couples the external momenta (and the hyperposition associated to the root vertex) to the internal momenta and the remaining V − 1 hyperpositions. This coupling is done in an analogous way to the coupling of the internal momenta with the respective variables.
We can thus state that the V polynomial is given, as in the commutative case, by the inverse Q −1 of the matrix Q giving the U polynomial. The particular form (5.14) of the matrix Q leads to Thus, the polynomial V has both a real V R and an imaginary part V I . In the case of the commutative theories, the imaginary part above disappears. This is a consequence of the fact that the matrix F , coupling through the Moyal oscillations the internal momenta, vanishes for θ = 0.
Let the following definitions.
Definition 5.2 A two -tree is a subset of edges with two boundaries.
We now prove a general form for both the real and the imaginary part of the polynomial V , noted X and Y .
Hence the subset K is the complement of a -tree plus an edge (just like in the commutative case). Adding an extra edge to a -tree represents an increase of the number of boundaries by one unit. Hence, the subset of edges K above is the complement of some 2 −tree T 2K = T 2 . Let us now investigate the square root of the momenta combination entering (5.30). Note that the matrix element R e 1 τ is not vanishing only for external momentum p e 1 which has a Moyal oscillation with the internal momenta associated to the edge τ . It is this edge τ which actually creates the extra boundary. Thus the sum on the external momenta in (5.30) is nothing but the sum of the momenta entering one of the two boundaries. By a direct verification, one can explicitly check the signs of the respective momenta in (5.30), which concludes the proof. 2 Example 5.3 For the graph of Figure 12, the second polynomial is Let us now investigate the form of the imaginary part Y . One has the following theorem: The imaginary part of the second Symanzik polynomial writes where ψ(p) is the phase obtained by following the momenta entering the face of the −tree T as if it was a Moyal vertex.
Proof. The proof follows closely the one of Theorem 5.2. Nevertheless, the equivalent of (5.30) is now (see again [20]) where d i are the elements on the diagonal of the matrix Q. Since we look this time for sets such that Pf(BK) is non-vanishing, this implies as above that K is the complement of some -tree T . Furthermore one needs to consider the two extra edges τ and τ . It is possible from the initial −tree above to erase these two more edges such that the Pfaffian Pf BKττ is non-vanishing. Indeed, if the -tree is a tree, by erasing two more edges of it we obtain a graph with 3 disconnected components, each of it with a single boundary; the corresponding Pfaffian will be non-vanishing. Summing up on all these possibilities leads to the Moyal oscillations of the external momenta (the one which disappears when truncating the graph). If the −tree is formed by a tree and some pair of genus edges we can always delete further the pair of genus edges and remain with the regular tree. Obviously the corresponding Pfaffian is again non-vanishing (since it corresponds to a graph with only one boundary). 2 Note that the form of the real part and of the imaginary one of the polynomial V are qualitatively different. Indeed, the real part contains some square of a sum of incoming external momenta, while the imaginary one contains a phase involving the external momenta.
Let us end this section by stating that the second noncommutative Symanzik polynomial also obeys the deletion-contraction rule. The proof is exactly like in the commutative case, a straightforward rereading of Theorem 5.1.

Relation to multivariate Bollobás-Riordan polynomials
In the previous subsections, we have identified the first Symanzik polynomial of a connected graph in a scalar NCQFT as the first order in w of the multivariate Bollobás-Riordan polynomial, Recall that the multivariate Bollobás-Riordan polynomial (see [68]) is a generalization of the multivariate Tutte polynomial to orientable ribbon graphs defined by the In order to deal with the second Symanzik polynomial in the noncommutative case, we now introduce an extension of Z G (β, q, w) for ribbon graphs with flags at q = 1. In the case of ribbon graphs, the flags are attached to the vertices and the cyclic order of flags and half-edges at each vertex matters. For each cyclically oriented subset I of the set of labels of the flags, we introduce an independent variable w I . Cyclically ordered subsets I are defined as sequences of different labels up to a cyclic permutation. Then, each boundary of a graph with the orientation induced by the graph, defines a cyclically ordered subset of the set of labels of the flags, by listing the flags in the order they appear on the boundary. Accordingly, a variable w I is attached to each boundary. We recover Z G (β e , 1, w) by setting w I = w and α e = 1, but the information pertaining to q is lost except for planar graphs. Indeed, in this case the genus of any subgraph is still 0 so that |V | − |A| + b(A) = 2k(A) and thus Z G (β e , q, w) = q |V |/2 Z G (q − 1 2 β e , q 1 2 w). The polynomial Ξ G (α e , β e , w I ) obeys the contraction/deletion rules for any semiregular edges (i.e. all types of edges except self-loops). The structure of the flags of G − e is left unchanged, but less variables w I enter the polynomial since the number of boundaries decreases. For G/e, the flags attached to the vertex resulting from the contraction are merged respecting the cyclic order of flags and half-edges attached to the boundary of the subgraph made of the contracted edge only.
Proposition 5.1 The polynomial Ξ G (α e , β e , w I ) obeys the contraction/deletion rule for a semi-regular edge, Ξ G (α e , β e , w I ) = α e Ξ G−e (α e =e , β e =e , w I ) + β e Ξ G/e (α e =e , β e =e , w I ). (5.34) This follows from gathering in the expansion of Ξ G (α e , β e , w I ) the terms that contain e and those that do not. The contraction/deletion rule may be extended to any edge provided we introduce vertices that are surfaces with boundaries as in [68].
The second interesting property of Ξ G (α e , β e , w I ) lies in its invariance under duality. Recall that for a connected ribbon graph G with flags, its dual G * is defined by taking as vertices the boundaries of G, with flags and half-edges attached in the cyclic order following the orientation of the boundary induced by that of G.
Proposition 5.2 For a connected graph G with dual G * , Ξ G (α e , β e , w I ) = Ξ G * (β e , α e , w I ). (5.34) Proof: First, recall that there is a natural bijection between the edges of G and those of G * . Thus, to a subset A of edges of G we associate a subset A * of edges of G * which is the image under the previous bijection of the complementary E − A. Then, the term corresponding to A in Ξ G (α e , β e , w I ) equals that corresponding to A * in Ξ G * (β e , α e , w I ). The only non trivial part in the last statement is the equality of the boundary terms in G and G * , which is best understood by embedding G in a surface Σ. Then, the spanning graph (V * , A * ), viewed as discs joined by ribbons, is homeomorphic to Σ − (V, A), with the orientation reversed. Accordingly, they have the same boundary.
2 This relation may also be extended to non connected graphs at the price of introducing again vertices that are surfaces with holes. For example, the dual of a disjoint union of n vertices is the vertex made of a sphere with n holes. For a regular edge, the duality exchanges contraction (resp. deletion) in G with deletion (resp. contraction) in G * . In the case of the deletion of a bridge in G, we have to contract a self-loop in G * , thus leading to vertices that are surfaces with holes. Note that this implies a duality for the multivariate Bollobás-Riordan polynomial only at the special point q = 1, in agreement with the fact that the duality for the Bollobás-Riordan polynomial only holds when its arguments lies on a hypersurface [69].
Finally, let us come to the relation with the second Symanzik polynomial in NCQFT. For a given connected graph with momenta p i such that i p i = 0 attached to the flags, we decompose the latter polynomial into real and imaginary part, V G (α e , θ, p i ) = X G (α e , θ, p i ) + i Y G (α e , θ, p i ). (5.34) Consider real variables w i and define w I = i w i for any cyclically oriented subset of flags, Then, expand (θ/2) |E|−|V | Ξ G (2α e /θ, θw I /2) to the first two orders at w i = 0, (θ/2) |E|−|V | Ξ G (2α e /θ, θw (5.34) The first order term reproduces the first Symanzik polynomial U G (α e , θ) = A, (5.34) whereas the second order terms yields the real part of the second Symanzik polynomial, X G (α e , θ, p i ) = − 1 To obtain the imaginary part, consider the variables if I contain all the flags and w I = 0 otherwise. The previous definition involves a choice of a total order on I compatible with its cyclic structure, but momentum conservation i p i = 0 implies that w I does not depend on this choice. Then, Y G (α e , θ, p i ) = (θ/2) |E|−|V | Ξ G (2α e /θ, w I ). (5.34) As a consequence of their expressions in terms of Ξ G (α e , β e , w I ), the noncommutative Symanzik polynomials obey contraction/deletion rules for regular edges and duality relations. For example, the duality for the first Symanzik polynomial reads (θ/2) |V | U G (α e , θ) = (θ/2) |V * | e∈E 2α e θ U G * θ 2 /α e , θ . (5.34) Beware that G * is the dual graph whereas the star on polynomials such as U and V refer to the Moyal product. Analogous relations, though slightly more cumbersome, can be written for the second Symanzik polynomial. Still an other way to categorify and regularize in the infrared is to introduce harmonic potentials on the edges rather than the vertices, leading to propagators based on the Mehler rather than the heat kernel. This is the so-called vulcanization. An extensive study of the corresponding commutative and noncommutative polynomials is under way as a companion paper [70].