The number of corner polyhedra graphs Dervieux, Clement; Poulalhon, Dominique; Schaeffer, Gilles
Discrete Mathematics and Theoretical Computer Science,
04/2020, Letnik:
DMTCS Proceedings, 28th...
Journal Article, Conference Proceeding
Recenzirano
Odprti dostop
Corner polyhedra were introduced by Eppstein and Mumford (2014) as the set of simply connected 3D polyhedra such that all vertices have non negative integer coordinates, edges are parallel to the ...coordinate axes and all vertices but one can be seen from infinity in the direction (1, 1, 1). These authors gave a remarkable characterization of the set of corner polyhedra graphs, that is graphs that can be skeleton of a corner polyhedron: as planar maps, they are the duals of some particular bipartite triangulations, which we call hereafter corner triangulations.In this paper we count corner polyhedral graphs by determining the generating function of the corner triangulations with respect to the number of vertices: we obtain an explicit rational expression for it in terms of the Catalan gen- erating function. We first show that this result can be derived using Tutte's classical compositional approach. Then, in order to explain the occurrence of the Catalan series we give a direct algebraic decomposition of corner triangu- lations: in particular we exhibit a family of almond triangulations that admit a recursive decomposition structurally equivalent to the decomposition of binary trees. Finally we sketch a direct bijection between binary trees and almond triangulations. Our combinatorial analysis yields a simpler alternative to the algorithm of Eppstein and Mumford for endowing a corner polyhedral graph with the cycle cover structure needed to realize it as a polyhedral graph.
In this paper, a surprising connection is described between a specific brand of random lattices, namely planar quadrangulations, and Aldous’ Integrated SuperBrownian Excursion (ISE). As a ...consequence, the radius rn of a random quadrangulation with n faces is shown to converge, up to scaling, to the width r=R−L of the support of the one-dimensional ISE, or precisely: More generally the distribution of distances to a random vertex in a random quadrangulation is described in its scaled limit by the random measure ISE shifted to set the minimum of its support in zero. The first combinatorial ingredient is an encoding of quadrangulations by trees embedded in the positive half-line, reminiscent of Cori and Vauquelin’s well labelled trees. The second step relates these trees to embedded (discrete) trees in the sense of Aldous, via the conjugation of tree principle, an analogue for trees of Vervaat’s construction of the Brownian excursion from the bridge. From probability theory, we need a new result of independent interest: the weak convergence of the encoding of a random embedded plane tree by two contour walks to the Brownian snake description of ISE. Our results suggest the existence of a Continuum Random Map describing in term of ISE the scaled limit of the dynamical triangulations considered in two-dimensional pure quantum gravity.
We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, ...via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results. In particular we prove (computationally and then bijectively) that the number of plane bipolar posets on n + 2 vertices equals the number of plane permutations (i.e., avoiding the vincular pattern 2 14 3) of size n. Regarding transversal structures, for each v ≥ 0 we consider tn(v) the number of such structures with n + 4 vertices and weight v per quadrangular inner face (the case v = 0 corresponds to having only triangular inner faces). We obtain a recurrence to compute tn(v), and an asymptotic formula that for v = 0 gives tn(0) ∼ c (27/2) n n −1−π/arccos(7/8) for some c > 0, which also ensures that the associated generating function is not D-finite.
We show that corner polyhedra and 3-connected Schnyder labelings join the growing list of planar structures that can be set in exact correspondence with (weighted) models of quadrant walks via a ...bijection due to Kenyon, Miller, Sheffield and Wilson.
Our approach leads to a first polynomial time algorithm to count these structures, and to the determination of their exact asymptotic growth constants : the number $p_n$ of corner polyhedra and $s_n$ of 3-connected Schnyder woods of size $n$ respectively satisfy $(p_n)^{1/n}\to 9/2$ and $(s_n)^{1/n}\to 16/3$ as $n$ goes to infinity.
While the growth rates are rational, like in the case of previously known instances of such correspondences, the exponent of the asymptotic polynomial correction to the exponential growth does not appear to follow from the now standard Denisov-Wachtel approach, due to a bimodal behavior of the step set of the underlying tandem walk. However a heuristic argument suggests that these exponents are $-1-\pi/\arccos(9/16)\approx -4.23$ for $p_n$ and $-1-\pi/\arccos(22/27)\approx -6.08$ for $s_n$, which would imply that the associated series are not D-finite.
The enumeration of maps and the study of uniform random maps have been classical topics of combinatorics and statistical physics ever since the seminal work of Tutte in the 1960s. Following the ...bijective approach initiated by Cori and Vauquelin in the '80s, we describe a bijection between rooted maps, or rooted bipartite quadrangulations, on a surface of genus $g$ and some simpler objects that generalize plane trees. Thanks to a rerooting argument, our bijection allows us to compute the generating series of rooted maps on a surface of genus $g$ with respect to the number of edges, and to recover the asymptotic numbers of such maps. Our construction allows us to keep track in a bipartite quadrangulation of the distances of all vertices to a random basepoint. This is an analogue for higher genus surfaces of the basic result on which were built the recent advances in the comprehension of the intrinsic geometry of large random planar maps, hopefully opening the way to the study of a model of continuum random surfaces of genus $g$.
We present a bijection between the set of plane triangulations (\emph{aka} maximal planar graphs) and a simple subset of the set of plane trees with two leaves adjacent to each node. The construction ...takes advantage of Schnyder tree decompositions of plane triangulations. This bijection yields an interpretation of the formula for the number of plane triangulations with $n$ vertices. Moreover the construction is simple enough to induce a linear random sampling algorithm, and an explicit information theory optimal encoding. Finally we extend our bijection approach to triangulations of a polygon with $k$ sides with $m$ inner vertices, and develop in passing new results about Schnyder tree decompositions for these objects.
In this paper we construct a bijection for partitioned 3-cacti that gives raise to a new formula for enumeration of factorizations of the long cycle into three permutations with given number of ...cycles.
Dans cet article, nous construisons une bijection pour 3-cacti partitionnés faisant apparaître une nouvelle formule pour l’énumération des factorisations d’un long cycle en trois permutations ayant un nombre donné de cycles.
PDF
