# Andy's Math/CS page

## Tuesday, October 09, 2007

### Random Freaky Facts

While it may not be at all apparent, I've been somewhat particular about the types of posts I make to this blog. I've realized, however, that there should be no real harm in loosening up, and it'd probably increase my post frequency. So today, let me report two theorems that caught my eye in recent weeks. If I had to find a common theme, it'd be: finding interesting constraints in seemingly very unconstrained settings.

1) Let G be an infinite (undirected, simple) graph. Let the 'density' d(H) of a finite subgraph H of G be the fraction of pairs of vertices (u, v) from H that are connected by an edge. Let the 'upper density' d*(G) of G be the greatest number p such that we can find arbitrarily large finite subgraphs H, with d(H) as close as desired to p.

(i.e. for all n, epsilon there exists an H with |H| > n, d(H) > p - epsilon.)

Then, bizarrely, d*(H) must be one of the following numbers: {0, 1, 1/2, 2/3, 3/4, 4/5, 5/6, ...}

This result follows from the 'Erdos-Stone Structure Theory', generalizing Turan's Theorem in extremal graph theory. It is presented, in context, in Bollobas' excellent textbook 'Modern Graph Theory'. Basically, the idea is that, if H is large enough and of density greater than, e.g., 5/6 + epsilon, it must contain a particular subgraph H', of density 6/7.

2) Let X be a probability distribution over R^d. Choose d+1 points independently, each distributed as X. Then the probability p that their convex hull contains the origin, cannot exceed (1/2)^d.

Wild!

Unfortunately, I forget where I saw this last one, or who it's due to, but if I find out I'll attribute it here. I'm, uh, 90% sure I've got the numbers in the statement correct.

Labels:

• I don't get the first one. If G has even a single edge (v, w), then if we take H to be the subgraph with vertices {v,w}, we get d(H) = 1, and consequently, d*(G) >= 1. If G has no edges, then d*(G) = 0. This would suggest 0 < d*(G) < 1 cannot occur. Where did I go wrong?

By  Anonymous, at 3:53 PM

• Diestel (exercise on page 189) gives a slightly more technical definition of upper density that may answer the anonymous question: the upper density of an infinite graph G is the infimum of all reals alpha such that the finite graphs with density greater than alpha have bounded order.

By  D. Eppstein, at 4:30 PM

• Sorry, anonymous, my fault. I changed the wording to reflect the (necessarily more complex) intended statement.
Prof. Eppstein's definition also works.

By  Andy D, at 4:48 PM

• Ah, I see. Neat result indeed!

By  Anonymous, at 5:47 PM

• The second one is a doozy.

And the first one is very typical of combinatorics, and seems like a weird sort of threshold phenomenon. Either you're here, or you're there, no in-between.

Maybe the intuition is that when you're dealing with an infinite graph and take an asymptotic parameter, then it looks like every substructure essentially either does not appear at all, or appears infinitely often.