7
$\begingroup$

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado graph that also has this property, but fails to be homogeneous?

I haven't found any clear statement that it is unique nor any such non-homogeneous example when searching around, but it feels like the answer to this should be well known...

Improve this question
$\endgroup$
6
  • 13
    $\begingroup$ I think there are many examples. The Rado graph plus an isolated point, or plus $n$ isolated points, the disjoint union of two Rado graphs, the disjoint union of all finite graphs . . . $\endgroup$
    – Will Brian
    Commented Nov 28, 2023 at 13:55
  • 3
    $\begingroup$ Once again my intuition for infinity turns out to be infinitely flawed. (Or at least I have yet to find an upper bound for its flawedness.) Thank you. $\endgroup$
    – Vilhelm Agdur
    Commented Nov 28, 2023 at 14:33
  • $\begingroup$ I think that if (1) $G$ is connected and countable, and (2) for every finite graph $A$ and full subgraph $B$, any full embedding of $B$ in $G$ extends to a full embedding of $A$, then $G$ is isomorphic to the Rado graph. $\endgroup$
    – Neil Strickland
    Commented Nov 28, 2023 at 14:44
  • 6
    $\begingroup$ @NeilStrickland You don’t need to assume connectedness. This characterization is more-or-less what “Fraïssé limit” means. $\endgroup$
    – Emil Jeřábek
    Commented Nov 28, 2023 at 15:05
  • 4
    $\begingroup$ It doesn't even have to contain Rado's graph; just take a disjoint union of finite graphs, one of each isomorphism type. $\endgroup$
    – bof
    Commented Nov 28, 2023 at 20:07

1 Answer 1

Reset to default
8
$\begingroup$

Since the question is very well answered in comments (by multiple people), here’s a CW answer putting them all together.

The Rado graph is not uniquely characterised, among countable graphs, by the property “every finite graph embeds”. It’s easy to give many counterexamples: the disjoint union of one copy of every finite graph; or (if you want connectedness) that disjoint union plus one extra vertex with an edge to every other; or the Rado graph union a point; or the disjoint union, or connected union, of two copies of the Rado graph…

However, it is characterised by a natural strengthening of that property: “given any finite graph $H$ and an embedding from some induced subgraph $H' \leq H$ into $G$, there’s an embedding of $H$ extending the given embedding of $H'$”. This is easily seen to be equivalent to the extension property as described in Wikipedia; similarly, it directly suffices for the back-and-forth argument sketched there, showing that any two countable graphs with this property are isomorphic. It is the special case for graphs of one of the standard definitions/characterisations of the Fraïssé limit; in category-theoretic terms, it says the Rado graph is injective with respect to finite extensions in the category of graphs and embeddings (or full homomorphisms).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .