The geometry of random objects.

Van H. Vu Department of Mathematics

University of California at San Diego vanvu@ucsd.edu The general question. What can one say about n random objects in the d-dimensional unit hypercube ?

One can, of course, replace the cube by another region or a discrete structure.

Examples.

(1) How many hyperplanes do one need to separate n random points in C^{d} ? (so that between any pair of points there is at least one hyperplane).

(2) Put n random boxes (whose edges are parallel to the axis) in C^{d}. How many points do we need to catch all of them ?

(3) Put n random boxes (whose edges are parallel to the axis) in C^{d}. How many lines do we need to intersect all of them ?

(4) Choose n random points from a finite projective plane. How many lines do we need to cover all these points. We introduce a general tool which can be used to provide an exact or almost exact answer to many problems of this type.

Separating random points. Sep(n, d). Consider d = 2. Trivially, almost surely

c\sqrt{n} ≤ Sep(n, 2) ≤ n − 1.

Somewhat surprisingly, it turns out that a.s.

Sep(n, 2) = Θ(\frac{n^{2/3}}{log^{1/3} n}).

Theorem 1. (Alon, Bollobás, Kim and V. 00) Almost surely, the number of hyperplanes one needs to separate n random points is Θ(\frac{n^{2/(d+1)}}{log^{1/(d+1)} n}).

Catching random boxes.

Theorem 2. (Sudakov and V. 02) Almost surely, the number of points one needs to catch n random boxes is between c_{1}\sqrt{n} and c_{2}\sqrt{n log log n}, where c_{1}, c_{2} are positive constants.

Coffman, Luecke, Spencer and Winkler consider M, the maximum number of mutually disjoint boxes, and showed (a.s)

c_{1}\sqrt{n} ≤ M ≤ c_{2}\sqrt{n log^{d−1} n}.

It is conjectured that the log is not needed (CLSW: true for d = 2). Theorem 2 implies (a.s)

c_{1}\sqrt{n} ≤ M ≤ c_{2}\sqrt{n log log n}.

The main tools.

H is a k-uniform hypergraph on n points. ν(H) (the matching number) is the maximum size of a matching; ρ(H) (the edge-covering number) is the minimum number of edges needed to cover all vertices. Trivially:

ρ(H) ≥ \frac{n}{k} ≥ ν(H).

Question. When do ρ(H) and ν(H) equal Θ(\frac{n}{k}), or even (1 + o(1))\frac{n}{k}?

The codegree C of H is the maximum number of edges containing a fixed pair of points. In general, the j-codegree of H is the maximum number of edges containing a fixed set of j points.

Rödl-Pippenger’s theorem. Assume that k is a CONSTANT and furthermore that H is D-regular and C = o(D), then ν(H) = (1 − o(1))\frac{n}{k}. Consequently ρ(H) = (1 + o(1))\frac{n}{k}.

Questions:

(1) How small is o(1) ? Estimate U(H), the number of vertices left uncovered by an optimal matching.

(2) What if k → ∞ ?

Theorem. (Alon, Bollobás, Kim, V. 00) For any k = o(log \frac{D}{C log(C+1)})

U(H) = O((\frac{C log C}{D})^{1/(k−1)}n).

Previous works for constant k: Alon-Kim-Spencer (C = 1), Kostochka-Rödl (general C, slightly weaker bound), V. (the same bound).

Corollary 1. If C = 1 and k = O(log D) then ρ(H) = O(n/k).

The bound log D on k is the right threshold. There is a hypergraph with C = 1, k = f log D and ρ(H) = Ω( \frac{n}{k} log f).

A very very rough analysis.

Pick each edge with probability θ/D. With a proper choice of θ, almost all edges picked are isolated and these form a partial matching. A vertex v remains with probability (1 − θ/D)^{D} ≈ 1 − θ. The number of vertices of the next hypergraph is n_{1} = n(1 − θ). An edge e containing v will count in the degree of v in the next hypergraph with probability (1 − θ)^{k−1}. So the next degree is D_{1} = D(1 − θ)^{k−1}. Repeat until D_{T} = D(1 − θ)^{T (k−1)} = Θ̃(C). We have

(1 − θ)^{T} = Θ̃(( \frac{D}{C})^{1/(k−1)}).

