How many countable graphs are there?

Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no axioms) over one unary relation.

How many isomorphism classes of countable models of the empty theory over one binary relation (a.k.a. graph theory) are there? I.e.: How many countable unlabeled graphs are there?

A handwaving argument might be: Since the number of unlabeled graphs with $n$ nodes grows (faster than) exponentially (as opposed to growing linearly in the case of a unary relation), there must be uncountably many countable unlabeled graphs. (Analogously to the case of subsets: the number of subsets of finite sets grows exponentially, thus (?) there are uncountably many subsets of a countably infinite set.)

How is this argument to be made rigorous?

-
Your argument is not an argument. The behavior of finite graphs doesn't necessarily tell you anything about infinite graphs. – Qiaochu Yuan Mar 16 '11 at 14:39
That's what I asked for! Your answer is: The argument cannot be made rigorous. That's interesting enough, since it seems to tell something. – Hans Stricker Mar 16 '11 at 14:47
@Qiaochu: Do you say, that there cannot be a proof of the uncountability of $P(\mathbb{N})$ based on the exponential growth of $|P([n])|$? I would like to understand that. – Hans Stricker Mar 16 '11 at 15:01
@Hans: what's to understand? There is no proof here. Your argument applies equally well to "graphs with a finite number of edges" but the conclusion is wrong in this case. – Qiaochu Yuan Mar 16 '11 at 15:06
@Qiaochu: Would you find it worth looking for an extra condition P such that "finite number grows exponentially AND P then uncountable"? – Hans Stricker Mar 16 '11 at 15:48

Another very simple way to show that they are uncountable is with well-orderings: By definition the well-orderings of a countable set are $\aleph_1$.

EDIT: Here's another simple way to show that they are $2^{\aleph_0}$ many. Take all but one (let's call it $p$) of the countable nodes and order them with the standard order of the natural numbers. This essentially assigns to every of these nodes a natural number. Now use the edgeless node $p$ that we kept to describe characteristic functions: For every subset $X$ of the natural numbers add an edge from the node that denotes $n$ to $p$ if and only if $n\in X$. It's trivial to see that all these graphs are not isomorphic: If two of them were then two different sets of natural numbers would coincide.

-

Here is one explicit way of producing continuum-many pairwise nonisomorphic (simple, undirected, loopless) graphs.

Start with a $3$-cycle among vertices labelled $-2,-1,0$. To the vertex $-1$ attach a tail (= path) of length $1$ and to the vertex $-2$ attach a tail of length $2$. Now, for each positive integer $n$, attach a tail of length $n$ to the vertex $0$, and label the terminal vertex in this tail $n$. (So we have some vertices that we have not labelled, but certainly only countably many of them.)

Now focus on the vertices marked $1,2,3,\ldots$: color the odd numbered ones red and the even numbered ones green. Consider the set of all possible bipartite graphs on this vertex set -- i.e., in which all edges connect red to green. There are clearly continuum-many: for instance even the independent choices of including / not including the edges $1--2$, $1--4$, $1--6$, and so forth gives a set of continuum cardinality. I claim that all of these graphs are pairwise nonisomorphic. Indeed, the only three cycle in any of them is formed by the vertices $-2,-1,0$, and it follows easily from this that any isomorphism between any two of these graphs carries $0$ to $0$, $-1$ to $-1$ and $-2$ to $-2$. From this it follows that for all $n \in \mathbb{Z}^+$, an isomorphism takes the vertex labelled $n$ to the vertex labelled $n$ and thus every vertex is fixed.

