open question on intersecting rectangles - reference request

Question

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?

Answer 1

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

Answer 2

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

• arXiv abs
• PDF download

The Abstract, followed by Fig.2:

---

---

                 

---