Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

enter image description here

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:

enter image description here

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

share|improve this question
2  
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 Jan 16 at 20:43
    
Or, what if all squares have distinct interiors? –  Eddie E. Jan 16 at 20:43
1  
@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 at 20:44
1  
@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 at 20:59
1  
@Listing The question stipulates that they must be squares, i.e. side lengths are equal. –  Eddie E. Jan 16 at 22:10

1 Answer 1

up vote 3 down vote accepted

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

squares

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

I hope this helps $\ddot\smile$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.