Venn diagram with rectangles: How many among $\binom{n}{k}$ regions created by intersections of exactly $k$ rectangles can be represented? This question is related to the question I asked a few time ago, see Venn diagram with rectangles for $n>3$. Within this question I wanted to know whether it is possible to draw a Venn diagram with rectangles for $n>3$ under the restriction that the rectangles are having the same width and height as well as being axis-aligned (not rotated). By his Bound 2 Alex Ravsky pointed out that this is not possible for $n>5$. However, Barry Cipra then showed that it is not possible for $n\ge4$.

Now I want to go a little bit deeper into the number of regions of a Venn diagram. Therefore I also consider axis-aligned rectangles with the same width and height. The rectangles are not rotated.
Preliminaries


*

*A Venn diagram cannot be drawn with rectangles for $n\ge4$

*Interpreting a Venn diagram geometrically, it forms $2^n$ regions, which is $2^n=\sum_{k=0}^n\binom{n}{k}$ 


The second preliminary implies, that a Venn diagram has $\binom{n}{k}$ regions where exactly $k$ rectangles intersect (i.e. overlap). Using the first preliminary, this formula is geometrically valid for $n<4$.


*

*As a Venn diagram with rectangles can't be drawn for $n\ge4$, at least how many regions can be formed using $n$ rectangles (is there an upper bound?)?


The maximum possible number of regions that can be formed using $n$ rectangles is $2+n(n-1)$.


*

*What is the maximum possible number of regions where exactly $k$ rectangles intersect?

For the first question I made the following considerations:
Let $a_n$ define the maximum number of regions which can be formed using $n$ rectangles. Imagine $n-1$ already aligned rectangles that produce $a_{n-1}$ regions. Now arrange the $n$-th rectangle in a way so that it intersects each of the $n-1$ rectangles in two distinct points (this maximizes the number of regions). This produces two new regions for every intersection of the $n-1$ already aligned rectangles. Thus, $a_n=a_{n-1}+2(n-1)$ with $a_1=2$. Using the iteration method for recursion yields $a_n=n^2-n+2$. Note that $a_n=2^n$ for $n\le 3$ and $a_n<2^n$ for $n>3$.
 A: Let’s start. As I understand, you are asking given $n$ and $k\le n$, how many among ${n\choose k}$ regions created by intersections of exactly $k$ rectangles among some $n$ rectangles can be represented (I shall call such regions k-exact). That is not $k$ exact regions are allowed, but not taken into account. Denote the asked maximum number of $k$-exact regions by $r(n,k)$. 