Therefore, the number of vertices remaining in the final hypergraph is

n_{T} = n(1 − θ)^{T} = nΘ̃(( \frac{D}{C})^{1/(k−1)}) = U(H).

Let us describe the above process by the following running race:

On the log scale, D and C are of distance log \frac{D}{C} apart. A runner (starting at D) runs toward an idle guy (staying at C) with velocity k − 1. The race ends when the two meet and the elapse time T determines U(H). (We lose control of the algorithms once the codegree is close to the degree.)

Observation. But the codegree C also runs !!!

We can have two runners, D = C_{1} and C = C_{2} and an idle guy at C_{3} (the codegree of three vertices). C_{1} runs with velocity k − 1, C_{2} with k − 2. If two guys meet, they stop. The race ends when D = C_{1} stops. Compared with the lone-runner race, the two-runner race clearly has a longer elapse time. In general, we have as many runners as codegrees which we can compute at the beginning, say C_{1}, …, C_{s}. The more runners, the better bound. Sometime, the initial positions of the runners might complicate the computation. The next idea is to use “phantom runners”. The phantom of C_{i} is C′_{i} is always on the left of C_{i} (C′_{i} ≥ C_{i}). This simplifies the calculation without too much loss.

The “multi-runners” theorem. (V. 99-02) U(H) is the determined by the time D = C_{1} hits the first (phantom) runner.

The theorem was proved for constant k in 1999. The same proof holds for any k with nominal modifications.

Corollary 2. If k = ϵ\frac{log n}{log log n}; D = C_{1} = n^{α} and \frac{C_{i}}{C_{i+1}} ≥ log^{100} n for all i = 1, 2, …, k − 1. Then U(H) = o(\frac{n}{k}) and ρ(H) = O(\frac{n}{k}).

Notice that ABKV’s (lone runner) theorem does not apply as ( \frac{C}{D})^{1/(k−1)} = ( \frac{1}{log^{100} n})^{log log n/ϵ log n} = Ω(1).

Separating points—2 dimension: Sep(n, 2) = Θ(\frac{n^{2/3}}{log^{1/3} n}).

Lower bound. Set R = \frac{n^{2/3}}{log^{1/3} n}. Consider a R × R grid splitting the unit square into R^{2} cells. A cell is bad if it contains two points. The number of points in a cell has Poisson distribution with mean n/R^{2}, so the probability that a cell is bad is p = \frac{n^{2}}{2R^{4}} e^{−n/R^{2}} ≈ \frac{n^{2}}{2R^{4}} .

The number of bad cells is ≈ R^{2}p ≈ \frac{n^{2}}{2R^{2}} .

But a line cannot intersect too many bad cells !!

A line l intersects at most 2R cells. The probability that at least k of them are bad is \binom{2R}{k}p^{k} ≤ ( \frac{e log n}{k})^{k} ≤ n^{−5} if k = 10 log n. So the number of lines needed to intersect all bad cells is at least

\frac{(n^{2}/2R^{2})}{10 log n} = \frac{n^{2/3}}{20 log^{1/3} n} .

Upper bound.

Naive assumption: The bad points are far apart within a cell so a line intersecting a bad cell likely separates the bad points.

Hypegraph H: Vertices are bad cells. Edges are lines which intersect k = log n/10 bad cells. The codegree is 1; The degree is a positive power of n. Recall Corollary 1. If C = 1 and k = O(log D) then ρ(H) = O(n/k).

A more refined argument: Split the bad cells into diadic classes according to the distance between the bad points. For each class, consider a hypergraph H_{i}. The ρ(H_{i})’s form a geometric sequence and their sum is dominated by the first term.

Covering boxes: 2 dimension.

Restrict to diadic boxes and do poissonization. A box with area x is activated with probability min(x^{2}n, 1). In particular, all boxes with area at least \frac{1}{\sqrt{n}} are activated. This implies the lower bound. Consider boxes with areas at least \frac{a}{\sqrt{n}}. It is a well-known fact in discrepancy theory that we need only O(a^{−1}\sqrt{n}) points to catch these “large” boxes. Consider all activated boxes with area A = \frac{b}{\sqrt{n}}, b ≤ a. The key point is to show that one can catch these boxes by O(b\sqrt{n} log log n) points. Together we need

