Marie Albenque

We prove that the combinatorial optimization problem of determining the hull-number of a partial cube is NP-complete. This makes partial cubes the minimal graph class for which NP-completeness of this problem is known and improves some earlier results in the literature. On the other hand we provide a polynomial time algorithm to determine the hull-number of planar partial cube quadrangulations. Instances of the hull-number problem for partial cubes described include poset-dimension and hitting sets for interiors of Jordan curves. To obtain the above results, we investigate convexity in partial cubes and characterize these graphs in terms of their lattice of convex subgraphs, improving a theorem of Handa. Furthermore we provide a topological representation theorem for planar partial cubes, generalizing a result of Fukuda and Handa about rank 3 oriented matroids.

Let M_n be a simple triangulation of the sphere S^2, drawn uniformly at random from all such triangulations with n vertices. Endow M_n with the uniform probability measure on its vertices. After rescaling graph distance on V(M_n) by (3/(4n))^{1/4}, the resulting random measured metric space converges in distribution, in the Gromov-Hausdorff-Prokhorov sense, to the Brownian map. In proving the preceding fact, we introduce a labelling function for the vertices of M_n. Under this labelling, distances to a distinguished point are essentially given by vertex labels, with an error given by the winding number of an associated closed loop in the map. The appearance of a winding number suggests that a discrete complex-analytic approach to the study of random triangulations may lead to further discoveries.

This article presents a unified bijective scheme between planar maps and blossoming trees, where a blossoming tree is defined as a spanning tree of the map decorated with some dangling half-edges that enable to reconstruct its faces. Our method generalizes a previous construction of Bernardi by loosening its conditions of applications so as to include annular maps, that is maps embedded in the plane with a root face different from the outer face. The bijective construction presented here relies deeply on the theory of \alpha-orientations introduced by Felsner, and in particular on the existence of minimal and accessible orientations. Since most of the families of maps can be characterized by such orientations, our generic bijective method is proved to capture as special cases all previously known bijections involving blossoming trees: for example Eulerian maps, m-Eulerian maps, non separable maps and simple triangulations and quadrangulations of a k-gon. Moreover, it also permits to obtain new bijective constructions for bipolar orientations and d-angulations of girth d of a k-gon. As for applications, each specialization of the construction translates into enumerative by-products, either via a closed formula or via a recursive computational scheme. Besides, for every family of maps described in the paper, the construction can be implemented in linear time. It yields thus an effective way to encode and generate planar maps. In a recent work, Bernardi and Fusy introduced another unified bijective scheme, we adopt here a different strategy which allows us to capture different bijections. These two approaches should be seen as two complementary ways of unifying bijections between planar maps and decorated trees.

We consider the problem of enumerating planar constellations with two points at a prescribed distance. Our approach relies on a combinatorial correspondence between this family of constellations and the simpler family of rooted constellations, which we may formulate algebraically in terms of multicontinued fractions and generalized Hankel determinants. As an application, we provide a combinatorial derivation of the generating function of Eulerian triangulations with two points at a prescribed distance.

This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn and their colors is changed according to the number of black balls among them.The limiting behaviour of the composition of the urn when both the time and the number of balls tend to infinity is investigated and the proportion of black balls is shown to converge to an algebraic number. We prove also that, surprisingly enough, not every algebraic number can be ``computed'' this way.

This article presents new enumerative results related to symmetric planar maps. In the first part a new way of enumerating rooted simple quadrangulations and rooted simple triangulations is presented, based on the description of two different quotient operations on symmetric simple quadrangulations and triangulations. In the second part, based on results of Bouttier, Di Francesco and Guitter and on quotient and substitution operations, the series of three families of symmetric quadrangular and triangular dissections of polygons are computed, with control on the distance from the central vertex to the outer boundary.

In this article we study a class of monoids that includes Garside monoids, and give a simple combinatorial proof of a formula for the formal sum of all elements of the monoid. This leads to a formula for the growth function of the monoid in the homogeneous case, and can also be lifted to a resolution of the monoid algebra. These results are then applied to known monoids related to Coxeter systems: we give the growth function of the Artin-Tits monoids, and do the same for the dual braid monoids. In this last case we show that the monoid algebras of the dual braid monoids of type A and B are Koszul algebras.

In the literature, most of the results about the enumeration of directed animals on lattices via gas considerations are obtained by a formal passage to the limit of enumeration of directed animals on cyclical versions of the lattice. Here we provide a new point of view on this phenomenon. Using the gas construction given in Le Borgne and Marckert (2006), we describe the gas process on the cyclical versions of the lattices as a cyclical Markov chain (roughly speaking, Markov chains conditioned to come back to their starting point). Then we introduce a notion of convergence of graphs, which gives a general tool to show that gas processes related to animals enumeration are often Markovian on lines extracted from lattices. We provide examples and computations of new generating functions for directed animals with various sources on the triangular lattice, on the (Tn) lattices and on a generalization of the (Ln) lattices.

Stack-triangulations appear as natural objects when one wants to define some families of increasing triangulations by successive additions of faces. We investigate the asymptotic behavior of rooted stack-triangulations with 2n faces under two different distributions. We show that the uniform distribution on this set of maps converges, for a topology of local convergence, to a distribution on the set of infinite maps. In the other hand, we show that rescaled by , they converge for the Gromov-Hausdorff topology on metric spaces to the continuum random tree introduced by Aldous. Under a distribution induced by a natural random construction, the distance between random points rescaled by (6/11)log(n) converge to 1 in probability. We obtain similar asymptotic results for a family of increasing quadrangulations.

We give a new and bijective proof for the formula of the growth function of the positive braid monoid with respect to Artin generators. We generalize Viennot's heaps of pieces to a large class of monoids that includes braid monoids.