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
The conjecture is too general (if I understand it correctly). Take a 3×3 grid of squares and identify opposite edges to make a polyhedron with square faces and the topology of the torus. Any two points belong to a common facet, so the maximum number of vertices such that [...] is 9. The same happens for a periodic grid of 3×…×3 hypercubes. –  Bruno Le Floch Oct 20 '14 at 15:52
A (counter-)example with $S^2$ topology. Let OABCD be a square pyramid and let A' and C' be the mid-points of OA and OC. The result is a (degenerate) polyhedron with five quadrilateral faces, and the points OABCD have the required property. If you don't allow collinear vertices then shift A' and C' a bit, keeping OA'AD and OC'CB flat, then replace the no-longer-flat faces OA'AB and OC'CD by five quadrilaterals each (glue a "cube" onto each face). –  Bruno Le Floch Oct 20 '14 at 16:38

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.