Diagrama de Venn con rectángulos para$n > 3$

Question

¿Es posible dibujar un diagrama de Venn con rectángulos para$n > 3$? Si es así, ¿es posible para todos$n\in\mathbb{N}$? Si no, ¿hasta qué$n$ es posible?

Además, los rectángulos deberían tener las siguientes propiedades

• mismo ancho y alto
• alineado con el eje (no girado)

Answer 1

Resolver el problema dado he probado diferentes enfoques, la obtención de mejores y límites. También la última obligado es la mejor, les dejo la otra, ya que pueden ayudar a resolver problemas similares.

Bound 4. Yo reclamo que $n\le 3$. En efecto, supongamos por el contrario, existe una familia de $\mathcal R$ $4$ (congruentes) rectángulos que representan un diagrama de Venn. Definir dos órdenes de $\le_x$$\le_y$$\mathcal R$. Es decir, para rectángulos $R,R'\in\mathcal R$ puesto $R\le_t R'$ si $t$-coordinar el lado izquierdo del rectángulo $R$ en no más grande que $t$-coordinar el lado izquierdo del rectángulo $R'$. Deje $R_1\le_x R_2\le R_3\le R_4$ ser la enumeración de la familia $\mathcal R$.

Supongamos primero que $R_1$ o $R_4$ es un mínimo o un elemento maximal de a $(\mathcal R,\le_y)$. Aplicar, si es necesario, para el plano de las transformaciones $x\mapsto -x$$y\mapsto -y$, sin pérdida de generalidad podemos suponer que $R_1$ es el mínimo elemento de $(\mathcal R,\le_y)$. Si $R_2\le_y R_4$$R_1\cap R_4\subset R_2$, contradiciendo la propiedad de un diagrama de Venn. Si $R_3\le_y R_4$$R_1\cap R_4\subset R_3$, contradiciendo la propiedad de un diagrama de Venn. Por lo tanto $R_4\le_y R_2$$R_4\le_y R_3$. Ahora si $R_2\le_y R_3$$R_1\cap R_3\subset R_2$, contradiciendo la propiedad de un diagrama de Venn y si $R_3\le_y R_2$$R_2\cap R_4\subset R_3$, contradiciendo la propiedad de un diagrama de Venn.

Así, en el orden de $\le_y$ los elementos $R_1$ $R_4$ están colocados entre los elementos $R_2$$R_3$. Pero, a continuación,$R_1\cap R_4\subset R_2\cup R_3$, contradiciendo la propiedad de un diagrama de Venn. En efecto, suponga que a contrario, que hay una (interior) punto de $R_1\cap R_4\setminus (R_2\cup R_3)$. Deje $\ell$ ser una línea recta horizontal ging a través del punto de $x$. Es fácil ver que si $\ell$ se cruza con alguno de los rectángulos $R_1$ o $R_4$ a continuación, se contradice la elección de $R_1$ o $R_4$ como de la izquierda o de la derecha del rectángulo. Desde $R_2$ $R_3$ cruza, tanto en $R_2$ $R_3$ se encuentran por encima de $\ell$ o ambos $R_2$ $R_3$ se encuentran debajo de la $\ell$, una contradicción con ese $R_2$ $R_3$ superior e inferior rectángulos.

Bound 3. Yo reclamo que $n\le 4$. En efecto, supongamos por el contrario, existe una familia de $\mathcal R$ $n\ge 5$ (congruentes) rectángulos que representan un diagrama de Venn. Definir dos órdenes de $\le_x$$\le_y$$\mathcal R$. Es decir, para rectángulos $R,R'\in\mathcal R$ puesto $R\le_t R'$ si $t$-coordinar el lado izquierdo del rectángulo $R$ en no más grande que $t$-coordinar el lado izquierdo del rectángulo $R'$. Por Erdős–Szekeres teorema existen distintos rectángulos $R,R',R''\in\mathcal R$ tal que $R\le_x R'\le_x R''$ y, o bien $R\le_y R'\le_y R''$ o $R''\le_y R'\le_y R$. De todos modos, $R\cap R''\subset R'$, contradiciendo la propiedad de un diagrama de Venn.

Bound 2. Una más ajustada cota superior para $n$ se puede obtener como sigue. Dada una partición del plano en los dominios por los rectángulos, considerar las esquinas de estos dominios como los vértices de un grafo $G$ y los segmentos de los lados de los rectángulos de la conexión de algunos de los rincones como los vértices de la gráfica. A continuación, cada uno de los rectángulos de la familia contribuye en la mayoría de las $4$ sus esquinas para el número total $c$ de las esquinas, y cada dos diferentes rectángulos de la familia, además de contribuir a este número en la mayoría de las $4$ en el caso general, y en la mayoría de las $2$ en su caso. Por lo tanto $c\le 4n+2n(n-1)=2n^2+2n$ en el caso general, y $c\le 4n+n(n-1)=n^2+3n$ vértices en su caso.

Ahora el doble cómputo de un número $N$ de los pares de $(e, f)$ donde $e$ es un borde de la gráfica de $G$ incidente a su cara $f$. Dado que, por la construcción, cada cara $f$ de la gráfica de $G$ tiene un grado mínimo de $4$, contribuye, al menos, $4$ a la suma de $N$, lo que implica la $N\ge 4r$ donde $r$ es el número de caras de la gráfica de $G$, igual al número de dominios en los que los rectángulos de la partición del plano. Por otro lado, cada arista $e$ $G$ es incidente a exactamente $2$ caras (también contamos la cara externa, si es necesario), lo que contribuye exactamente $2$ a la suma de $N$, lo que implica la $N=2m$ donde $m$ es el número de aristas del grafo $G$. Por lo tanto $2m=N\ge 4r$.

La combinación de los obtenidos con la desigualdad de Euler fórmula $c-m+r=2$, obtenemos $r=2+m-c\le m/2$ o $m+4\le 2c$. A continuación,$r=2+m-c\le 2c-2-c=c-2$, que es en la mayoría de los $2n^2+2n-2$ en el caso general, y en la mayoría de las $n^2+3n-2$ vértices en su caso. La desigualdad de $r\ge 2^n$ implica $n\le 6$ en el caso general, y $n\le 5$ en su caso.

Ruedas 1. Incluso en un caso general, cuando no requerimos que los rectángulos tienen el mismo ancho y la altura, la familia consta de $n$ rectángulos útil por sus tamaños en la mayoría de las $2n$ líneas paralelas a cada uno de los ejes de coordenadas. Así que se puede particionar el plano en que en la mayoría de $(2n+1)^2$ dominios, mientras que los de Venn diagrama de la ha $2^n$ dominios. Por lo $(2n+1)^2\ge 2^n$, que los rendimientos de $n\le 8$.