Regular colored graphs of positive degree

by R. Gurau and G. Schaeffer. Ann. Inst. Henri Poincaré Comb. Phys. Interact., 3(3): 257-320, 2016. doi, arXiv: 1307.5279 [math.CO].

This article deals with the exact enumeration of rooted bipartite \((D+1)\)-regular properly edge-coloured graphs of fixed degree \(\delta\) (hereafter rooted \((D+1)\)-coloured graphs), in dimension \(D\geqslant 3\).


Disclaimer: in what follows I will not try to be very precise. My aim here is to give a brief (and partial) overview of the article of Gurau and Schaeffer and explain some of their main arguments.


Recall that

  • coloured graphs are dual to coloured triangulations of piecewise linear orientable \(D\)-dimensional pseudo-manifolds,
  • the degree is a combinatorial (and non topological) higher dimensional generalisation of the genus.

The authors determine the generating function of rooted \((D+1)\)-coloured graphs. To this aim, they first partition such coloured graphs into equivalence classes labelled by melon-free coloured graphs called cores. The degree is indeed the same in each class (inserting or removing melons in a coloured graphs does not change its degree). But each such class is still made of an infinite number of graphs. Thus, the authors proceed further and show that the degree of coloured graphs is independent of the length of some chains of \((D-1)\)-dipoles. They identify six different types of chains (four broken ones and two unbroken ones) and further decompose each melon-free class into finer classes labelled by (reduced) schemes i.e. melon free graphs the chains of which have been replaced by so-called chain-vertices. Knowing the generating function of melons and after having computed the ones of the six different chains, there remains to prove (and this is the hardest part of the article) that the number of schemes of degree \(\delta\) is finite.

The main result of this article is then the following:

For any fixed dimension \(D\geqslant 3\) and degree \(\delta\geqslant 0\), there exist a finite set \(\widetilde{\mathcal S}_{\delta}^{0}\) of reduced schemes of degree \(\delta\) and root edge of colour \(0\), and triples \((P_{\widetilde S}(u),U_{\widetilde S},B_{\widetilde S})_{\widetilde S\in\widetilde{\mathcal S}_{\delta}^{0}}\) consisting in a monomial and two integer parameters associated to the schemes such that the generating function of coloured graphs of degree \(\delta\) rooted at an edge of color \(0\) with respect to the number of black vertices is \[H_\delta^0(z)=T(z)\sum_{\widetilde S\in\widetilde{\mathcal S}_{\delta}^{0}}\left[\frac{P_{\widetilde S}(u)}{(1-u^2)^{U_{\widetilde S}+B_{\widetilde S}}(1-D^2u^2)^{B_{\widetilde S}}}\right]_{u=zT(z)^{D+1}},\] where \(T(z)\) is the unique power series solution of the equation \[T(z)=1+zT(z)^{D+1}.\]

Let us now give some details about the proof of the following:

The number of reduced schemes with a fixed degree is finite.</div> <div class="idproof"> It goes in two steps. The authors first bound the number of chain-vertices, \((D-1)\)-, and for \(D\geqslant 4\), \((D-2)\)-dipoles in a reduced scheme of degree \(\delta\) by \(19\delta\). Then, they observe that “the minimal realization of any chain-vertex consists of at most four \((D-1)\)-dipoles, so that there is an injective map from the reduced schemes of degree \(\delta\) into melon free colored graphs of degree \(\delta\) with at most \(76\delta\) \((D-1)\)- and \((D-2)\)-dipoles.” And they conclude by proving that the number of coloured graphs with fixed degree and fixed numbers of \((D-1)\)- and, for \(D\geqslant 4\), \((D-2)\)-dipoles is finite.

As the proof of this theorem is by far the lengthiest part of the article, let us give some more details about it.

The number of chain-vertices, \((D-1)\)-, and for \(D\geqslant 4\), \((D-2)\)-dipoles in a reduced scheme of degree \(\delta\) is bounded by \(19\delta\).

Let \(\widetilde G\) be a reduced scheme of degree \(\delta\). Gurau and Schaeffer recursively delete its chain-vertices, \((D-1)\)- and, if \(D\geqslant 4\), \((D-2)\)-dipoles. Note that such deletions may increase the number of connected components. The degree of a disconnected graph is defined a the sum of the degrees of its components. Now, if the deletion of a chain-vertex or a dipole would strictly decrease the degree, the proof would be easy. But it is not the case. The authors provide then a comprehensive study of the behaviour of the degree under a \((D-q)\)-dipole deletion. They call completly separating a dipole the deletion of which separates the graph into \(q+1\) connected components and prove that

  • under the deletion of a completely separating dipole, the degree is distributed in the connected components (in other words it stays the same)
  • under the deletion of a non completely (or not) separating \((D-1)\)- or \((D-2)\)-dipole, the degree decreases by at least \(D-2\).

