Next: Problem 75: Edge-Coloring Geometric Graphs
Previous: Problem 73: Congruent Partitions of Polygons
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?
Vincent Vatter, Jun 2009.
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.
The problem arises in the study of permutation classes, see [Vat08], where it was proved that f(m) exists and is at most exponential.
V. Vatter, 24 June 2009; J.O’Rourke, 16 Mar. 2012; P. Soberón, 3 May 2012.
T. Kaiser. Transversals of d-intervals. Discrete Comput. Geom., 18(2):195–203, 1997.
Vincent Vatter. Small permutation classes. arXiv:0712.4006v2 [math.CO], 2008.
Daniel Werner and Matthias Lenz. Polynomial bounds on the rectangle slicing number. CoRR, abs/1004.3381, 2010. http://arxiv.org/abs/1004.3381.