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.