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)

Lead section

I know that this can be said about a lot of math articles on Wikipedia, but since this is a GA (and thus "SOFIXIT" is a bit scarier)... the lead is too inaccessible IMO. This topic is not that difficult - a smart, math-focused high schooler can understand it, and a college math major certainly should. It's the graph you get as you expand a randomly created graph countably infinite times, or use certain procedural styles of construction that are "random enough", and it contains every subgraph you can imagine. Precision is important, yes, and I'm not complaining about the content of the rest of the article being technical if dense, but the lead should be able to lay off stuff like "Hereditarily finite set", or at least gloss all the technical terms heavily.

Usual disclaimer here that an accurate if tough to read article is better than an inaccurate and easy to read article, so I hope this doesn't come across as too "whiny" - there was clearly good work done here. But the standards for a GA are a bit higher. (I was reminded of this due to Matt Parker's fine YouTube video on the topic - https://www.youtube.com/watch?v=TNWl-0rle4A . Makes it very friendly and "obvious" in the way that a good explanation can ease complexity. Then I checked the Wikipedia article, and... the lead is written much more densely than it needs to be. While maybe not "circle" or "square", we can definitely be friendlier here, IMO.) @David Eppstein: Does the above criticism make sense? Would you be willing to take a shot at making a slightly friendlier lede, or would you complain if I did? SnowFire (talk) 02:03, 22 December 2025 (UTC)

You say the Rado graph "is" something that is only part of what it is, a randomly-constructed graph. But the lead should accurately summarize the content of the article, including the many other constructions that have nothing to do with randomness. One of those is the hereditarily finite sets. I don't think that can reasonably be omitted. And the lead is not the place for pedantic glosses of every technical term. They should be explained, but the detailed explanations should be and are later. Parker's video is fine for what it is but it does not explain several important aspects of the subject including most of these non-random constructions, and that lack of explanation appears to have contributed to your misconception that this graph can only be constructed randomly.

You should also see Royal Road § A metaphorical "Royal Road" in famous quotations: people have been demanding that mathematicians explain things in ways that take no effort for non-mathematicians to understand for literally millenia, and the answer has always been: It's not possible. You have to put some effort into it.

All that said, I have attempted to rewrite this part of the lead to say the same things as before, in roughly the same length, but using fewer technical words. —David Eppstein (talk) 02:32, 22 December 2025 (UTC)

As I wrote above, 'certain procedural styles of construction that are "random enough"'. Yes, that is in fact gone over in the video (e.g. rules taking the numbered vertices binary representations etc.) and no, I wasn't confused on this point. I do think that "pedantic glosses" can be quite helpful, actually. The reason to avoid them is if there's no way to compress a technical term accurately other than "click the wikilink" but again, this isn't a topic that requires being a grad student or anything. Or shouldn't be. That said, "(finite sets whose elements are hereditarily finite)" is indeed not a helpful gloss as it's just repeating the term again.

Thanks for taking a look. This is still dense but it's better now. SnowFire (talk) 03:25, 22 December 2025 (UTC)

@SnowFire if you think that gloss is merely repeating the same term then you haven't understood it. It is in fact the complete definition. —David Eppstein (talk) 05:46, 22 December 2025 (UTC)

... This is why discussing this kind of matter is exceptionally difficult because saying "hey this could be written more clearly" apparently gets interpreted as "Hi I am a big idiot who doesn't understand what I'm talking about." David Eppstein, I'm not a math professor, so you can pull rank on me for the details, but I was a math major in college, I am friends with an actual (retired) math professor, I pay attention to math. If I'm saying that this can be written more clearly, then I'd appreciate less implication that I'm "not willing to put effort in to understand it" (and I understand hereditary finite sets just fine, thanks). Wikipedia is written for multiple audiences. Making an article accessible to "casual" readers does not have to mean compromising accuracy later on.

Okay back to the main issue here. I'd love to write this out more clearly but am holding back in deference to you, but I'm not sure what point you're trying to prove here by putting in some sort of intentionally useless gloss. If there's some term like "Broccoli-Rutabaga set", it is a useless gloss to say ("a set that conforms to the Broccoli-Rutabaga property"). That's just repeating yourself. If I had my druthers, we'd write this out even more directly with examples in the lead, but I'm not sure what you're trying to prove by having such a repetitive gloss. If this is some sort of "you asked for it so how do you like it", no, I don't think this is a good addition. SnowFire (talk) 05:56, 22 December 2025 (UTC)

I wasn't meaning to insult you, but the fact is that "hereditarily finite sets are finite sets whose elements are hereditarily finite sets" is a complete definition, not a mere repetition of words as you claimed it to be. We have a separate article Recursive definition explaining this sort of thing. It is not an "intentionally useless gloss", it is both a completely informative gloss for people who have seen this sort of thing before (but just need reminding what hereditarily finite means) and an intentionally intriguing gloss for people who have not but are willing to explore that kind of apparent circularity and figure out why it is not actually circular. Or you could, you know, put a chip on your own shoulder and use it as an excuse to stop reading. —David Eppstein (talk) 06:32, 22 December 2025 (UTC)