Intersecting family of triangulations

Question

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.

Answer 1

This falls short of a proof but is too long for a comment. I show that for every $n$ there is always a family $\cal \overline S$ large enough that $|\cal \overline S| = |\cal T_{n-1}|$ and therefore that if the conjecture in the question is true, it is in fact a slightly stronger statement than claimed:

The question inquires into the largest family of triangulations in which every pair of members shares some diagonal.

If we instead fix any single diagonal in common to every member of a family of triangulation of an n-gon, it is self-evident (from the noncrossing property of triangulations) that the number of triangulations sharing it is given by the product of the enumerations of the two families of triangulations of the ploygons so formed either side of it.

For any triangulatable n-gon, any given diagonal is a member of up to two fan triangulations, in which it can be assigned an integer the $d^{th}$ diagonal from the perimeter satisfying $1\leq d\leq \frac{n-2}{2}$. By symmetry we may choose either of the two fans with no effect upon the distance of the diagonal from the nearest edge.

$d=\frac{n-2}{2}$ shall be the distance of the central triangulation if $n$ is even and $d=\frac{n-3}{2}$ shall be the distance of the two "most central" diagonalisations if $n$ is odd.

The number of triangulations of any $n$-gon sharing the $d^{th}$ diagonal is the product of the number of triangulations $\cal T(d,n)$ either side of it:

$$\cal T(d,n)=C_d\times C_{n-d}$$

$$\cal T(d,n)=(d+1)^{-1}\binom{2d}{d}(n-d+1)^{-1}\binom{2n-2d}{n-d}$$

The ratio of one Catalan number to the next is greater than the ratio of the previous two Catalan numbers, and therefore in the choice of which diagonal to share, in order to maximise the size of the family, for any given choice $d$ of diagonal which is not at the edge, we may always identify a larger family by choosing the diagonal $d-1$ which is one position closer to the perimeter and by induction the outermost diagonal $d=1$ yields the largest family.

The size of the largest family of triangulations sharing the same diagonal is therefore given by:

$|\cal\overline S| = C_{n-2-1}\times C_1=|\cal T_{n-1}|$

My claim which would complete the proof (and which remains to be proven) is that there is no family of triangulations in which every pair shares some diagonal, which is larger than the largest family of triangulations in which every triangulation in the family shares the same diagonal.

I suspect this is proven by the fact that the largest face on any associahedron has the same number of edges as the number of vertices of the associahedron one order smaller. In particular I believe that each face of the associahedron represents a family of triangulations which all share the same edge. These two statements alone would in fact be sufficient to answer the entire question in the affirmative.