Familia de triangulaciones de intersección

Question

Dejemos que $\cal T_n$ sea la familia de todas las triangulaciones sobre un $n$ -gon utilizando $(n-3)$ diagonales no intersecantes. El número de triangulaciones en $\cal T_n$ es $C_{n-2}$ el $(n-2)$ th Número catalán . Sea $\cal S \subset \cal T_n$ sea una subfamilia de triangulaciones con la propiedad de que cada dos triangulaciones de $\cal S$ tienen una diagonal común.

El problema: Demuestra que $|\cal S| \le |\cal T_{n-1}|$ .

Observación: Este problema fue planteado de forma independiente alrededor de la misma época por Karen Meagher y por mí.

---

Actualización (y contra-actualización)

Unas semanas después de la publicación de este problema, Gjergji Zaimi (comunicación privada) propuso una conjetura más general:

Conjetura: Dejemos que $P$ sea un politopo sin cara triangular. Entonces el número máximo de vértices tal que cada dos vértices pertenecen a una faceta común es alcanzado por todos los vértices de una sola faceta.

La pregunta original es el caso del associaedro . El caso del permutaedro es conocido -es un resultado de Frankl y Deza- y está relacionado con combinatoria extrema sobre permutaciones . Para el cubo el resultado es inmediato pero puede servir como un buen punto de partida para la combinatoria extrema (Problema 1 aquí ).

Actualización: Bruno le Floch demostró que la conjetura más general es falsa: Describió una cuadrangulación de S^2 con 15 vértices y 13 cuadrángulos que tienen 5 vértices cada uno dos en una cara.

Actualización Paco Santos propuso la siguiente conjetura intermedia:

Conjetura: Para todo politopo simplicial de bandera, el tamaño máximo de un conjunto de facetas que se cruzan por pares se alcanza con las facetas que contienen algún vértice común.

Un politopo simplicial de bandera es un politopo simplicial de manera que cada conjunto de vértices que dos cualesquiera forman una arista es el conjunto de vértices de una cara. La conjetura de Santos afirma, pues, que la conjetura sobre los politopos sin caras triangulares sigue siendo válida para los politopos duales a bandera.

Answer 1

Esto se queda un poco corto para una prueba, pero es demasiado largo para un comentario.

La pregunta se refiere a la mayor familia de triangulaciones en la que cada par de miembros comparte alguna diagonal.

Si en cambio fijamos cualquier solo diagonal en común a cada miembro de una familia de triangulación de un n-gon, es evidente (a partir de la propiedad de no cruce de triangulaciones) que el número de triangulaciones que lo comparten viene dado por el producto de las enumeraciones de las dos familias de triangulaciones de los ploygons así formados a cada lado.

Para cualquier n-gono triangulable, cualquier diagonal dada es miembro de hasta dos triangulaciones en abanico, en las que se le puede asignar un número entero el $d^{th}$ diagonal del perímetro que satisface $1\leq d\leq \frac{n-2}{2}$ . Por simetría podemos elegir cualquiera de los dos abanicos sin que ello afecte a la distancia de la diagonal al borde más cercano.

$d=\frac{n-2}{2}$ será la distancia de la triangulación central si $n$ es par y $d=\frac{n-3}{2}$ será la distancia de las dos diagonalizaciones "más centrales" si $n$ es impar.

El número de triangulaciones de cualquier $n$ -gon compartiendo el $d^{th}$ diagonal es el producto del número de triangulaciones $\cal T(d,n)$ a cada lado de ella:

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

La relación de un número catalán con el siguiente es mayor que la relación de los dos números catalanes anteriores, y por tanto en la elección de qué diagonal compartir, para maximizar el tamaño de la familia, para cualquier elección $d$ de la diagonal que no está en el borde, siempre podemos identificar una familia más grande eligiendo la diagonal $d-1$ que es una posición más cercana al perímetro y por inducción la diagonal más externa $d=1$ produce la familia más grande.

Por tanto, el tamaño de la mayor familia de triangulaciones que comparten la misma diagonal viene dado por:

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

Mi afirmación que completaría la prueba (y que queda por demostrar) es que no existe ninguna familia de triangulaciones en la que cada par comparta alguna diagonal, que sea mayor que la mayor familia de triangulaciones en la que cada triangulación de la familia comparta la misma diagonal.

Sospecho que esto se demuestra por el hecho de que la cara más grande de cualquier associaedro tiene el mismo número de aristas que el número de vértices del associaedro de un orden menor. En particular, creo que cada cara del asociaedro representa una familia de triangulaciones que comparten la misma arista. De hecho, estas dos afirmaciones bastarían para responder afirmativamente a toda la pregunta.