The Open Problems Project

Next: Problem 75: Edge-Coloring Geometric Graphs

Previous: Problem 73: Congruent Partitions of Polygons

Problem 74: Slicing Axes-Parallel Rectangles

Statement

Let us say that two rectangles in the place are independent if both their x- and y-axis projections are disjoint. A set of rectangles is then independent if the rectangles are pairwise independent. Suppose that a collection of axes-parallel rectangles contains no independent set of size m or greater. What is the minimal number, f(m), of horizontal and vertical lines needed to slice every rectangle in the collection?

Origin

Vincent Vatter, Jun 2009.

Status/Conjectures

It was known that f(m) exists and is at most exponential. An advance was made in 2010 by Werner and Lenz, who established a quadratic upper bound, O(m^2), in [WL10]. They also uncovered a long history of the problem under other names, e.g., “d-separated interval piercing.” In fact, the result was already established by Tardos and Karolyi earlier. See the cited paper for more details.

But, as pointed out by Pablo Soberón, apparently an earlier result [Kai97], Thm. 1.4, established f(m) \le 2 m. This largely solves the problem.

Partial and Related Results

The problem arises in the study of permutation classes, see [Vat08], where it was proved that f(m) exists and is at most exponential.

Categories

combinatorial geometry

Entry Revision History

V. Vatter, 24 June 2009; J.O’Rourke, 16 Mar. 2012; P. Soberón, 3 May 2012.

Bibliography

[Kai97]

T. Kaiser. Transversals of d-intervals. Discrete Comput. Geom., 18(2):195–203, 1997.

[Vat08]

Vincent Vatter. Small permutation classes. arXiv:0712.4006v2 [math.CO], 2008.

[WL10]

Daniel Werner and Matthias Lenz. Polynomial bounds on the rectangle slicing number. CoRR, abs/1004.3381, 2010. http://arxiv.org/abs/1004.3381.