Tricki
a repository of mathematical know-how

Extra logarithmic factors

Quick description

Many proofs in many areas of mathematics, but especially in parts of number theory and combinatorics, give rise to bounds that have logarithmic terms. This article is about why that should be, and gives some examples of proofs where they arise. So far it has just one example. It would be good to have many more, demonstrating many different reasons for the appearance of log factors.

Example 1

An aligned rectangle is a rectangle in \mathbb{R}^2 with its sides parallel to the x and y axes. Suppose you have a collection of n aligned rectangles. What is the maximum value of m for which it is always possible to find either m disjoint rectangles in the collection or a point in \mathbb{R}^2 that is contained in m rectangles from the collection? For convenience we shall assume throughout the discussion that all rectangles are closed.

A simple example shows that m cannot be greater than \sqrt n: one simply takes \sqrt n sets of aligned rectangles and makes sure that two aligned rectangles in the same set intersect, while two aligned rectangles in different sets are disjoint.

Now let us match this lower bound with an upper bound that is the same—apart from a logarithmic factor.

First, if R is an aligned rectangle, let us define x_0(R) and x_1(R) to be the minimum and maximum x coordinates of points in R, respectively. Similarly, let y_0(R) and y_1(R) be the minimum and maximum y coordinates. (Thus, if R is closed, then it equals [x_0(R),x_1(R)]\times[y_0(R),y_1(R)]. Now, given any collection of n aligned rectangles, let X be the set of all real numbers that are equal to x_0(R) or x_1(R) for some R in the collection, and let Y be the same thing for y coordinates. Then the sizes of X and Y are both at most 2n.

Now whether or not two rectangles R and R' intersect depends solely on the ordering of the four numbers x_0(R), x_1(R), x_0(R') and x_1(R') and the ordering of the four numbers y_0(R), y_1(R), y_0(R') and y_1(R'). Therefore, we can replace the sets X and Y by \{1,2,\dots,m_1\} and \{1,2,\dots,m_2\} for two integers m_1 and m_2 that are both at most 2n.

What all this amounts to is that we can assume, without loss of generality, that the coordinates of the vertices of all rectangles in the collection are integers between 1 and 2n.

Now it turns out to be a lot easier to prove the result if all the rectangles have about the same size and shape. Here is an argument that shows that gives a lower bound of c\sqrt n for aligned squares. Let us form a graph whose vertices are the aligned squares, with an edge joining two vertices if those squares intersect. (If you are unfamiliar with graph theory terminology, then you can find it in Wikipedia's graph theory glossary.) If the maximum degree of any vertex in this graph is \sqrt n, then we can pick a sequence of vertices S_1,S_2,\dots,S_k, with no vertex joined to any previous one, provided that (k-1)\sqrt n<n, so certainly if k=\sqrt n. So in this case we have a collection of \sqrt n disjoint squares. But now suppose that there is a vertex of degree greater than \sqrt n. This will be a square S that overlaps with over \sqrt n other squares. Now each of those other squares must contain a vertex of the original square (this is the step that fails when the rectangles have different shapes), so a least one vertex of S must be contained in at least \sqrt n/4 rectangles, which completes the proof.

What can we do if we have rectangles? We can use the widely applicable trick of making everything roughly the same size. The widths of the rectangles lie between 1 and 2n, as do their heights. Let us partition the set \{1,2,\dots,2n\} into sets of the form 2^{k-1}\leq r<2^k\}. There are at most \log_2(2n)+1 of these sets, so we can find two of them, U and V say, and a set \mathcal{R} of at least n/(\log_2(2n)+1)^2 aligned rectangles taken from the original collection, such that the width of every rectangle in \mathcal{R} lies in U and the height lies in V.

This implies that the ratios of the widths and heights of any two rectangles in \mathcal{R} are at most 2. We now repeat the argument above for squares, except that this time when we have a rectangle R of degree at least \sqrt N (where N is the size of \mathcal{R}), we cannot argue that all rectangles that intersect R must contain a vertex of R. However, we can argue that any rectangle in \mathcal{R} that intersects R contains either a vertex of R or the midpoint of an edge or the centre of R. This makes nine possibilities, so we can obtain a lower bound of c\sqrt N. Since N is of the form cn/(\log n)^2, this gives a lower bound of the form c\sqrt n/\log n for the original problem.

This demonstrates one way in which stray logarithmic factors can arise: through an application of the make-everything-roughly-the-same-size trick.

It is often possible to be more careful and remove a logarithmic factor of this kind by avoiding the use of that trick and thinking hard about how to relate objects of different sizes. However, closing the gap between the above estimates is still an open problem.

Comments

Squares?

In the example proof, instead of squares, isn't it meant to be rectangles equal to each other? If squares are allowed to have different sizes, I don't think it is true that each neighbour of a square must overlap with one of its vertices.

A question: is there some reference for this problem and proof? I realize this problem asks for bounds on m in terms of n, where n=R(m,m) for intersection graph of rectangles. Was this studied for other special graphs?

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

Only if squares are of the

Only if squares are of the same size, no? It would also work for rectangles with same sizes, right?