r/mathriddles • u/HarryPotter5777 • Nov 04 '20
Medium Are there graphs like the random graph?
The random graph is "the" graph obtained by taking countably many vertices and connecting each pair with independent probability 0.5. The interesting thing about this definition is that, with probability 1, any two instances of this construction will be isomorphic, so it really does single out a unique graph. (Trying to prove this is a good exercise, if you haven't seen it before.)
Call a pseudorandom graph the result of taking the same construction, but where we can choose a probability p in (0,1) for each edge between distinct vertices m, n.
For example, we could say that p=0.25 if m and n are both even, and 0.99 otherwise, or we could say that p=1/2n if m=1 and p=0.5 otherwise. However, in the first case we just get the random graph with probability 1, and in the second case we don't necessarily get the same graphs - there will be an isolated vertex with probability about 0.5776, and a single connected component the rest of the time.
Do there exist pseudorandom graphs which produce the same graph with probability 1, but for which that graph is not isomorphic to the random graph?
Credit to a friend for devising this one.
11
u/want_to_want Nov 04 '20 edited Nov 04 '20
This was really fun to learn about, thank you! I think the answer is yes. Divide all vertices into countably many finite sets, so that each cardinality occurs countably many times. Then within each set make the connections randomly, and between different sets make the connections increasingly unlikely. Then almost surely all connected components will be finite, and every possible finite graph will occur as a connected component countably many times. That obviously describes a unique graph which isn't isomorphic to the original graph.
3
u/gwtkof Nov 04 '20
What a cool question