The random graph

Description:  In 1963, Erdos and Rényi proved the paradoxical result that there is a graph R with the property that, if a countable graph is chosen by selecting edges independently with probability 1/2, the resulting graph is almost surely isomorphic to R. Their proof was a beautiful example of a non-constructive existence proof, but in fact an explicit construction was given by Rado at about the same time. Several different constructions for the random graph (as it is now called) are known, exploiting things from various areas of mathematics such as number theory and set theory. Quite a bit is known about its automorphism group, and about representations of it as a Cayley graph. Recently, it has made an appearance in some dramatic results on Ramsey theory and topological dynamics. Start Date:  2014-07-17 Start Time:   15:00 Speaker:  Peter Cameron (Queen Mary, Univ. London, UK) Institution:  Queen Mary, University of London URL:  http://www.maths.qmul.ac.uk/~pjc/ See more:   <Main>