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?

3 comments:

onthecusp said...

Is the rearranging acausal (i.e. a property of the graph)? Something tells me that there are many other micro-processes going on that would be to fast to see unless simulated stepwise. Ice may seem to form quickly but there are numerous regions of crystalization that are disconnected space wise but only related by temperature.

barry goldman said...

the dynamic structure of water is complex on the microscopic scale. There might be heterogeneous regions but presumably they are communicating by heat transfer at 10billion collisions/oscillations per second?


water structure



complex on the microscopic scale. There might be heterogeneous regions but presumably they are communicating by heat transfer at 10billion collisions/oscillations per second?


models


It's all a mystery to me. Don't know when i'll get a chance to study it.

I'll post my findings, when i find them.

thanks.

barry goldman said...

hmm posting html tags in comments is messy... i need my own webpage