Editing Erdos-RenyiModel
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri May 17 11:38:42 2024.
Press
to finish editing.
Who can edit this page?
... world editing disabled
Members
Council
Admin
Let $n$ be a natural number and $d$ be a real in some appropriate range. Construct a graph as follows: * Take three set of vertices, each of size $n$ * For all pairs of vertices $(u,v)$ with $u$ and $v$ in different sets, ** let $uv$ be an edge with probability chosen such that *** the average degree in $G$ is $d.$ [[[> I think this is Dominic's paper: * A Randomised 3-Colouring Algorithm * http://www.sciencedirect.com/science/article/pii/0012365X89902148 It's not exactly how I remembered it, but close enough ]]] From memory as $d$ goes from 4 to 6 the difficulty of finding a colouring goes from very small to quite large and then back again. Some would say that the maximum difficulty is pretty much exactly when $d$ is 5, and so each vertex is connected - on average - to 2.5 vertices of each of the other colours. This seems plausible. However, there are problems with the ERM.