<div class="proofinterm">Deletion of chain-vertices is similar to the case of \((D-1)\)-dipoles. So Gurau and Schaeffer first delete recursively all not completely separating elements. The scheme \(\widetilde G’\) obtained this way is generally not connected and contains only completely separating dipoles and chain-vertices. As the deletion of those does not decrease the degree, it is not clear a priori that there is a finite number of them. Nevertheless completely separating dipoles have a simple recursive structure (in terms of \(2\)-point function insertions for QFT oriented minds) which endows \(\widetilde G’\) with the structure of a forest \(\mathcal F\). If \(\widetilde G”\) is the graph obtained after deletion of all chain-vertices, \((D-1)\)- and \((D-2)\)-dipoles of \(\widetilde G'\), then the vertices of \(\mathcal F\) correspond to the connected components of \(\widetilde G”\) (roughly speaking because there is in fact a subtlety due to the \((D-2)\)-dipoles) and its edges correspond to pairs of edges created by the deletions. We need to bound the number \(\mathcal D\) of chain-vertices, \((D-1)\)- and \((D-2)\)-dipoles of \(\widetilde G”\). As the deletion of a chain-vertex or \((D-1)\)-dipole (resp. \((D-2)\)-dipole) creates two (resp. six) new edges, \(\mathcal D\) is bounded above by the number \(e({\mathcal F})\) of edges of \(\mathcal F\). \(e({\mathcal F})\) is itself bounded by the number of vertices of \(\mathcal F\). There remains to bound this number of vertices. They are of different kinds:</div>

  • There are vertices which correspond to components of \(\widetilde G”\) of positive degree. Let us call them positive vertices.
  • There are degree zero (or melonic) vertices which are adjacent to an edge created by the deletion of a \((D-2)\)-dipole. We call them type 2 vertices.
  • There are melonic vertices of valency at least three in \(\mathcal F\). They are of type 3.

<div class="idproofend">Each vertex is of exactly one of these kinds1. The number of positive vertices is clearly bounded by \(\delta\). Then, type 3 vertices cannot be too numerous because each new vertex of this type increases the number of edges by at least 3/2 but the number of edges is itself bounded by the number of type 3 vertices (all other numbers of vertices being kept fixed). If \({\mathcal D}^{(D-2)}\) is the number of \((D-2)\)-dipoles of \(\widetilde G’\), the number of type 2 vertices is bounded above by \(3{\mathcal D}^{(D-2)}\) (the deletion of a \((D-2)\)-dipole can create at most 3 such vertices). But \({\mathcal D}^{(D-2)}\) is also the number of trivalent vertices of \(\mathcal F\) which is bounded above by its number of univalent vertices minus 2 (\({\mathcal D}^{(D-2)}\) is bounded above by the maximal number of trivalent vertices in a forest of binary trees, i.e. by the number of trivalent vertices in a binary tree). Finally univalent vertices of \(\mathcal F\) are essentially positive2.</div>

For \(D=3\), the number of melon free colored graphs with fixed degree and a fixed number of 2-dipoles is finite. For \(D=4\), the number of melon free colored graphs with fixed degree and fixed numbers of \((D-1)\)-dipoles and \((D-2)\)-dipoles is finite.

<div class="idproofstart">The graph considered here having bounded degree, it is enough to prove that they have a finite number of vertices. By a double counting argument and from the definition of the degree of a coloured graph, one gets \begin{equation*} -2F_1+\sum_{p\geqslant 2}[(D-1)p-D-1]F_p=(D+1)\delta-D(D+1) \end{equation*} </div> <div class="idproofend">where \(F_p\) is the number of faces of length \(2p\). The difficulties in \(D=3\) or higher are different. For \(D=3\), fixing the number of \((D-1)\)-dipoles amounts to fixing the number of faces of length 2 i.e. \(F_1\) is fixed. But in the previous equation only the coefficients of \(F_p\) for \(p\geqslant 3\) are positive. Hence there could be proliferation of faces of length 4 and thus proliferation of vertices adjacent to such faces. This is in fact not the case as is proven by Gurau and Schaeffer with a nice argument (see p. 297 of the published article). On the other hand, for \(D\geqslant 4\), all coefficients of \(F_p\) for \(p\geqslant 2\) are positive but this time there can be faces of length 2 which do not belong to \((D-1)\)- and \((D-2)\)-dipoles. Said differently, the number of such dipoles being fixed, \(F_1\) is not fixed but still depends on the number of vertices of the graph. The rest of the proof consists in proving that the number of vertices cannot nevertheless be too large.</div>

 

1 This is one place where I am not telling the full story but the main arguments are given.

2 Another not totally true statement.

Leave a comment

All comments are reviewed before being displayed.


Name (required):

E-mail (required, will not be published):

Website: