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

Remark: This problem was raised independently around the same time by Karen Meagher and by me.

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

**Update** Paco Santos proposed the following intermediete conjecture:

**Conjecture:** For every flag simplicial polytope, the maximum size of a set of pairwise intersecting facets is achieved by the facets containing some common vertex.

A flag simplicial polytope is a simplicial polytops so that every set of vertices that any two form an edge is the set of vertices of a face. Santos's conjecture thus asserts that the conjecture about polytopes with no triangular faces still applies for dual-to-flag polytopes.

3more comments