Bound 2 implies $r(n,k)\le n^2+3n-2$ for each $k$.
Trivial cases are $r(n,1)=n$ and $r(n,n)=1$. 
The first non-trivial case is $k=2$. It is easy to check that $r(3,2)=3$. Let $\mathcal R$ be a family consisting of $n$ (congruent) rectangles. Consider a graph $G$ with a set $\mathcal R$ of vertices such that the vertices $R,R’\in\mathcal R$ are adjacent  iff there exists a $2$-exact region created by intersection of $R$ and $R’$. It can be easily checked that the proof of Bound 4 implies that $G$ is $K_4$-free, that is among arbitrary  four distinct rectangles of $\mathcal R$ exist two which do not create a $2$-exact region. Now, by Turán's theorem, $G$ has at most $n^2/3$ edges. Thus $r(n,2)\le n^2/3$. It is easy to show that $r(4,2)\ge 5$. Comparing with the upper bound, we obtain $r(4,2)=5$.
Added. The absence of other answers despite of the opened bounty suggests that the question looks hard. So I proposed it to Prof. Dr. Alexander Wolff as a subject for a joint research with his group. Although this question is specific, he will may be interested in it because it looks like a propitious topic to apply different ideas of graph theory. 
I remark trivial lower bounds. For each $n\ge k$ and each $l$, taking $l$ copies of the diagram for $r(n,k)$ we obtain a lower bound $r(ln,lk)\ge r(n,k)$. Taking disjoint diagrams for $r(n,k)$ and $r(n’,k)$ we obtain a lower bound $r(n+n’,k)\ge r(n,k)+r(n’,k)$.
But I concentrated my investigation on most interesting for me problem to tighten a degree gap between a linear lower bound and a quadratic* upper bound for $r(k,n)$ with fixed $k$ and $n$ tending to the infinity. The most interesting case for me is $k=2$, for which I found the following reduction of the upper bound. 
Lemma. Let $C>0$, $\alpha\ge 1$, and $Cn^\alpha$ be an upper bound for the number of $2$-exact regions on a diagram with $n$ rectangles containing a common point. Then $r(n,2)\le Cn^\alpha+2\sqrt{2}n^{3/2}+ 8n.$ 
Proof. Consider a diagram of $n$ axis-aligned rectangles having the same width and height with $r(n,2)$ $2$-exact regions. Applying to the diagram plane an affine transformation, we can convert all diagram rectangles into (axis-aligned) unit squares. Endow the diagram plane with a unit square grid $\Gamma$ such that no diagram square side contains a grid node. Then each diagram square contains exactly one grid node in its interior. For each grid node $s$ let $V_s$ be the set of diagram squares containing $s$ and $n_s=|V_s|$. Thus, $n=\sum_{s\in\Gamma} n_s$. We say that nodes $s$ and $t$ of $\Gamma$ are adjacent and write $(s,t)\in E(\Gamma)$, provided $t$ is one of eight natural neighbors of $s$. Define the graph $G$ similarly to the above. Let $s,t$ be arbitrary distinct nodes of the grid $\Gamma$. Consider a subgraph $G_{s,t}$ of $G$ with a set $V_s\cup V_t$ of vertices and all edges between $V_s$ and $V_t$ (so the graph $ G_{s,t}$ is bipartite). We claim that the graph $G_{s,t}$ contains no $4$-cycles (that is, cycles of length $4$). Indeed, suppose to the contrary, there exists such a cycle with vertices $R,R’$ of $V_s$ and $T,T’$ of $V_t$ (remark, that $s$ and $t$ are necessarily adjacent in $\Gamma$). Consider a diagram $\mathcal R’$ created by squares $R$, $R’$, $T$, and $T’$. Since each of rectangles $R$, $R’$ contains a grid node $s$ in its interior and each of rectangles $T$, $R’$ contains a grid node $s$ in its interior, a small piece of the plane near $s$ and behind $s$ (if we look from $t$) is contained in each of $R$ and $R’$, but in none of $T$ and $T’$. Thus the squares $R$ and $R’$ create a $2$-exact region in the diagram $\mathcal R’$. Similarly we can show that the squares $T$ and $T’$ create a $2$-exact region in the diagram $\mathcal R’$. Thus, each two of distinct squares of the diagram $\mathcal R’$ create a 2-exact region, which contradicts the proof of Bound 4. Since the graph $G_{s,t}$ is bipartite and has no $4$-cycles, by Kővári–Sós–Turán theorem it has less than $(n_s-1)n_t^{1/2}+n_t$ egdes. Let $m$ be the number of edges of the graph $G$. Then
$$m\le\sum_{s\in\Gamma} Cn_s^\alpha+\sum_{(s,t)\in E(\Gamma)} (n_s-1)n_t^{1/2}+n_t\le$$
$$Cn^\alpha +\sum_{(s,t)\in E(\Gamma)} n_sn_t^{1/2}+ \sum_{t\in\Gamma} n_t \cdot |\{s\in\Gamma: (s,t)\in E(\Gamma)\}|\le $$
$$Cn^\alpha +\sum_{s\in\Gamma} n_s \sum_{(s,t)\in E(\Gamma)} n_t^{1/2}+ \sum_{t\in\Gamma} n_t\cdot 8\le $$
$$Cn^\alpha +\sum_{s\in\Gamma} n_s \sqrt{8\cdot\sum_{(s,t)\in E(\Gamma)} n_t}+ 8n\le $$
$$Cn^\alpha +\sum_{s\in\Gamma} n_s \sqrt{8n}+ 8n\le $$
$$Cn^\alpha +n\sqrt{8n}+ 8n.$$
I can talk at our seminar on the bound $Cn^\alpha$ with our specialists on semilattices, because this question can be reformulated in terms of their favorite semilattice $(\Bbb N^2,\min)$.
