Slick hyperfinite Ramsey theory proof

post by Alok Singh (OldManNick) · 2022-12-19T08:40:06.610Z · LW · GW · 3 comments

Contents

  Blog power laws
  Claim
  Proof
None
3 comments

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.

3 comments

Comments sorted by top scores.