Change search
ReferencesLink to record
Permanent link

Direct link
Generalized triangulations and diagonal-free subsets of stack polyrominoes
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
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
Abstract [en]

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.
Keyword [en]
enumeration, polygon, triangulation, associahedron, Catalan number, Hankel determinant
URN: urn:nbn:se:kth:diva-15075DOI: 10.1016/j.jcta.2005.01.009ISI: 000232241700005ScopusID: 2-s2.0-25144491045OAI: diva2:333116
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jonsson, Jakob
By organisation
Mathematics (Div.)
In the same journal
Journal of combinatorial theory. Series A (Print)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link