# Least greedy square

There are $n$ squares of $m$ different colors. Squares of the same color are interior disjoint, but squares of different colors may intersect.

For every square, define its "greed" as the maximum number of squares of a single color that it intersects. For example, in the figure below, the top-left red square has a greed of 1 because it intersects 1 green square; the bottom-right red square has a greed of 4 becaues it intersects 4 green squres (in addition to 1 blue square); the other two red squares have a greed of 2.

MY QUESTION IS: What is the minimum greed that a single square can have, in the worst case?

4 is an upper bound, because the smallest of all squares has a greed of at most 4. This is because, when a square intersects a larger square, at least one corner of the smaller square must be covered. Since a square has 4 corners, it can intersect at most 4 larger squares that are disjoint, i.e., at most 4 squares per color.

2 is a lower bound, as shown by the construction below, where all squares have a greed of 2:

So, the question is whether there is always a square with a greed of at most 2? Or at most 3?

-
Why could a large red square not intersect, say, 15 blue squares, all lined up along its right-hand edge, but not intersecting each other? Perhaps you need to be clearer for us on what the constraints on the squares might be. – John Hughes Jan 16 '14 at 20:43
Or, what if all squares have distinct interiors? – Eddie E. Jan 16 '14 at 20:43
@John If I understand the problem correctly, then the question is on $$\sup_{\text{instance }I}\quad\min_{\text{square } s \in I}\quad\mathrm{greed}(s).$$ – dtldarek Jan 16 '14 at 20:44
@HagenvonEitzen yes. In other words: Is there an arrangement of squraes where each square intersects at least 3/4 squares of at least one other color? – Erel Segal-Halevi Jan 16 '14 at 20:59
@Listing The question stipulates that they must be squares, i.e. side lengths are equal. – Eddie E. Jan 16 '14 at 22:10

Partial solution: Here is an example for lowerbound of $\mathbf{3}$:

and my hypothesis is that this is it (assuming finite number of squares and colors).

I hope this helps $\ddot\smile$

-
Nice! Now it only remains to check the case of 4. – Erel Segal-Halevi Jan 18 '14 at 21:03
The case of 4 is probably worth a new question: math.stackexchange.com/questions/646150/… – Erel Segal-Halevi Jan 21 '14 at 12:28