Talk:Rado graph

Lead section

This article currently starts

The Rado graph, also known as the Random graph, is the unique countably infinite graph that contains all countable (finite and infinite) graphs as induced subgraphs.

This is not true. Consider the Rado graph together with an isolated vertex. Clearly this still has the desired property, but this graph is not isomorphic to the Rado graph (indeed, it violates the currently listed property "For any finite sets of vertices U and V, there exists a vertex connected to everything in U, and nothing in V." for U the set containing just the one isolated vertex). A correct statement would be something like

The Rado graph R is the unique countable graph with the property that for every finite graph G and any vertex a of G, each embedding of G - a into R can be extended to an embedding of G into R.

I will make this or a similar change now. Boris Alexeev (talk) 16:24, 23 December 2007 (UTC) Incidentally, insisting the graph be connected does not help either. Boris Alexeev (talk) 16:35, 23 December 2007 (UTC)

It says it's an induced subgraph, not isomorpihc to the whole graph — Preceding unsigned comment added by EZ132 (talk • contribs) 23:36, 7 July 2020 (UTC)

No, the criticism was valid. But it was also from 2007, and long since fixed, so your reply comes a little late... —David Eppstein (talk) 04:12, 8 July 2020 (UTC)

Equivalent definitions?

I find the definition given a bit unsatisfactory from the point of view of visualization, if it is left like that with no other comments. The fourth property listed:

For any finite disjoint sets of vertices U and V, there exists a vertex connected to everything in U, and nothing in V.

is also a carachterization up to isomorphisms and may serve as equivalent definition. Moreover it suggests a concrete visualization as follows: Consider $\mathbb {N}$ as a vertex set of a graph where any $n<m$ are joined iff $2^{n}$ enters in the binary expansion of $m$, that is the adjacency matrix is

${\Big \lfloor }{\frac {m}{2^{n}}}{\Big \rfloor }$.

In other words we connect 0 with all odd numbers, then we also connect

1 with 2,3, 6,7, 10,11,..; then

2 with 4,5,6,7, 12,13,14,15, 20,21,23,24, ...;

and so on. This way, for any pair of finite disjoint sets of vertices (numbers) U and V a vertex connected with everything in U and nothing in V can be produced just as a (large enough) number having a binary expansion with 1 in the places U and 0 in the places V, so this graph is a concrete model of the a Rado graph. --PMajer (talk) 09:51, 10 November 2008 (UTC)

This binary number idea turns out to be exactly Rado's definition. I've made considerable changes to the article since you left this comment, including leading with this definition and only putting the other constructions and characterizations later. I hope you get a chance to come back and leave some feedback on the updated article. —David Eppstein (talk) 02:26, 10 March 2009 (UTC)

(after wandering around) here I am again; in the meanwhile this article has reached a very good quality indeed. Thank you! --pma (talk) 19:19, 22 October 2009 (UTC)

Saturated model

@David Eppstein @Bryanrutherford0 While it's true the Rado graph is a saturated model, the property described in the section is instead (modulo a misleading conflation of the theory of graphs with the theory of the Rado graph) the much weaker weak saturation. As one would expect given this, the reference supports none of the material except the fact that the Rado graph is saturated. I removed the section rather than attempting to correct it because a) saturation seems a slightly odd choice of a property to highlight, rather than omega-categoricity (which implies saturation for the countable model) and/or ultrahomogeneity, where the Rado graph serves as a standard example; and b) properly describing types and saturation is fairly technical if done in general, and essentially amounts to a restatement of the extension property if just done for the Rado graph. In light of (a), neither approach seemed worthwhile.

I was considering replacing the section with an "Other model-theoretic properties" section restating that it's ultrahomogeneous. Then given that it's in a finite relational language, this is equivalent to the theory having quantifier elimination and being omega-categorical. Omega-categoricity in turn implies the countable model is both saturated and prime. Perhaps also stating that it gives a standard example of a simple theory that is not stable, and thus of a theory with the independence property. But this would probably just be a barrage of links, with little to no explanation. JoelleJay (talk) 15:55, 31 March 2023 (UTC)

This is going beyond my competency, I'm afraid! If you think you can produce a more clear, more accurate, more relevant section, then, please do! "A barrage of links, with little to no explanation," should be fine, since readers can click through the links to learn more.-Bryan Rutherford (talk) 18:15, 31 March 2023 (UTC)

I replaced the gloss but I'm not certain I got it right. This also affects Cantor's isomorphism theorem which has a similar paragraph (that I reused here to replace the gloss). User:JoelleJay can you please check that it's ok and/or correct the remaining inaccuracies? —David Eppstein (talk) 15:58, 4 April 2023 (UTC)

Hi David, that's a bit better but I think it still has OR and saturation is still a rather odd section to have thematically. I'll try to work on it more but might just end up replacing it with something on omega-categoricity. JoelleJay (talk) 23:46, 4 April 2023 (UTC)

Please go ahead. Only, if you do, please make sure the coverage of this topic is consistent throughout the entire article, rather than (as before) just ripping out a section but leaving dangling pointers to it in the rest of the article text. —David Eppstein (talk) 06:55, 5 April 2023 (UTC)