Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\cal S \subset \cal T_n$ be a subfamily of triangulations with the property that every two triangulations of $\cal S$ have a common diagonal.

Problem: Show that $|\cal S| \le |\cal T_{n-1}|$.


A few weeks after this problem was posted Gjergji Zaimi (private communication) proposed a more general conjecture:

Conjecture: Let $P$ be a polytope with no triangular face. Then the maximum number of vertices such that every two vertices belongs to a common facet is attained by all vertices of a single facet.

The original question is the case of the associahedron. The case of the permutahedron is known- it is a result by Frankl and Deza- and it is related to extremal combinatorics on permutations. For the cube the result is immediate but can serve as a good starting point for extremal combinatorics (Problem 1 here).

share|improve this question
Have you thought about using a cluster algebra mutation argument? Triangulations having all but one diagonal in common correspond to adjacent clusters in a cluster algebra of type $A$, so maybe this helps? –  Jan Grabowski Nov 27 '12 at 11:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.