Tricki
a repository of mathematical know-how

Revision of Extra logarithmic factors from Mon, 15/12/2008 - 22:57

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.

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?

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.

Parent article

Which techniques lead to which kinds of bounds?

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?