Analytic combinatorics of chord and hyperchord diagrams with k crossings

DOI10.1016/J.AAM.2014.04.001MaRDI QIDQ403161zbMATH OpenOpenAlexFDO

Authors Vincent Pilaud, Juanjo Rué

Publication date 29 August 2014

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

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)

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.

Recommendations

• Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings
• Publication:4502534
• Linear \(k\)-chord diagrams
• Analytic combinatorics of non-crossing configurations
• Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

Cites work

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

Cited in

(8)

• Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings
• Linear \(k\)-chord diagrams
• scientific article; zbMATH DE number 1504583 (Why is no real title available?)
• Perfect matchings with crossings
• Perfect matchings with crossings
• The combinatorics of a tree-like functional equation for connected chord diagrams
• Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle

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)