Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Multichains, non-crossing partitions and trees

Bijections are presented between certain classes of trees and multichains in non-crossing partition lattices.     

Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n²) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(loglogn) and O(n²) time, respectively, based on the reverse search technique.     

2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.     

Lower bounds on the maximum number of non-crossing acyclic graphs

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of $N$ points has $\Omega \left(12.52^N\right)$ non-crossing spanning trees and $\Omega \left(13.61^N\right)$ non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of $N$ points in general position given by Dumitrescu, Schulz, Sheffer and Tóth (2013). Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of $O\left(22.12^N\right)$ for the number of non-crossing spanning trees of the double chain is also obtained.     

Exceptional Sequences over Path Algebras of Type A n and Non-Crossing Spanning Trees

Exceptional sequences are fundamental to investigate the derived categories of finite dimensional algebras. The aim of this note is to classify all the complete exceptional sequences over the path algebra of a Dynkin quiver of type A _n in terms of non-crossing spanning trees.     

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.     

Non-crossing cumulants of type B

We establish connections between the lattices of non-crossing partitions of type B introduced by V. Reiner, and the framework of the free probability theory of D. Voiculescu.

Lattices of non-crossing partitions (of type A, up to now) have played an important role in the combinatorics of free probability, primarily via the non-crossing cumulants of R. Speicher. Here we introduce the concept of non-crossing cumulant of type B; the inspiration for its definition is found by looking at an operation of ``restricted convolution of multiplicative functions', studied in parallel for functions on symmetric groups (in type A) and on hyperoctahedral groups (in type B).

The non-crossing cumulants of type B live in an appropriate framework of ``non-commutative probability space of type B', and are closely related to a type B analogue for the R-transform of Voiculescu (which is the free probabilistic counterpart of the Fourier transform). By starting from a condition of ``vanishing of mixed cumulants of type B', we obtain an analogue of type B for the concept of free independence for random variables in a non-commutative probability space.