(By the way, I don't find the argument you suggest to be at all valid. I strongly suspect there are first order theories such that the number of nonisomorphic models of finite size $n$ grows at least exponentially with $n$ but for which there are only countably many isomorphism classes of countable models.)

Added: I want to make sure that the paths from $0$ to $n$ stay pairwise nonisomorphic when edges are added, so it's best to modify the construction slightly. For instance, call the penultimate vertex in the path $p_n$ and attach one more length one tail at $p_n$, so that now $p_n$ has degree $3$.

-
Qiaochu gave an example: graphs with a finite number of edges (even when this is not first order). – Hans Stricker Mar 16 '11 at 15:41
Might exponential growth in the finite case be a necessary condition? Or do you know counter examples? – Hans Stricker Mar 16 '11 at 15:45
@Pete: Would you find it worth looking for an extra condition P such that "finite number grows exponentially AND P then uncountable"? – Hans Stricker Mar 16 '11 at 15:49
@Pete: Could "faster than any exponential" suffice? What do you think? (see: math.stackexchange.com/questions/27382/…) – Hans Stricker Mar 16 '11 at 17:31
@Hans: Consider the problem of counting fields. For finite $n$, there is at most 1, but I claim there are uncountable many nonisomorphic countable fields. Namely, Let $P$ denote the primes and let $X\subseteq P$ be any subset. Consider $\mathbb{Q}$ with square roots of all the primes in $X$ adjoined. Each of these fields are countable, and it's not too hard to see that they are pairwise nonisomorphic. – Jason DeVito Mar 16 '11 at 17:43

One way is to construct an injection from $2^{\mathbb{N}}$ (or from some other uncountable set) to the set of countable graphs. There are many, many ways to do this.

Here's one way: I will construct a countable graph corresponding to a function $f: \mathbb{N} \rightarrow \{0,1\}$. The graph has vertices $y$ and $x_{n,i}$ for $n \in \mathbb{N}$ and $1 \leq i \leq n+1$. For each fixed $n$, we connect $x_{n,i}$ for all $i$ (in a chain as Alex suggests, or a loop, or a complete graph-- any will work). Then we add an edge from $y$ to $x_{n,1}$ if $f(n)=1$.

This is indeed an injection; we can recover $f$.

Edit: At first I had a multigraph construction, with multiple edges to each vertex, which is not what the question wanted. I have modified the construction to make a simple graph.

-
How do I connect two nodes by multiple edges? (I didn't want to allow multiple edges.) – Hans Stricker Mar 16 '11 at 14:28
Note that the OP wants simple graphs (corresponding to a binary relation). It shouldn't be hard to modify your construction accordingly. (I have another construction in mind, but it seems more complicated than yours...) – Pete L. Clark Mar 16 '11 at 14:29
You could just more vertices in between $y$ and $x_n$ to break up each edge, which I don't think would interfere with the isomorphism classes. – Alex Becker Mar 16 '11 at 14:31

I assume you mean by countable graph one that is countably infinite. I will also assume that your relation can be an arbitrary binary relation and not just symmetric since you seem to be interested in that case.

In this case there are uncountably many. For, a special case of a binary relation is a total order. We do not need to add anything to the theory to have a total order; it's just a special case and ordering will be preserved by isomorphism. There are uncountably many nonisomorphic orders on a totally ordered set.

Indeed let $N$ be the natural numbers. Let $S$ be a subset of $N$. Replace each $s\in S$ by a copy of $\mathbb{Q}\cap [0,1]$ where $\mathbb{Q}$ are the rationals. It's easy to show that if $S\not = T$ then you will get nonisomorphic orders this way. But there are uncountably many subsets of $N$.

So there are uncountably many orders on a countable set.

-
What is $T$? – Hans Stricker Mar 16 '11 at 14:33
Oh, it's short for the theory. – Jason Polak Mar 16 '11 at 15:51

Here is a bijection between $[0,1) \subset \mathbb{R}$, which is uncountable, and a pairwise non-isomorphic collection of countably infinite graphs:

For $x \in [0,1)$, let $0.x_1 x_2 x_3 ....$ be its unique decimal expansion (so $0\le x_i<10$ for each $i$, and no expansion ends in infinitely many 9's). Construct the graph $G_x$ as follows: start with the 3-cycle on $\{a,b,c\}$; attach the infinite chain $(a,1,2,3,...)$ to node $a$; and attach a chain of length $x_i$ to each node $i \ge 1$.

A minimal modification of this (use chain length $x_1 x_2 ... x_i$ in place of $x_i$) gives a bijection that preserves the order relation: $G_x$ is a subgraph of $G_y$ if and only if $x \le y$.

-

You might be interested in a related, but quite different, question. Suppose we choose the edges of a countable graph randomly, according to some probability $p$. How many different graphs do we expect to get, if we repeat the experiment several times?

You might think that every time we'll get a different graph, but in fact, with probability $1$ the graph generated will be isomorphic to the so-called Rado graph. This is the same graph immaterial of the probability $p$, and you even get the same graphs if the probabilities decay not too fast (under some arbitrary $\omega$-ordering of the edges).

The charming proof is an illustration of the back-and-forth argument - check it out.

-

In Wilfrid Hodges "Model Theory", p. 355, I found as an exercise:

(c) if L is the signature with one binary relation symbol, there are continuum many non-isomorphic ultrahomogeneous $\omega$-categorical structures of signature L.

which seems a little bit stronger: ultrahomogeneous and $\omega$-categorical!

-