## 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 with its sides parallel to the and axes. Suppose you have a collection of aligned rectangles. What is the maximum value of for which it is always possible to find either disjoint rectangles in the collection or a point in that is contained in rectangles from the collection?

A simple example shows that cannot be greater than : one simply takes 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 is an aligned rectangle, let us define and to be the minimum and maximum coordinates of points in , respectively. Similarly, let and be the minimum and maximum coordinates. (Thus, if is closed, then it equals . Now, given any collection of aligned rectangles, let be the set of all real numbers that are equal to or for some in the collection, and let be the same thing for coordinates. Then the sizes of and are both at most .

Now whether or not two rectangles and intersect depends solely on the ordering of the four numbers , , and and the ordering of the four numbers , , and . Therefore, we can replace the sets and by and for two integers and that are both at most .

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 and .

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 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 , then we can pick a sequence of vertices , with no vertex joined to any previous one, provided that , so certainly if . So in this case we have a collection of disjoint squares. But now suppose that there is a vertex of degree greater than . This will be a square that overlaps with over 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 must be contained in at least 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?

### 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?