6
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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$. $\endgroup$ Commented Jan 13, 2018 at 20:43
  • 1
    $\begingroup$ Well I can make antichain with 320 rectangles. Take the rectangles 6x1,5x2and 4x3 $\endgroup$
    – nonuser
    Commented Jan 13, 2018 at 20:44
  • 1
    $\begingroup$ I was thinking about de Bruijn-Tengbergen-Kruyswijk theorem, but I don't know how to use it. $\endgroup$
    – nonuser
    Commented Jan 13, 2018 at 20:49
  • 1
    $\begingroup$ Are you interested in any brute force proof by computer code? $\endgroup$
    – 2'5 9'2
    Commented Jan 19, 2018 at 6:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – 2'5 9'2
    Commented Jan 19, 2018 at 6:55

3 Answers 3

3
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – nonuser
    Commented Jan 20, 2018 at 21:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 20, 2018 at 21:22
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .