Effectively Connected

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

But for each graph we can look at the connected components, and for each graph we write the sizes of the components as a descending sequence. When the graph is connected the sequence is just $(n).$ Before that we can look at the distribution of the sizes. Something interesting happens. Before a certain point all the components are of size $O(log(n)).$ Then after that point, significantly before the graph is actually connected, the largest component has size $O(n^{(2/3)})$ and all the other components are still $O(log(n)).$

So there is a giant component that emerges, and at that point, more or less, the graph is connected apart from some stragglers. In a very real sense the graph is "effectively connected."

All of the above works when we are in a bi-partite graph, only adding edges between the independent sets.

So now suppose we have a tri-partite graph on $A,$ $B,$ and $C,$ and we're throwing in edges between those sets. Initially the induced graph on, say, $A \cup B,$ is not connected, so there are few restrictions on whether the vertices in $A$ get colouring Amber or Blue, and ditto the vertices in $B.$ However, as this induced bi-partite graph gets connected it gets harder and harder for vertices not to get the colour the construction of the graph implies.

Now start with three sets $A,$ $B,$ and $C,$ each of size $n.$ We throw in edges between them uniformly at random creating a tri-partite graph. In each of the induced subgraphs on $A \cup B,$ $A \cup C,$ and $B \cup C,$ at some point the giant component emerges. At that point we can look at the vertices that are in the giant components and ignore the stragglers. The evidence suggests that on that graph, once the average degree between each of $A$ and $B,$ $A$ and $C,$ and $B$ and $C,$ gets to 3 (so the total average degree is 6) then the colouring that exists by construction is the only one.