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