Search

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on analytic combinatorics and on the notion of patchwork to describe the possible overlapping of copies. [ABSTRACT FROM AUTHOR]

We introduce a new technique to specify increasing labeled structures. For such objects, the boxed product as introduced by Greene is sufficient to efficiently specify the class, however for particular classes the size of the specification is very large. In particular, in the case of partially ordered sets, the calculus of the total orders compatibles with the poset (called linear extensions) can be tedious. We here developed an idea due to Stanley that uses a geometrical interpretation to calculate the linear extensions of a given poset. We will present a way to extend this idea to the symbolic method, and illustrate it with the example of specific increasing trees with exactly one repeated label, and show how to uniformly generate such structures. [ABSTRACT FROM AUTHOR]

A two-dimensional lattice walk model is said to be reluctant if its defining step set has a strong drift away from the negative half-planes. We consider the uniform random generation of reluctant walks of length n in the positive quadrant, noting that a naive rejection from unconstrained walks has exponential time complexity. A baseline algorithm using the recursive method requires Θ ( n 4 ) time and memory. We consider an alternative strategy which draws unidimensional walks from a well-chosen half-plane model, as identified by Johnson, Mishna and Yeats. The resulting generator is provably efficient, and typically outperforms the baseline algorithm. A general analysis of its complexity requires further developments to characterize the subexponential growth factors of reluctant walks, and motivates the design of efficient algorithms for the generation of 1D walks taking irrational step sets. [ABSTRACT FROM AUTHOR]

The goal of our work is to analyze random cubic planar graphs according to the uniform distribution. More precisely, let G be the class of labelled cubic planar graphs and let g n be the number of graphs with n vertices. Then each graph in G with n vertices has the same probability 1 / g n . This model was analyzed first by Bodirsky et al. [1], and here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs in [1] where incomplete with respect to the singularity analysis and we aim at providing full proofs. Secondly, we obtain new results that considerably strengthen those in [1] and shed more light on the structure of random cubic planar graphs. We present a selection of our results on asymptotic enumeration and on limit laws for parameters of random graphs. [ABSTRACT FROM AUTHOR]

In this extended abstract we determine a normal limiting distribution for the number of triangles in a uniformly at random 3-connected cubic planar graph, as well as the precise expectation and variance values. Further comments towards the more complicated problem of studying both the limiting distribution of triangles in random cubic planar graphs, and the (asymptotic) number of triangle-free cubic planar graphs are discussed as well. [ABSTRACT FROM AUTHOR]

Non-uniform hypergraphs appear in various domains of computer science as in the satisfiability problems and in data analysis. We analyse a general model where the probability for an edge of size t to belong to the hypergraph depends of a parameter ω t of the model. It is a natural generalization of the models of graphs used by Flajolet, Knuth and Pittel [11] and Janson, Knuth, Łuczak and Pittel [16] . The present paper follows the same general approach based on analytic combinatorics. We show that many analytic tools developed for the analysis of graphs can be extended surprisingly well to non-uniform hypergraphs. More specifically, we analyze their typical structure before and near the birth of the complex components, that are the connected components with more than one cycle. We derive the asymptotic number of sparse connected hypergraphs as their complexity, defined as the excess , increases. Although less natural than the number of edges, this parameter allows a precise description of the structure of hypergraphs. Finally, we compute some statistics of the model to link number of edges and excess. [ABSTRACT FROM AUTHOR]

Abstract: Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of combinatorials objects. This paper proposes a Boltzmann sampler for ordered structures constructed with the box operator, which is an extension of the cartesian product. Under an abstract real-arithmetic computation model, our algorithm is of linear complexity for free generation. For generation of objects of a targetted size, provided a small tolerance, the complexity remains linear for many classes of structures. As an illustration we show how to generate alternating permutations, and our implementation makes possible to generate random objects of sizes up to 107 on a standard machine. [Copyright &y& Elsevier]