I’m not yet back to full-blown quasi-daily blogging.  But I couldn’t resist this all the same.

Edit: I am embarrassed to admit that I used the wrong terminology in the first version of this entry.  I said “discrete graph” for null graph.  Whoops.

I recently learned about a version of Ramsey’s theorem in combinatorics:

Let $m \in \mathbb{N}$.  There is $r$ such that if $G$ be a graph with more than $r$ vertices, then $G$ contains either a null subgraph of size $m$ or a complete subgraph of size $m$.

One of the interesting applications of model theory is that this (finitary) version of Ramsey’s theorem can be proved using the simpler infinite Ramsey theorem.  There are other such applications, e.g., using the regular Nullstellensatz to prove one with bounds on the coefficients.  The idea is similar to the theorem of Robinson that a sentence of first-order logic holding in fields of characteristic zero must hold in fields of all but finitely many characteristics.   All this abstract nonsense (OK, it’s not technically category theory, but it has the same feel) deserves its own post at some point.

I don’t have time for a full post that explains all this, but I found the infinite Ramsey theorem an interesting problem in itself.

Let $G$ be an infinite graph.  Then $G$ contains either an infinite complete subgraph or an infinite null subgraph.

To prove this, let $V_{fin}$ be the collection of vertices that are connected to only finitely many other vertices.

1) If $V_{fin}$ is infinite, we may construct a null subgraph is follows.  Choose $v_1 \in V_{fin}$; then choose $v_2 \in V_{fin}$ not one of the finitely many points connected to $v_1$; then $v_3 \in V_{fin}$ not connected to $v_1, v_2$.  The infiniteness of $V_{fin}$ allows this process to continue indefinitely.

2) If $V_{fin}$ is finite, we may assume wlog that for any infinite subgraph $G' \subset G$, the analogous set $V'_{fin}$ is finite (or we could use the previous reasoning applied to $G'$).   Now choose $v_1 \in V - V_{fin}$, which is connected to infinitely many vertices that form a subgraph $G_1$; then each vertex of $G_1$ is connected to $v_1$.  Also, because $V^1_{fin}$ (the analog of $V_{fin}$ for $G_1$) is finite, we can choose $v_2 \in G_1$ connected to infinitely many points of $G_1$.  Then define $G_2 \subset G_1$ to be the subgraph of $G_1$ consisting of points connected to $v_2$.  Repeating this process, one obtains an infinite sequence $v_1, v_2, \dots$ such that $v_n$ is connected to $v_1, \dots, v_{n-1}$ (by virtue of belonging to $G_n \subset G_{n-1} \subset \dots \subset G_1$), which is thus a complete subgraph.