55
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 27, 2012 at 11:09
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 20, 2014 at 15:52
  • 4
    $\begingroup$ 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). $\endgroup$ Oct 20, 2014 at 16:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – user35593
    Apr 12, 2015 at 6:56
  • 1
    $\begingroup$ There is a conjecture stronger than the original one and weaker than the (false and) more general one that might be true: 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. $\endgroup$ Nov 23, 2016 at 18:58

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What makes the problem hard is the fact that there can be intersecting families that do not correspond to faces of the associahedron. I don't know what the policy is for this, but I would have preferred for this question to remain in the "unanswered" section, where it is more likely to get visibility. I would personally encourage adding comments as comments. $\endgroup$ May 24, 2017 at 22:32
  • 1
    $\begingroup$ Dear Robert, "I'm sure the largest family of intersecting triangulations must always share the same diagonal", yes this is indeed the motivation for the problem and where the difficulty in proving it lies! $\endgroup$
    – Gil Kalai
    May 29, 2017 at 17:40
  • $\begingroup$ Robert, no I don't have a proof and the question is open to the best of my knowledge. The observation that in order to to maximize the size of the family of all triangulations that contain a given diagonal you need to take the "short" diagonal was indeed known. $\endgroup$
    – Gil Kalai
    May 31, 2017 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.