How many whole rectangles can you catch in a grid?

I’m amazed how you can devise new problems in so well-studied domain as plain combinatorial geometry.

My first attack of the problem brought the following results.

Proposition 1. If $n$ is not least than Ramsey number $R(m,m)$ then $s(n)\ge m$.

Proof. Consider a graph whose vertices are the packed rectangles. Let any two vertices of the graph are adjacent by a red edge, if they can be separated by a vertical line and by a blue edge, if they can be separated by a horizontal line. Since any two packed rectangles can be separated either by a vertical or a horizontal line, each edge of the graph is either red or blue. Since $n\ge R(m,m)$, there are a (vertical or horizontal) direction and a set $S$ of $m$ packed rectangles such that any two distinct rectangles of $S$ can be separated by a line parallel to the direction. Then the segment, which are orthogonal projections of rectangles of $S$ parallel to the direction, have pairwise disjoint interiors. Thus the lines parallel to the direction and erected from the endpoints of the segment provided a grid with score $m$. $\square$

Since $R(3,3)=6$, Proposition 1 implies that $s(6)=3$.

Unfortunately, Proposition 1 provides weak asymptotic lower bounds for $s(n)$, because asymptotic bounds for $R(m,m)$ are exponential.

We can improve them by the following

Proposition 2. For any natural $n$, we have $s(n)\ge \sqrt{n}$.

Proof. Define a binary relation $<$ on the set $H$ of the horizontal projections of the packed rectangles, putting $I<I’$ if the right endpoint of the segment $I\in H$ lies at the left of (or coincides with) the left endpoint of the segment $I’\in H$. It is easy to check that $(P,\le)$ is a partially ordered set. Dilworth’s theorem implies that $H$ has either a chain of size at least $\sqrt{n}$ or an antichain $A$ of that size. In the former case similarly to the end of the proof of Proposition 1 we obtain a grid with score at least $\sqrt{n}$. In the latter case interiors of each two segments of $A$ intersect. Helly’s theorem implies that all interiors of the segments of $A$ have a common point. It follows that interiors of vertical projections of the rectangles horizontally projected to the segments of $A$ are pairwise disjoint, and we can proceed similarly to the former case. $\square$

Proposition 2 implies that $s(5)=3$.

Lemma 3. For each natural $a$, $b$, and $c$, we have $s(ab+2c)\le \max\{ab,a+c,b+c\}$.

Proof. The claim is provided by a packing consisting of $2c$ rectangles attached to a rectangle $a\times b$ partitioned into $ab$ squares with. See below an example for $a=3$, $b=2$, and $c=2$. $\square$

Proposition 4. For each $a\ge 2$ we have $s(3a^2-2a)\le a^2$.

Proof. In Lemma 3 put $a=b$ and $c=a^2-a$. $\square$