54
$\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$
  • 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$ – Jan Grabowski Nov 27 '12 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$ – Bruno Le Floch Oct 20 '14 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$ – Bruno Le Floch Oct 20 '14 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 '15 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$ – Francisco Santos Nov 23 '16 at 18:58
2
$\begingroup$

This falls slightly short of a proof but is too long for a comment.

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 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$
  • $\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$ – Gjergji Zaimi May 24 '17 at 22:32
  • $\begingroup$ @GjergjiZaimi I'm sure the largest family of intersecting triangulations must always share the same diagonal, which gives my result. This property can easily be proven for the set of possibly crossing diagonals, in fact I realised later the proof of which is referenced in your linked example. But this property appears to be preserved in the non crossing subsets. Do you have a counterexample? I'll gladly remove if wrong. $\endgroup$ – user334732 May 25 '17 at 2:58
  • $\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 '17 at 17:40
  • $\begingroup$ @GilKalai Do u already have the proof? Assuming the result is unknown, by showing equality rather than inequality moves us closer, but if this is an exercise in showing a known result, my partial answer has little point. I hope to finish the answer when I get a chance by showing the largest family is described by the Tamari lattice which is embedded in the next dimension up of lattice. $\endgroup$ – user334732 May 31 '17 at 8:46
  • $\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 '17 at 17:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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