Blog power laws
My dissection post is 80% of this blog’s traffic. Before writing that, 80% of traffic came from Vim’s conceal feature.
The math posts are almost never read, which is depressing because they’re the ones with the least obvious insights. The few that do read them tend to really like them.
This post isn’t going to buck that trend, since it won’t make sense unless you already know nonstandard analysis, and this isn’t going to be the post that teaches you nonstandard analysis either.
Claim
Let g be a graph where every finite subgraph is n-colorable. Then the whole graph g is n-colorable.
Proof
If g is finite, then the whole thing is trivial because g is a finite subgraph of itself and is n-colorable by hypothesis, and we’re done.
Now assume g is infinite. Construct g*, the nonstandard extension of g. It is a fact (which I don’t prove but appeal to Joel David Hamkins) that any infinite structure can be embedded inside a larger hyperfinite one. The trick of approximating an infinite thing by a larger hyperfinite one is called hyperfinite approximation. In this case, we construct H, a hyperfinite subgraph of g* that contains g
In symbols: $$g \subseteq H \subseteq g^*$$.
$$H$$ is $$n$$-colorable, because all finite subsets of $$g$$ are, so by the Transfer Principle all (hyper)finite subsets of $$g^*$$ are too, including $$H$$.
But $$g$$ is contained in $$H$$, so it can’t require more colors than $$H$$ does. Therefore, $$g$$ is $$n$$-colorable $$\QED$$.
This is the Compactness Theorem in disguise because “all finite substructures” carry over to the whole infinite structure.
A few disjointed remarks:
Your mathematics hasn’t come over to LW. LW does support LATEX in posts and comments (as I have just demonstrated) but doesn’t pull it in automagically from blogs that use MathJax or whatever.
I like the proof!
But when I read the statement being proved, my immediate thought was “isn’t this just going to be a compactness theorem thing?” and it’s not obvious to me that going via nonstandard analysis really makes it slicker.
iLate reply, but the slicker bit is going in more fully. The appeal of the NSA approach here is axiomatizing it which helps people understand because people already know what numbers are, so ‘inf big’ is much less of a stretch than going the usual crazy inference depth math has.
I enjoyed being pleasantly surprised how much I could actually follow the point.
For those that are interested I did not the all the way throught because i don’t (yet) understand how you take a power (set) on a graph.