Interpretar un diagrama de Venn geométricamente

Question

Esta pregunta se relaciona con la pregunta que le hice un par de años, ver un diagrama de Venn con rectángulos para $n>3$. Dentro de esta pregunta quería saber si es posible dibujar un diagrama de Venn con rectángulos para $n>3$ bajo la restricción de que los rectángulos tienen el mismo ancho y altura, así como estar alineado al eje (no gira). Por su Bound 2 Alex Ravsky señaló que esto no es posible por $n>5$. Sin embargo, Barry Cipra, a continuación, mostró que no es posible para $n\ge4$.

---

Ahora quiero ir un poco más profundo en el número de regiones de un diagrama de Venn. Por lo tanto considero, también, alineado al eje rectángulos con la misma anchura y altura. Los rectángulos no se giran.

Preliminares

1. Un diagrama de Venn no puede ser dibujado con rectángulos para $n>5$
2. La interpretación de un diagrama de Venn geométricamente, las formas $2^n$ regiones, que es $2^n=\sum_{k=0}^n\binom{n}{k}$

La segunda preliminar implica, que un diagrama de Venn ha $\binom{n}{k}$ regiones donde exactamente $k$ rectángulos se intersecan (es decir, se superponen). El uso de la primera preliminar, esta fórmula es geométricamente válido para $n\le 5$.

Como un diagrama de Venn con los rectángulos no puede ser dibujado para $n>5$, al menos, cómo muchas regiones pueden formarse usando $n$ rectángulos (hay un límite superior?)? ¿Cuál es el máximo número posible de regiones donde exactamente $k$ rectángulos se cruzan?

---

Para la primera pregunta que me hizo las siguientes consideraciones:

Deje $a_n$ definir el número máximo de regiones que pueden formarse usando $n$ rectángulos. Imagine $n-1$ ya alineados rectángulos que producen $a_{n-1}$ regiones. Ahora organizar la $n$-ésimo rectángulo, de manera que se cruza cada una de las $n-1$ rectángulos en dos puntos distintos (esto maximiza el número de regiones). Esto produce dos nuevas regiones para cada intersección de la $n-1$ ya alineados rectángulos. Por lo tanto, $a_n=a_{n-1}+2(n-1)$$a_1=2$. El uso de la iteración del método de recursión de los rendimientos $a_n=n^2-n+2$. Tenga en cuenta que$a_n=2^n$$n\le 3$$a_n<2^n$$n>3$.

---

EDIT: hasta ahora, mi primera pregunta sobre el máximo número posible de regiones que pueden formarse usando $n$ rectángulos parece ser respondido correctamente. Que es $2+n(n-1)$ (que funciona incluso para los cuadrados).

Answer 1

Vamos a comenzar. Como yo lo entiendo, usted está pidiendo un determinado$n$$k\le n$, ¿cuántos de entre ${n\choose k}$ regiones creadas por las intersecciones de exactamente $k$ rectángulos entre algunos de los $n$ rectángulos pueden ser representados (voy a llamar a esas regiones k-exacto). Que no es $k$ regiones exactas son permitidos, pero no se toman en cuenta. Denotar la pregunta número máximo de $k$-regiones exactas por $r(n,k)$.

Bound 2 implica $r(n,k)\le n^2+3n-2$ por cada $k$.

Trivial de los casos se $r(n,1)=n$$r(n,n)=1$.

El primer no-trivial caso es $k=2$. Es fácil comprobar que $r(3,2)=3$. Deje $\mathcal R$ ser una familia que consta de $n$ (congruentes) rectángulos. Considere la posibilidad de un gráfico de $G$ con un conjunto $\mathcal R$ de vértices tal que los vértices $R,R'\in\mathcal R$ son adyacentes si existe un $2$-región exacta creado por la intersección de $R$$R'$. Puede comprobarse fácilmente que la prueba de la envolvente de 4 implica que $G$ $K_4$- libre, que es arbitraria entre cuatro distintos rectángulos de $\mathcal R$ existen dos que no crean una $2$-región exacta. Ahora, por Frigyes del teorema, $G$ tiene más de $n^2/3$ bordes. Por lo tanto $r(n,2)\le n^2/3$. Es fácil mostrar que $r(4,2)\ge 5$. Comparando con el límite superior, obtenemos $r(4,2)=5$.