A cute combinatorial result of Santaló

There is a nice result due to Santaló that says that if a (finite) collection of axis-parallel rectangles is such that any small subcollection is aligned, then the whole collection is aligned. This is kind of surprising at first, because the condition only says that there is a line, but this line might be different for any choice of subcollection. The precise statement is as follows:

Theorem. Let \mathcal{R} be a collection of rectangles with sides parallel to the axes (possibly intersecting). If for every choice of 6 rectangles of \mathcal{R} there exists a line intersecting all 6 of them, then there exists a line intersecting all rectangles of \mathcal{R} at once.

To be precise, I should clarify that by line intersection it is meant intersection with the interior of the rectangle – so a line touching only the boundary is not allowed. The number 6 doesn’t have any special esoteric meaning here, to the best of my understanding – it just makes the argument work.

The proof of this result is by induction on the number N of rectangles. If N = 6 then the result trivially holds, so let N+1 > 6 and suppose the theorem is true for any collection \mathcal{R} of N rectangles satisfying the property that for every choice of 6 rectangles of \mathcal{R} there exists a line intersecting all 6 of them.
We let \mathcal{R} = \{R_1, R_2, \ldots, R_{N+1}\}. For every rectangle R_j, by inductive hypothesis there exists a line \ell_j that intersects every rectangle in the collection \mathcal{R} \backslash \{R_j\}. If one of these intersects R_j itself then we are done, so we assume that each \ell_j does not intersect R_j (but it intersects every other rectangle; in particular, it intersects N rectangles of \mathcal{R}). We will argue by a bit of convexity that there must be a line \ell (in general distinct from the lines \ell_j) that crosses everyone of the N+1 rectangles at once.
We assume for simplicity that none of the lines \ell_j are horizontal (if there are horizontal ones, just add a small perturbation to their slope). In this case we can write down the equation of each line as
\ell_j : \qquad x + b_j y + c_j = 0.
Select four distinct indices j_1, j_2, j_3,j_4 such that b_{j_1}, b_{j_2}, b_{j_3},b_{j_4} all have the same sign (thus the corresponding lines are either all pointing upward or all pointing downward). Notice that you can do this because there are at least 7 lines – here is where that number 6 in the statement comes from. The two cases are treated in the same way, so assume that the lines are all pointing downward – that is b_{j_1}, b_{j_2}, b_{j_3},b_{j_4} are all positive. Now consider a non-trivial solution to the system of equations

\displaystyle \begin{aligned} \lambda_{j_1} + \lambda_{j_2}+ \lambda_{j_3}+ \lambda_{j_4} &= 0 \\ b_{j_1}\lambda_{j_1} + b_{j_2}\lambda_{j_2}+ b_{j_3}\lambda_{j_3}+ b_{j_4}\lambda_{j_4} &= 0 \\ c_{j_1}\lambda_{j_1} + c_{j_2}\lambda_{j_2}+ c_{j_3}\lambda_{j_3}+ c_{j_4}\lambda_{j_4} &= 0. \end{aligned}

Some of the \lambda_{j_k} will be positive, some will be negative (some might be 0 – deal with that case separately). Assume for simplicity that \lambda_{j_1}, \lambda_{j_2} are positive and \lambda_{j_3}, \lambda_{j_4} are negative – the other cases being all similar. We claim that the line \ell of equation

\displaystyle \ell : \qquad (\lambda_{j_1} + \lambda_{j_2})x + (b_{j_1}\lambda_{j_1}+ b_{j_2} \lambda_{j_2})y + (c_{j_1}\lambda_{j_1}+ c_{j_2} \lambda_{j_2}) = 0 \ \ \ \ \ (1)

intersects all N+1 rectangles of \mathcal{R} at once.
Observe that the equation of \ell can be rewritten in terms of \lambda_{j_3}, \lambda_{j_4}, namely

\displaystyle (-\lambda_{j_3} + \lambda_{j_4})x + (-b_{j_3}\lambda_{j_3}- b_{j_4} \lambda_{j_4})y + (-c_{j_3}\lambda_{j_3}- c_{j_4} \lambda_{j_4}) = 0. \ \ \ \ \ (2)

Now, let j \in \{1, \ldots, N+1\} be the index of a rectangle in \mathcal{R}. R_j intersects every line \ell_{i} with i \neq j, so for every such i we can find a point p^{(j)}_i in (the interior of) R_j, of coordinates (x^{(j)}_i, y^{(j)}_i), such that p^{(j)}_i \in R_{j} \cap \ell_i; in coordinate terms, for every i \neq j

\displaystyle  x^{(j)}_i + b_i y^{(j)}_i + c_i = 0.

Now, the index j cannot belong to both sets \{j_1, j_2\}, \{j_3, j_4\} at once; let’s assume that j does not belong to \{j_1, j_2\}. Consider then point q^{(j)} given by the following convex combination of coordinates of p^{(j)}_{j_1} and p^{(j)}_{j_2} :

\displaystyle q^{(j)} = \Big( \frac{\lambda_{j_1} x^{(j)}_{j_1}+ \lambda_{j_2} x^{(j)}_{j_2}}{\lambda_{j_1}+\lambda_{j_2}}, \frac{b_{j_1}\lambda_{j_1} y^{(j)}_{j_1}+ b_{j_2}\lambda_{j_2} y^{(j)}_{j_2}}{b_{j_1}\lambda_{j_1} + b_{j_2}\lambda_{j_2} }\Big).

Notice how the weights have been chosen. Because the coordinates are convex combinations of the coordinates of two points in R_j , the point q^{(j)} itself belongs to R_j (however, they are convex combinations with distinct weights for the two coordinates; thus this is only true if the set is a rectangle, and not just a convex set more in general!). Moreover, it’s immediate to see by substitution that q^{(j)} satisfies equation (1), and therefore \ell intersects (the interior of) R_j. Repeat the argument for all j‘s to conclude (notice, if j had belonged to \{j_1, j_2\} we would have used \lambda_{j_3},\lambda_{j_4} and equation (2) to reach the same conclusion). \square

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s