Examples of $\aleph_0$-categorical nonhomogeneous structures
How about: dense linear order with endpoints.
It's $\aleph_0$-categorical by the same proof as for the case without endpoints.
It's not homogeneous because of the endpoints.
Here is my favorite example.
Theorem. Fix $n\geq 1$. Then there is a unique (up to isometry) countable metric space $(M_n,d)$ satisfying the following properties:
- $d(x,y)\in\{0,1,2,\ldots,n\}$ for all $x,y\in M_n$
- Any finite metric space with distances in $\{0,1,2,\ldots,n\}$ embeds as a subspace of $M_n$.
- Any partial isometry between two finite subspaces of $M_n$ extends to a total isometry of $M_n$.
I don't really know who to attribute this to (perhaps Casanovas & Wagner, or Delhomme, Laflamme, Pouzet, Sauer). The point is that the class of finite metric spaces with distances in $\{0,1,\ldots,n\}$ is a Fraisse class in an appropriate relational language, and so $M_n$ is the Fraisse limit. In particular, for all $k\leq n$, add a binary relation $d_k(x,y)$ interpreted as "$d(x,y)\leq k$". In this language, $M_n$ is homogeneous. But....
View $M_n$ as a graph under just the relation $d_1(x,y)$. Then $M_n$ is still $\aleph_0$-categorical because the metric is "definable" from the graph language using existential quantifiers. (Specifically, the defining properties of $M_n$ force the metric $d$ to coincide with the "path metric" given by distance $1$. E.g, $d(x,y)\leq 2$ iff $\exists z(d_1(x,z)\wedge d_1(z,y))$.) However, in the graph language, $M_n$ is homogeneous if and only if $n=1$ or $n=2$. Indeed, if $n\geq 3$ then we can find points $a,b,c,d\in M_n$ such that $d(a,b)=2$ and $d(c,d)=3$. In the graph language, the finite substructures $\{a,b\}$ and $\{c,d\}$ are isomorphic. But an automorphism of $M_n$ has to respect the metric, and so there is no automorphism sending $(a,b)$ to $(c,d)$.
The point, of course, is that by looking only at the distance $1$ relation, we lose quantifier elimination.
Note, on the other hand, $M_1$ is a countably infinite complete graph and $M_2$ is the countable Rado graph, both of which are homogeneous as graphs.
By the way, $M_n$ is an example of what is called a metrically homogeneous graph. For more on these, see Cherlin's work on the classification program for these graphs.