Slick hyperfinite Ramsey theory proof


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.

Related Posts

My biggest takeaway from Redwood Research REMIX

finite, actual infinity, potential infinity

Actions and Flows

PSA: reward is part of the habit loop too

a kernel of lie theory

The hyperfinite timeline

Gaoxing Guy

What it's like to dissect a cadaver

A Prince, a Pauper, Power, Panama

Braindead Way to Derive Taylor Series of Exponential Function