Analytic combinatorics of chord and hyperchord diagrams with k crossings

DOI10.1016/J.AAM.2014.04.001zbMATH Open1295.05036arXiv1307.6440OpenAlexW2018335206MaRDI QIDQ403161FDOQ403161

Vincent Pilaud, Juanjo Rué

Publication date: 29 August 2014

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Using methods from Analytic Combinatorics, we study the families of perfect matchings, partitions, chord diagrams, and hyperchord diagrams on a disk with a prescribed number of crossings. For each family, we express the generating function of the configurations with exactly $k$ crossings as a rational function of the generating function of crossing-free configurations. Using these expressions, we study the singular behavior of these generating functions and derive asymptotic results on the counting sequences of the configurations with precisely $k$ crossings. Limiting distributions and random generators are also studied.

Full work available at URL: https://arxiv.org/abs/1307.6440

zbMATH Keywords

generating functionsanalytic combinatoricschord diagramsquasi-planar configurations

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On convergence rates in the central limit theorems for combinatorial structures
• Singularity Analysis of Generating Functions
• The number of connected sparsely edged graphs
• The number of connected sparsely edged graphs. II. Smooth graphs and blocks
• Maximal fillings of Moon polyominoes, simplicial complexes, and Schubert polynomials
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• Analytic combinatorics of non-crossing configurations
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• Crossings and nestings of matchings and partitions
• A Bijection for Rooted Maps on Orientable Surfaces
• Multitriangulations as complexes of star polygons
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A Turán-type theorem on chords of a convex polygon
• Partitions with \(k\) crossings
• On an asymptotic method in enumeration
• A generalization of diagonal flips in a convex polygon
• Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings
• Uniform random sampling of planar graphs in linear time
• Sur Un Problème De Configurations Et Sur Les Fractions Continues

Cited In (7)

• Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings
• Perfect matchings with crossings
• Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings
• Perfect matchings with crossings
• The combinatorics of a tree-like functional equation for connected chord diagrams
• Linear $k$-Chord Diagrams
• Title not available (Why is that?)

This page was built for publication: Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403161)