next up previous
Next: Problem 75: Edge-Coloring Geometric Up: The Open Problems Project Previous: Problem 73: Congruent Partitions


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(m2), 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)≤2m. 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.


next up previous
Next: Problem 75: Edge-Coloring Geometric Up: The Open Problems Project Previous: Problem 73: Congruent Partitions
The Open Problems Project - December 04, 2015