O(a^{−1}\sqrt{n} + ∑_{b≥a,b diadic} b\sqrt{n} log log n) = O(a^{−1}\sqrt{n} + a\sqrt{n} log log n)

Choose a = \frac{1}{\sqrt{log log n}}.

Consider all boxes with fixed area A = b(\sqrt{n})^{−1}. There are Θ( \frac{\sqrt{n}}{b} log n) diadic boxes with this area. Each one is activated with probability nA^{2} = b^{2}, so Θ(b\sqrt{n} log n) boxes are activated. A box is of type i if the length of its vertical edge is 2^{−i}. There are O(log n) types. Each type is a tiling. Split the boxes into L = 100 log log n classes so that in each class, the difference between the types of two boxes is a multiple of L. Consider a class. Each class has Θ( \frac{b\sqrt{n} log n}{L}) activated boxes. A point is good (with respect to this class) if it is in exactly k = \frac{ϵ log n}{log log n} activated boxes, where ϵ is a small positive constant. Define a (dual) hypergraph as follows: The vertices are the activated boxes in the class. The edges are the good points. This hypergraph is k-uniform by definition.

The degree D = C_{1} is the number of good points in a box. The codegree C_{2} is the (maximum) number of good points in the intersection of two boxes; C_{3} is the (maximum) number of good points in the intersection of three boxes etc. By the way we choose the boxes in the class, the intersection of two boxes has area 0 (if they have the same type) or at most \frac{A}{2^{L}} = \frac{A}{log^{100} n}. So C_{1}/C_{2} ≥ log^{100} n. In general C_{i}/C_{i+1} ≥ log^{100} n. Now apply Corollary 2 (multi-runners). There is an economical cover using O( \frac{|V |}{k}) edges.

\frac{|V |}{k} = \frac{Θ( \frac{b\sqrt{n} log n}{L})}{k} = Θ(\frac{(b\sqrt{n} log n)/(log log n)}{log n/ log log n}) = Θ(b\sqrt{n}).

There are L = Θ(log log n) classes, so one needs Θ(b\sqrt{n} log log n) good points to catch all boxes.

How to prove the matching–covering theorems ? The key idea is to show that for all relevant i the codegree C_{i} really behaves as a runner, namely at any time j

C_{i}^{j} ≈ C_{i}(1 − θ)^{j(k−i)}.

This is a large deviation problem, we should prove that C_{i}^{j}’s are sharply concentrated around their expectations. However, standard tools (Azuma, Talagrand etc) fail as the Lipschitz coefficients are too large.

A new method: The polynomial method.

• Approximate C_{i}^{j} by low-degree polynomials.

• Show that the lower-degree polynomials are sharply concentrated.

Key advantages:

(1) The polynomials arise naturally.

(2) A polynomial is sharply concentrated EVEN when its Lipschitz coefficient is large. One only needs to look at the average Lipschitz coefficient (Kim-V. 1998, V. 00).

Example. Recall the very very rough analysis. Let t_{f} denote the event that the edge f is chosen; t_{f} is a binary random variable with mean θ/D. The event that a vertex u survives can be written as

∏_{f∋u}(1 − t_{f}).

If v ∈ e, then e counts in the degree of v in the next hypergraph if and only if all vertices in e\v survives. This event can be written as

∏_{u∈e\v} ∏_{f∋u}(1 − t_{f}).

Thus, the degree of v in the next graph is

D_{1} = ∑_{e∋v} ∏_{u∈e\v} ∏_{f∋u}(1 − t_{f}).

As

X^{−} ≤ ∏_{i=1}^{n}(1 − t_{i}) ≤ X^{+},

where X^{−} (X^{+}) is obtained from the expansion of ∏_{i=1}^{n}(1 − t_{i}) by truncating at a negative (positive) term, so D_{1} can be sandwiched between two low-degree polynomials.

http://www.math.ucsd.edu/ vanvu V.H. Vu, New bound on nearly perfect matchings in hypergraphs: Higher codegrees do Help. N. Alon, B. Bollobás, J.H. Kim, V.H. Vu, Economical covers with geometric applications.