# $551$ rectangles are selected from a $10\times 10$ square. Prove that one of these rectangles is inside another one (they can have common side).

I'm actually looking for a solution of extension of this problem:

We have a set $$M = \{(x,y)\in \mathbb{Z}^2; 0\leq x,y\leq 10\}$$

Let $$P$$ be a subset of rectangles with vertices in $$M$$ and with sides parallel to coordinate axis. What is the smallest cardinality of $$P$$ that we can find for sure in $$P$$ two rectangles $$R$$ and $$R'$$ such that $$R\subseteq R'$$?

Proof for $$551$$: Every rectangle is uniquely determined with two parallels with x-axis and two parallel with y-axis. Since we have $$11$$ parallel lines with x-axis, we can chose those on $${11\choose 2}=55$$ ways. So we have two parallels to x-axis with at least $$11$$ rectangles with sides on these two parallels.

Now let us observe only these $$11$$ rectangles. Each is uniquely determined with their left and right side. Since we have $$11$$ rectangles and only $$10$$ possibilities we have two of them with left side on the same parallel to y-axis. So one of those includes the other one and we are done.

• Working on the opposite direction, it is pretty simple to show that there is a Sperner family with $286$ rectangles. It is enough to consider all the possible rectangles with dimensions $1\times 11 (\text{columns}), 2\times 10, 3\times 9, 4\times 8,5\times 7,6\times 6,7\times 5,\ldots, 11\times 1(\text{rows})$. We have $\sum_{k=1}^{11}k(12-k) = 2(12^2-1)=286$. Commented Jan 13, 2018 at 20:43
• Well I can make antichain with 320 rectangles. Take the rectangles 6x1,5x2and 4x3 Commented Jan 13, 2018 at 20:44
• I was thinking about de Bruijn-Tengbergen-Kruyswijk theorem, but I don't know how to use it. Commented Jan 13, 2018 at 20:49
• Are you interested in any brute force proof by computer code? Commented Jan 19, 2018 at 6:40
• I believe there are $55^2=3025$ such rectangles. The algorithm would not need to look at all $2^{3025}$ subsets. Since there is the obvious poset ordering, the brute force search could go fast if the algorithm starts by mapping the poset structure. Commented Jan 19, 2018 at 6:55

Proof for $386$.

For $R,S$ rectangles, define $R\sim S$ if and only if all these three requirements holds:

1. $R\subseteq S$ or $S\subseteq R$;
2. $R,S$ have the same left-down corner, say at position $(x,y)$;
3. if $y\leq x$ then $R,S$ have the same base, otherwise the same height.

Then $\sim$ is an equivalence relation, its equivalence classes are chain of rectangles. The number of equivalence classes is given by $$\sum_{n=1}^{10}\sum_{m=1}^{10}\min\{n,m\}=385$$ because for each pair $(n,m)$ there are exactly $\min\{n,m\}$ equivalence classes whose rectangle have left corner at position $(10-n,10-m)$.

Since an antichain shares with each equivalence class at most a rectangle, it follows that each antichain contains at most $385$ rectangles.

• Do you think you can upgrade your idea. To redefine this relation to get smaller number of equivalence classes, so that some of them contains more chains with pairwise empty intersection. Commented Jan 20, 2018 at 21:14
• Yes, I'm trying to enlarge equivalence classes in order to reduce their number. On the other hand I'm also trying to obtain an antichain by choosing suitable ractangles from each class. Commented Jan 20, 2018 at 21:22

A quick and dirty calculation can get the maximum down to 495.

As the 551 calculation shows, for a given $a<b$ there are at most 10 rectangles in $P$ with base at height $a$ and top at height $b$. That argument also showed that no 2 of the rectangles have the same left side and no 2 of them have the same right side.

If, for each $a$ and $b$, there are at most 9 rectangles in $P$ with base at height $a$ and top at height $b$, then $|P|\leq {11\choose 2}9=495$.

Now consider an $a<b$ such that there are 10 rectangles with base at height $a$ and top at height $b$. Since they all have different left sides and different right sides, each of the values 0,1,...9 is a left side and each of the values 1,2,...10 is a right side. This implies each rectangle is 1 by 1. Thus every remaining rectangle in $P$, other than these 10, either has base $>a$ or height $<b$ (otherwise it would contain one of these 1 by 1 rectangles). So the collection of possible pairs $(a',b')$ such that there is a rectangle with base at height $a'$ and top at height $b'$ is ${11\choose 2}-(11-b)(a+1)+1$. Thus the size of a set of of rectangles in which there are 10 with base at height $a$ and top at height $b$ is $\leq 10({11\choose 2}-(11-b)(a+1)+1)$. The $a$ and $b$ that maximize this are $a=0$, $b=10$, where the above bound is 496. But certainly we can't get all 496 of these, because then we'd have lots of other values $a'$ and $b'$ giving us 10 rectangles with base at height $a'$ and top at height $b'$, and $10({11\choose 2}-(11-b')(a'+1)+1)<496$. So our upper bound on $|P|$ when there are 10 rectangles with base at height $a$ and top at height $b$ is 495.

A partial answer, pointing towards a hopefully promising direction.

Working on the opposite direction, is is pretty simple to show that there is a Sperner family with $220$ rectangles. It is enough to consider all the possible rectangles with dimensions $1\times 10 (\text{columns}), 2\times 9, 3\times 8, 4\times 7,5\times 6,6\times 5,,\ldots, 10\times 1(\text{rows})$.

Let us assume to have a Sperner family of rectangles and let us define the weight of a rectangle as the sum of its dimensions. Let us say that a Sperner family is homogeneous if all its elements have the same weight, dishomogeneous otherwise.

Reasonable conjecture: the largest Sperner family is homogenous. We may consider a rectangle $R$ and the set of rectangles which partially overlap with it (neighbourhood $U$). Reasonable attempt: if the weight of an element $S$ of $U$ is larger than the weight of $R$, we may suitably resize $S$ and rearrange the neighbourhood of $S$ by preserving the Sperner property.

Statement with a straightforward proof by inspection: the largest homogeneous Sperner family has weigth $7$ and $320$ elements.

Conclusion: if we take $321$ rectangles or more, at least two of them fulfill $R_1\subset R_2$ or $R_2\subset R_1$.