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 is known that f (m) exists and is at most exponential.

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

Bibliography

Vat08

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