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}|$.


Update (and counter-update)

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).

Update: Bruno le Floch showed that the more general conjecture is false: He described a quadrangulation of S^2 with 15 vertices and 13 quadrangles having 5 vertices each two on a face.

share|improve this question
1  
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
1  
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
2  
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
    
Dear Bruno, thanks very nice! –  Gil Kalai Apr 12 at 6:08
    
Consider the graph with $V$ the set of all triangulations and and an edge between two vertices if the two triangulations have a diagonal in common. Your Problem is equivalent of showing that there exist no $C_{n-3}+1$-clique. Maybe this graph has been studied. The graph is connected. For $n\leq 6$ it is also a regular graph. –  user35593 Apr 12 at 6:56

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.