Asymptotic expansion of the multi-orientable random tensor model

Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs, or 3D maps, can be classified with respect to a particular integer or half-integer, the degree of the respective graph. In this paper we analyze the general term of the asymptotic expansion in N, the size of the tensor, of a particular random tensor model, the multi-orientable tensor model. We perform their enumeration and we establish which are the dominant configurations of a given degree.

Boltzmann Samplers, Polya Theory, and Cycle Pointing

We introduce a general method to count unlabeled combinatorial structures and to efficiently generate them at random. The approach is based on pointing unlabeled structures in an unbiased way that a structure of size n gives rise to n pointed structures. We extend Polya theory to the corresponding pointing operator, and present a random sampling framework based on both the principles of Boltzmann sampling and on Polya operators. All previously known unlabeled construction principles for Boltzmann samplers are special cases of our new results. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and nonplane unrooted trees, and tree-like structures in general, but also to families of graphs (such as cacti graphs and outerplanar graphs) and families of planar maps.

Dissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling

We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees, with interesting consequences for enumeration, mesh compression and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best known uniform random sampler for labelled planar graphs [{bf Fusy, Analysis of Algorithms 2005}]. It also provides an encoding for the set $mathcal{P}(n)$ of $n$-edge 3-connected planar graphs that matches the entropy bound $frac1nlog_2|mathcal{P}(n)|=2+o(1)$ bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the {optimal parametric rate} $frac1nlog_2|mathcal{P}(n,i,j)|$ bpe for graphs of $mathcal{P}(n)$ with $i$ vertices and $j$ faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated to the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is for instance a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs [bf Bonichon et al., Graph Drawing 2005].