Generalized triangulations and diagonal-free subsets of stack polyrominoes
2005 (English)In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 112, no 1, 117-142 p.Article in journal (Refereed) Published
For n >= 3, let Omega(n) be the set of line segments between vertices in a convex n-gon. For j >= 1, a j-crossing is a set of j distinct and mutually intersecting line segments from Q,, such that all 2j endpoints are distinct. For k >= 1, let Delta(n,k) be the simplicial complex of subsets of Omega(n) not containing any (k + 1)-crossing. For example, Delta(n.1) has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Delta(n,k) have the same number k(2n - 2k - 1) of line segments. We demonstrate that the number of such maximal sets is counted by a k x k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung, on determinantal ideals.
Place, publisher, year, edition, pages
2005. Vol. 112, no 1, 117-142 p.
enumeration, polygon, triangulation, associahedron, Catalan number, Hankel determinant
IdentifiersURN: urn:nbn:se:kth:diva-15075DOI: 10.1016/j.jcta.2005.01.009ISI: 000232241700005ScopusID: 2-s2.0-25144491045OAI: oai:DiVA.org:kth-15075DiVA: diva2:333116
QC 201005252010-08-052010-08-05Bibliographically approved