# open question on intersecting rectangles - reference request

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

http://www.tricki.org/article/Extra_logarithmic_factors

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?

• I agree with bof, the inequalities should probably be $c\sqrt{n}/{\log n} \le m \le \sqrt n$. Oct 3, 2014 at 23:57
• Sorry for the mistake, I updated the question. Oct 4, 2014 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

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:

• (While I was posting, Jan Kyncl posted several relevant references.) Oct 4, 2014 at 0:04
• This just released, 2Oct2014: "A fractional Helly theorem for boxes," (arXiv abstract link). Oct 4, 2014 at 13:40