In the now-inactive (and very nice) "Tricki" website that describes various proof techniques, there is an article (written I think by Timothy Gowers) that describes the following Ramsey-type problem:

Given n axis-aligned rectangles in the plane, what is the largest m such that there are always either m disjoint rectangles, or m rectangles intersecting in one point. The given proof shows that $c \cdot \sqrt{n} / \log(n) \leq m \leq \sqrt{n}$.


It is mentioned that closing this gap is an open question. Where can this problem (and related background) be found in a research paper or book? Is it still open in this form or was there some progress on it?

  • 2
    $\begingroup$ I agree with bof, the inequalities should probably be $c\sqrt{n}/{\log n} \le m \le \sqrt n$. $\endgroup$ – Jan Kyncl Oct 3 '14 at 23:57
  • $\begingroup$ Sorry for the mistake, I updated the question. $\endgroup$ – László Kozma Oct 4 '14 at 21:40

There has been some research on a related problem, finding a smallest transversal for sets of rectangles with a given maximum number of disjoint rectangles. Small transversal implies many rectangles intersecting in one point, but not vice versa. The problem seems to be still open.

Here are some references:

Károlyi, On point covers of parallel rectangles, 1991

Fon-Der-Flaass and Kostochka, Covering boxes by points, 1993

Ahlswede and Karapetyan, Intersection Graphs of Rectangles and Segments, 2006

Akopyan, On Point Coverings of Boxes in $\mathbb{R}^d$, 2008

| cite | improve this answer | |

This is not a direct hit, I realize, but as no one else has offered a reference...

Mandal, Ritankar, et al. "Greedy is good: An experimental study on minimum clique cover and maximum independent set problems for randomly generated rectangles." arXiv preprint arXiv:1212.0640 (2012).

The Abstract, followed by Fig.2:


| cite | improve this answer | |
  • $\begingroup$ (While I was posting, Jan Kyncl posted several relevant references.) $\endgroup$ – Joseph O'Rourke Oct 4 '14 at 0:04
  • 1
    $\begingroup$ This just released, 2Oct2014: "A fractional Helly theorem for boxes," (arXiv abstract link). $\endgroup$ – Joseph O'Rourke Oct 4 '14 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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