4
$\begingroup$

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?

$\endgroup$
2
  • 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, 2014 at 23:57
  • $\begingroup$ Sorry for the mistake, I updated the question. $\endgroup$ Oct 4, 2014 at 21:40

2 Answers 2

5
$\begingroup$

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

$\endgroup$
1
3
$\begingroup$

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:


GreedyIsGood
                  Fig.2


$\endgroup$
2
  • $\begingroup$ (While I was posting, Jan Kyncl posted several relevant references.) $\endgroup$ Oct 4, 2014 at 0:04
  • 1
    $\begingroup$ This just released, 2Oct2014: "A fractional Helly theorem for boxes," (arXiv abstract link). $\endgroup$ Oct 4, 2014 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.