Wednesday, March 7, 2007
zero one laws in random graphs.
if you have an ensemble of M sets of N vertices each, each with the probability of an edges between vertices being p, then for each property of a graph, i.e. a cycle exists, a completely connected graph exists, no nonconnected component exists... a certain proportion q, of the ensemble will have that property.
now as we let M go to infinity and p go from 0 to 1 smoothly the function q(p) will approach a step function at some probability p for each property. This takes VERY high level math to prove, but can we simulate it?
can we relate this to the behavior of a SINGLE very large graph? i.e. with on the order of 10^23 vertices, or cellular scale, 10^12 vertices, but with edges rearranging 10^10 times/sec so in the order of a few seconds this graph wanders through the space of the ensemble...
so if we just think of the transition from liquid to solid where the probability of a bond is proportional to temperature or basically the definition of temperature is the probability of a bond.. then as we raise temperature smoothly we get a step transition from liquid to solid.
ditto for more complicated properties of chemical networks?
where does this go?