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:
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.
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Search /
Change password /
Logout
