You are browsing as Guest
Click here for list of discussions
Click here to login





Discussion: HardInstancesOfGraphThreeColouring
You have read-only access
You may need to scroll to the right ...

Click here to view in strict time order
Click here to view in neighbourhood mode.

%3 N_20210815210540a_ColinWright    By ColinWright 2021/08/15 @ 21:05:40a -------------------------------- Graph Three Colouring (G3C) is well-known to be NP-Complete. However, like most NPC problems, most instances are trivial.        (select only this node)     N_20210815210540b_ColinWright    By ColinWright 2021/08/15 @ 21:05:40b -------------------------------- In this discussion we talk about creating instances that are hard.        (select only this node)     N_20210815210540a_ColinWright->N_20210815210540b_ColinWright N_20210815210801a_ColinWright    By ColinWright 2021/08/15 @ 21:08:01a -------------------------------- Although Integer Factoring (FAC) is *not* NPC, it serves as a useful places to talk about some of the concepts.        (select only this node)     N_20210815210540a_ColinWright->N_20210815210801a_ColinWright N_20210816120009a_ColinWright    By ColinWright 2021/08/16 @ 12:00:09a -------------------------------- Follow this arrow to get directly to the new idea, skipping the (mostly standard) definitions and motivating context.        (select only this node)     N_20210815210540b_ColinWright->N_20210816120009a_ColinWright N_20210815210801b_ColinWright    By ColinWright 2021/08/15 @ 21:08:01b -------------------------------- Choose an integer at random. Most of the time (for some definition of that term) there will be a small factor, so finding a non-trivial factor is easy.        (select only this node)     N_20210815210801a_ColinWright->N_20210815210801b_ColinWright N_20210816095008a_ColinWright    By ColinWright 2021/08/16 @ 09:50:08a -------------------------------- Consider, half the random numbers you choose will be divisible by 2, and 1/3 of the remainder will be divisible by 3. And so on.        (select only this node)     N_20210815210801b_ColinWright->N_20210816095008a_ColinWright N_20210815210801c_ColinWright    By ColinWright 2021/08/15 @ 21:08:01c -------------------------------- We construct a difficult instance of FAC by choosing two primes of roughly the same size, with no special form, and without a simple ratio relating them.        (select only this node)     N_20210815210801b_ColinWright->N_20210815210801c_ColinWright N_20210815211018a_ColinWright    By ColinWright 2021/08/15 @ 21:10:18a -------------------------------- Unless stated otherwise:        (select only this node)     N_20210815211240a_ColinWright    By ColinWright 2021/08/15 @ 21:12:40a -------------------------------- A "colouring" is a function c from the vertices V of the graph G to the set of colours C.        (select only this node)     N_20210815211018a_ColinWright->N_20210815211240a_ColinWright N_20210815211041a_ColinWright    By ColinWright 2021/08/15 @ 21:10:41a -------------------------------- All graphs are finite,        (select only this node)     N_20210815211018a_ColinWright->N_20210815211041a_ColinWright N_20210815211018b_ColinWright    By ColinWright 2021/08/15 @ 21:10:18b -------------------------------- All colourings are vertex colourings,        (select only this node)     N_20210815211018a_ColinWright->N_20210815211018b_ColinWright N_20210815211018c_ColinWright    By ColinWright 2021/08/15 @ 21:10:18c -------------------------------- We will occasionally (re-)state these things explicitly for emphasis.        (select only this node)     N_20210815211018b_ColinWright->N_20210815211018c_ColinWright N_20210815211041a_ColinWright->N_20210815211018c_ColinWright N_20210815211335a_ColinWright    By ColinWright 2021/08/15 @ 21:13:35a -------------------------------- A colouring c is proper, legal, valid, permitted, and other such words, if for every edge {u,v} in G, c(u) != c(v).        (select only this node)     N_20210815211240a_ColinWright->N_20210815211335a_ColinWright N_20210815211613a_ColinWright    By ColinWright 2021/08/15 @ 21:16:13a -------------------------------- For the set E of edges in V we will sometimes refer to an edge as {u,v}, or as "uv".        (select only this node)     N_20210815211335a_ColinWright->N_20210815211613a_ColinWright N_20210815211821a_ColinWright    By ColinWright 2021/08/15 @ 21:18:21a -------------------------------- G3C is the problem of: Given a graph G, find a proper colouring using a set of colours C such that |C|=3.        (select only this node)     N_20210815211335a_ColinWright->N_20210815211821a_ColinWright N_20210815211353a_ColinWright    By ColinWright 2021/08/15 @ 21:13:53a -------------------------------- Usually we are only talking about proper colourings.        (select only this node)     N_20210815211335a_ColinWright->N_20210815211353a_ColinWright N_20210815211353a_ColinWright->N_20210815211018c_ColinWright N_20210815211613b_ColinWright    By ColinWright 2021/08/15 @ 21:16:13b -------------------------------- We are dealing with undirected graphs, so the vertices of an edge are not in any particular order.        (select only this node)     N_20210815211613a_ColinWright->N_20210815211613b_ColinWright N_20210815211613b_ColinWright->N_20210815211018c_ColinWright N_20210815211821b_ColinWright    By ColinWright 2021/08/15 @ 21:18:21b -------------------------------- In other words, "colour" the vertices of G with the colours red, green, and blue, so that for every edge {u,v}, the vertices u and v get assigned different colours.        (select only this node)     N_20210815211821a_ColinWright->N_20210815211821b_ColinWright N_20210815211930a_ColinWright    By ColinWright 2021/08/15 @ 21:19:30a -------------------------------- For some definitions of the terms, most graphs are such that it is easy either to find a three colouring, or show that no such colouring exists.        (select only this node)     N_20210815211821b_ColinWright->N_20210815211930a_ColinWright N_20210815212246a_ColinWright    By ColinWright 2021/08/15 @ 21:22:46a -------------------------------- In 1989, A.D.Petford and Dominic Welsh published a paper:        (select only this node)     N_20210815211821b_ColinWright->N_20210815212246a_ColinWright N_20210815211930b_ColinWright    By ColinWright 2021/08/15 @ 21:19:30b -------------------------------- Our challenge is to generate graphs that are hard to colour.        (select only this node)     N_20210815211930a_ColinWright->N_20210815211930b_ColinWright N_20210815211930c_ColinWright    By ColinWright 2021/08/15 @ 21:19:30c -------------------------------- Whatever that means.        (select only this node)     N_20210815211930b_ColinWright->N_20210815211930c_ColinWright N_20210815212246b_ColinWright    By ColinWright 2021/08/15 @ 21:22:46b -------------------------------- "A Randomised 3-Colouring Algorithm"        (select only this node)     N_20210815212246a_ColinWright->N_20210815212246b_ColinWright N_20210815212246c_ColinWright    By ColinWright 2021/08/15 @ 21:22:46c -------------------------------- https://www.solipsys.co.uk/documents/RandomisedThreeColouring_Petford_Welsh.pdf        (select only this node)     N_20210815212246b_ColinWright->N_20210815212246c_ColinWright N_20210815212519a_ColinWright    By ColinWright 2021/08/15 @ 21:25:19a -------------------------------- Their algorithm goes like this:        (select only this node)     N_20210815212246b_ColinWright->N_20210815212519a_ColinWright N_20210815212519b_ColinWright    By ColinWright 2021/08/15 @ 21:25:19b -------------------------------- Randomly colour the given graph        (select only this node)     N_20210815212519a_ColinWright->N_20210815212519b_ColinWright N_20210815214050a_ColinWright    By ColinWright 2021/08/15 @ 21:40:50a -------------------------------- Diversion:        (select only this node)     N_20210815212519a_ColinWright->N_20210815214050a_ColinWright N_20210815212519c_ColinWright    By ColinWright 2021/08/15 @ 21:25:19c -------------------------------- That is, literally choose a random colour for each vertex. The colouring need not be "proper" or "legal", and almost surely will not be.        (select only this node)     N_20210815212519b_ColinWright->N_20210815212519c_ColinWright N_20210815212519d_ColinWright    By ColinWright 2021/08/15 @ 21:25:19d -------------------------------- Repeatedly:        (select only this node)     N_20210815212519b_ColinWright->N_20210815212519d_ColinWright N_20210815212519c_ColinWright->N_20210815212519d_ColinWright N_20210815212614a_ColinWright    By ColinWright 2021/08/15 @ 21:26:14a -------------------------------- Choose a vertex at random        (select only this node)     N_20210815212519d_ColinWright->N_20210815212614a_ColinWright N_20210815212614b_ColinWright    By ColinWright 2021/08/15 @ 21:26:14b -------------------------------- Randomly choose a colour based on some probability function of its neighbours' colours.        (select only this node)     N_20210815212614a_ColinWright->N_20210815212614b_ColinWright N_20210815212614c_ColinWright    By ColinWright 2021/08/15 @ 21:26:14c -------------------------------- Recolour our vertex with this newly chosen colour.        (select only this node)     N_20210815212614b_ColinWright->N_20210815212614c_ColinWright N_20210815212646a_ColinWright    By ColinWright 2021/08/15 @ 21:26:46a -------------------------------- If the graph /is/ now properly coloured:        (select only this node)     N_20210815212614c_ColinWright->N_20210815212646a_ColinWright N_20210815212725a_ColinWright    By ColinWright 2021/08/15 @ 21:27:25a -------------------------------- If you've been going on for too long:        (select only this node)     N_20210815212614c_ColinWright->N_20210815212725a_ColinWright N_20210815212614c_ColinWright->N_20210815214050a_ColinWright N_20210815212614d_ColinWright    By ColinWright 2021/08/15 @ 21:26:14d -------------------------------- Note: The result will probably still not be proper.        (select only this node)     N_20210815212614c_ColinWright->N_20210815212614d_ColinWright N_20210815212646b_ColinWright    By ColinWright 2021/08/15 @ 21:26:46b -------------------------------- Terminate with success        (select only this node)     N_20210815212646a_ColinWright->N_20210815212646b_ColinWright N_20210815212907a_ColinWright    By ColinWright 2021/08/15 @ 21:29:07a -------------------------------- We make the following observations:        (select only this node)     N_20210815212646b_ColinWright->N_20210815212907a_ColinWright N_20210815212725b_ColinWright    By ColinWright 2021/08/15 @ 21:27:25b -------------------------------- Give up, and terminate with failure        (select only this node)     N_20210815212725a_ColinWright->N_20210815212725b_ColinWright N_20210815212725b_ColinWright->N_20210815212907a_ColinWright N_20210815212907b_ColinWright    By ColinWright 2021/08/15 @ 21:29:07b -------------------------------- Each vertex may be visited many times,        (select only this node)     N_20210815212907a_ColinWright->N_20210815212907b_ColinWright N_20210815212924a_ColinWright    By ColinWright 2021/08/15 @ 21:29:24a -------------------------------- If we find a colouring then it's valid        (select only this node)     N_20210815212907a_ColinWright->N_20210815212924a_ColinWright N_20210815212936a_ColinWright    By ColinWright 2021/08/15 @ 21:29:36a -------------------------------- Even if there is a colouring, we might not find it.        (select only this node)     N_20210815212907a_ColinWright->N_20210815212936a_ColinWright N_20210815213113a_ColinWright    By ColinWright 2021/08/15 @ 21:31:13a -------------------------------- In using the algorithm to colour lots of examples they found that with an appropriate choice of "how to choose the new colour at random the algorithm worked quite well.        (select only this node)     N_20210815212907b_ColinWright->N_20210815213113a_ColinWright N_20210815212924a_ColinWright->N_20210815213113a_ColinWright N_20210815212936a_ColinWright->N_20210815213113a_ColinWright N_20210815213113b_ColinWright    By ColinWright 2021/08/15 @ 21:31:13b -------------------------------- This is perhaps unsurprising because most instances of NP-Complete problems are easy to solve.        (select only this node)     N_20210815213113a_ColinWright->N_20210815213113b_ColinWright N_20210815213113c_ColinWright    By ColinWright 2021/08/15 @ 21:31:13c -------------------------------- They did, however, find that there were some graphs that were not coloured successfully by the algorithm.        (select only this node)     N_20210815213113a_ColinWright->N_20210815213113c_ColinWright N_20210815213225a_ColinWright    By ColinWright 2021/08/15 @ 21:32:25a -------------------------------- Investigating the difficult examples, Petford and Welsh say:        (select only this node)     N_20210815213113c_ColinWright->N_20210815213225a_ColinWright N_20210815213113d_ColinWright    By ColinWright 2021/08/15 @ 21:31:13d -------------------------------- Again, not surprising, as Graph 3-Colouring is NP-Complete, so there must be some instances that are difficult.        (select only this node)     N_20210815213113c_ColinWright->N_20210815213113d_ColinWright N_20210815213412a_ColinWright    By ColinWright 2021/08/15 @ 21:34:12a -------------------------------- They then go on:        (select only this node)     N_20210815213225a_ColinWright->N_20210815213412a_ColinWright N_20210815213225b_ColinWright    By ColinWright 2021/08/15 @ 21:32:25b -------------------------------- ... simulations ... tend to confirm our ideas that ... for this particular method of colouring ... the most difficult case among the class of ... "roughly regular" graphs is the case ... when the graphs have low vertex degree, say 5 or 6.        (select only this node)     N_20210815213225a_ColinWright->N_20210815213225b_ColinWright N_20210815213225b_ColinWright->N_20210815213412a_ColinWright N_20210816115846a_ColinWright    By ColinWright 2021/08/16 @ 11:58:46a -------------------------------- Taking all this as inspiration, let's see if we can create a model that explains "Difficult to Colour" and produces this magic idea of a "roughly regular graph of average degree between 5 and 6".        (select only this node)     N_20210815213225b_ColinWright->N_20210816115846a_ColinWright N_20210815213412b_ColinWright    By ColinWright 2021/08/15 @ 21:34:12b -------------------------------- We have no theoretical explanation of this curious behaviour. It is not unlike the phenomenon of phase-transition ... which occurs in the Ising model, Potts model ... and other models of statistical mechanics.        (select only this node)     N_20210815213412a_ColinWright->N_20210815213412b_ColinWright N_20210815213412b_ColinWright->N_20210816115846a_ColinWright N_20210815213707a_ColinWright    By ColinWright 2021/08/15 @ 21:37:07a -------------------------------- So the takeaway here is this:        (select only this node)     N_20210815213412b_ColinWright->N_20210815213707a_ColinWright N_20210815213412c_ColinWright    By ColinWright 2021/08/15 @ 21:34:12c -------------------------------- The concept of "phase transition" is also well known in random graph processes, perhaps the most common example being the emergence of the giant component.        (select only this node)     N_20210815213412b_ColinWright->N_20210815213412c_ColinWright N_20210815213412d_ColinWright    By ColinWright 2021/08/15 @ 21:34:12d -------------------------------- https://www.google.co.uk/search?q=phase+transition+in+random+graph+processes        (select only this node)     N_20210815213412c_ColinWright->N_20210815213412d_ColinWright N_20210815213707c_ColinWright    By ColinWright 2021/08/15 @ 21:37:07c -------------------------------- They generate 3-colourable graphs according to a random model        (select only this node)     N_20210815213707a_ColinWright->N_20210815213707c_ColinWright N_20210815213707b_ColinWright    By ColinWright 2021/08/15 @ 21:37:07b -------------------------------- They have a randomised graph colouring algorithm *A*        (select only this node)     N_20210815213707a_ColinWright->N_20210815213707b_ColinWright N_20210815213707e_ColinWright    By ColinWright 2021/08/15 @ 21:37:07e -------------------------------- As they adjust the parameter they look at how long *A* takes        (select only this node)     N_20210815213707b_ColinWright->N_20210815213707e_ColinWright N_20210815213707d_ColinWright    By ColinWright 2021/08/15 @ 21:37:07d -------------------------------- The random graphs have a parameter        (select only this node)     N_20210815213707c_ColinWright->N_20210815213707d_ColinWright N_20210815213707d_ColinWright->N_20210815213707e_ColinWright N_20210815213833a_ColinWright    By ColinWright 2021/08/15 @ 21:38:33a -------------------------------- The parameter is the degree in their "roughly regular" graphs.        (select only this node)     N_20210815213707d_ColinWright->N_20210815213833a_ColinWright N_20210815213707f_ColinWright    By ColinWright 2021/08/15 @ 21:37:07f -------------------------------- The time taken seems linear(ish) but has a strong peak in the mid-range        (select only this node)     N_20210815213707e_ColinWright->N_20210815213707f_ColinWright N_20210815213707f_ColinWright->N_20210816115846a_ColinWright N_20210815213833a_ColinWright->N_20210815213707f_ColinWright N_20210815214050b_ColinWright    By ColinWright 2021/08/15 @ 21:40:50b -------------------------------- Their algorithm is like a form of simulated annealing (SA).        (select only this node)     N_20210815214050a_ColinWright->N_20210815214050b_ColinWright N_20210815214050e_ColinWright    By ColinWright 2021/08/15 @ 21:40:50e -------------------------------- Understanding this is not critical.        (select only this node)     N_20210815214050a_ColinWright->N_20210815214050e_ColinWright N_20210815214050c_ColinWright    By ColinWright 2021/08/15 @ 21:40:50c -------------------------------- In SA we pick a random configuration, jiggle it a bit, if it gets better then keep it (probably), if it gets worse then don't keep it (probably). As we go on, we make the probability of accepting a bad change go to zero.        (select only this node)     N_20210815214050b_ColinWright->N_20210815214050c_ColinWright N_20210815214050d_ColinWright    By ColinWright 2021/08/15 @ 21:40:50d -------------------------------- In the Petford and Welsh algorithm we always accept the change, but we choose the new colour in such a way as to make it more likely to be better. The paper suggests different probability distributions to make that happen, and examines the effects.        (select only this node)     N_20210815214050c_ColinWright->N_20210815214050d_ColinWright N_20210815214050d_ColinWright->N_20210815214050e_ColinWright N_20210815214258a_ColinWright    By ColinWright 2021/08/15 @ 21:42:58a -------------------------------- Follow this arrow to skip the definitions and preliminaries.        (select only this node)     N_20210816093310a_ColinWright    By ColinWright 2021/08/16 @ 09:33:10a -------------------------------- Definitions and background        (select only this node)     N_20210815214258a_ColinWright->N_20210816093310a_ColinWright N_20210815214526a_ColinWright    By ColinWright 2021/08/15 @ 21:45:26a -------------------------------- In everything that follows we assume that the graphs are tri-partite, and hence guaranteed to be 3-colourable.        (select only this node)     N_20210815214258a_ColinWright->N_20210815214526a_ColinWright N_20210815214526b_ColinWright    By ColinWright 2021/08/15 @ 21:45:26b -------------------------------- We make some heuristic observations.        (select only this node)     N_20210815214526a_ColinWright->N_20210815214526b_ColinWright N_20210815214650a_ColinWright    By ColinWright 2021/08/15 @ 21:46:50a -------------------------------- If G has almost no edges then it will almost certainly be easy to colour, since "most" attempts will work, even if the result is not the default colouring.        (select only this node)     N_20210815214526b_ColinWright->N_20210815214650a_ColinWright N_20210815214526c_ColinWright    By ColinWright 2021/08/15 @ 21:45:26c -------------------------------- If G has very high average degree then it will almost certainly be easy to colour.        (select only this node)     N_20210815214526b_ColinWright->N_20210815214526c_ColinWright N_20210815214526d_ColinWright    By ColinWright 2021/08/15 @ 21:45:26d -------------------------------- Method: Find any triangle, colour that, then many other vertices will have their colourings forced, and so the colouring emerges quite quickly.        (select only this node)     N_20210815214526c_ColinWright->N_20210815214526d_ColinWright N_20210815214526e_ColinWright    By ColinWright 2021/08/15 @ 21:45:26e -------------------------------- For some definition of "quite quickly"        (select only this node)     N_20210815214526d_ColinWright->N_20210815214526e_ColinWright N_20210815214650b_ColinWright    By ColinWright 2021/08/15 @ 21:46:50b -------------------------------- So as the average degree goes from small to large it's plausible to think that the difficulty of colouring will go from easy, through a peak of difficulty, and return to being easy.        (select only this node)     N_20210815214526d_ColinWright->N_20210815214650b_ColinWright N_20210815214544a_ColinWright    By ColinWright 2021/08/15 @ 21:45:44a -------------------------------- This is the case even if there are some vertices of low degree, because the majority of the graph will have its colouring forced, and the vertices of low degree will be few in number and not affect the main process.        (select only this node)     N_20210815214526d_ColinWright->N_20210815214544a_ColinWright N_20210815214526f_ColinWright    By ColinWright 2021/08/15 @ 21:45:26f -------------------------------- Remember that by construction we know there is at least one proper 3-colouring.        (select only this node)     N_20210815214526e_ColinWright->N_20210815214526f_ColinWright N_20210815214526g_ColinWright    By ColinWright 2021/08/15 @ 21:45:26g -------------------------------- We call that colouring the "default" colouring.        (select only this node)     N_20210815214526f_ColinWright->N_20210815214526g_ColinWright N_20210816152604a_ColinWright    By ColinWright 2021/08/16 @ 15:26:04a -------------------------------- Demonstration reply ...        (select only this node)     N_20210815214544a_ColinWright->N_20210816152604a_ColinWright N_20210815214650a_ColinWright->N_20210815214650b_ColinWright N_20210815215426a_ColinWright    By ColinWright 2021/08/15 @ 21:54:26a -------------------------------- Consider the random graph process where we add the edges of $K_{n,n,n}$ uniformly at random.        (select only this node)     N_20210815214650b_ColinWright->N_20210815215426a_ColinWright N_20210815215426b_ColinWright    By ColinWright 2021/08/15 @ 21:54:26b -------------------------------- We can consider each of the three induced bi-partite graphs and ask how long it takes for them to become connected.        (select only this node)     N_20210815215426a_ColinWright->N_20210815215426b_ColinWright N_20210815215537a_ColinWright    By ColinWright 2021/08/15 @ 21:55:37a -------------------------------- The model Petford and Welsh used to generate graphs to test their colouring algorithm was to take $n$ vertices, colour them randomly, throw in random edges between differently coloured vertices, then discard the original colouring.        (select only this node)     N_20210815215426a_ColinWright->N_20210815215537a_ColinWright N_20210815215426c_ColinWright    By ColinWright 2021/08/15 @ 21:54:26c -------------------------------- Standard results show that the onset of connectedness is relatively sharp, but there is an emergence of an equivalent of the giant component much earlier, so the induced bi-partite sub-graphs can be thought of as "effectively connected" much earlier.        (select only this node)     N_20210815215426b_ColinWright->N_20210815215426c_ColinWright N_20210815220424a_ColinWright    By ColinWright 2021/08/15 @ 22:04:24a -------------------------------- Modification        (select only this node)     N_20210815215426c_ColinWright->N_20210815220424a_ColinWright N_20210815215723a_ColinWright    By ColinWright 2021/08/15 @ 21:57:23a -------------------------------- The average degree at the onset of full connectedness is much higher than the observed "5 or 6" quoted in the Petford/Welsh paper, but we might wonder if the onset of "effective connectedness" is close to that number.        (select only this node)     N_20210815215426c_ColinWright->N_20210815215723a_ColinWright N_20210815215643a_ColinWright    By ColinWright 2021/08/15 @ 21:56:43a -------------------------------- A graph is "effectively connected" when the giant component has appeared. In other words, there are a few vertices not connected to the giant component, but they are few enough in number that we can ignore them when colouring the graph.        (select only this node)     N_20210815215426c_ColinWright->N_20210815215643a_ColinWright N_20210815215643a_ColinWright->N_20210815215723a_ColinWright N_20210815215643a_ColinWright->N_20210815220424a_ColinWright N_20210815215723a_ColinWright->N_20210815220424a_ColinWright N_20210815215809a_ColinWright    By ColinWright 2021/08/15 @ 21:58:09a -------------------------------- So we observe that in the Erdos-Renyi model of a random 3-colourable graph the area of difficult instances to colour does *not* correspond to the emergence of the connectedness of the induced bi-partite sub-graphs.        (select only this node)     N_20210815215723a_ColinWright->N_20210815215809a_ColinWright N_20210815215809a_ColinWright->N_20210815220424a_ColinWright N_20210815220424b_ColinWright    By ColinWright 2021/08/15 @ 22:04:24b -------------------------------- Consider the graph $K_{n,n,n}$. Remove all the edges, and then add them back in one by one in a random order. We can then ask at what point the graph becomes uniquely 3-colourable.        (select only this node)     N_20210815220424a_ColinWright->N_20210815220424b_ColinWright N_20210815220424c_ColinWright    By ColinWright 2021/08/15 @ 22:04:24c -------------------------------- Certainly when any of the induced bi-partite sub-graphs are not connected the default colouring is not the only one, so uniqueness of the colouring is much delayed.        (select only this node)     N_20210815220424b_ColinWright->N_20210815220424c_ColinWright N_20210815220424d_ColinWright    By ColinWright 2021/08/15 @ 22:04:24d -------------------------------- But even before the induced bi-partite sub-graphs are connected, they will have a giant component, and are in a sense "effectively connected".        (select only this node)     N_20210815220424c_ColinWright->N_20210815220424d_ColinWright N_20210815220424e_ColinWright    By ColinWright 2021/08/15 @ 22:04:24e -------------------------------- When the giant component emerges in each of the induced bi-partite graphs, we may regard the stragglers as hairs that need to be shaved off.        (select only this node)     N_20210815220424d_ColinWright->N_20210815220424e_ColinWright N_20210815220424f_ColinWright    By ColinWright 2021/08/15 @ 22:04:24f -------------------------------- This loosely corresponds to the comment in the Petford/Welsh paper of the graph being "roughly regular."        (select only this node)     N_20210815220424e_ColinWright->N_20210815220424f_ColinWright N_20210815220424g_ColinWright    By ColinWright 2021/08/15 @ 22:04:24g -------------------------------- We can then ask whether the shaved graph is uniquely 3-colourable. So working in the "shaved graph":        (select only this node)     N_20210815220424e_ColinWright->N_20210815220424g_ColinWright N_20210815220424i_ColinWright    By ColinWright 2021/08/15 @ 22:04:24i -------------------------------- *Speculation:* The peak of difficulty of 3-colouring corresponds closely to the transition to uniqueness of the colouring.        (select only this node)     N_20210815220424g_ColinWright->N_20210815220424i_ColinWright N_20210815220424h_ColinWright    By ColinWright 2021/08/15 @ 22:04:24h -------------------------------- *Conjecture:* The transition to uniqueness of 3-colouring corresponds closely to the emergence of the giant components in the induced bi-partite sub-graphs.        (select only this node)     N_20210815220424g_ColinWright->N_20210815220424h_ColinWright N_20210816093310a_ColinWright->N_20210815211018a_ColinWright N_20210816120513a_ColinWright    By ColinWright 2021/08/16 @ 12:05:13a -------------------------------- Let n be fixed, and let A, B, and C be sets of vertices, each of size n. We construct a random bi-partite graph between each pair, thereby creating a subgraph of K_{n,n,n}.        (select only this node)     N_20210816115846a_ColinWright->N_20210816120513a_ColinWright N_20210816120009a_ColinWright->N_20210815214258a_ColinWright N_20210816120009a_ColinWright->N_20210816120513a_ColinWright N_20210816120513b_ColinWright    By ColinWright 2021/08/16 @ 12:05:13b -------------------------------- We describe the process on the subgraph on AuB.        (select only this node)     N_20210816120513a_ColinWright->N_20210816120513b_ColinWright N_20210816120513c_ColinWright    By ColinWright 2021/08/16 @ 12:05:13c -------------------------------- Choose three disjoint matchings between A and B. Put all the edges from the first two matchings into the graph.        (select only this node)     N_20210816120513b_ColinWright->N_20210816120513c_ColinWright N_20210816120513e_ColinWright    By ColinWright 2021/08/16 @ 12:05:13e -------------------------------- Choose a random order for the edges of the third matching.        (select only this node)     N_20210816120513c_ColinWright->N_20210816120513e_ColinWright N_20210816120513d_ColinWright    By ColinWright 2021/08/16 @ 12:05:13d -------------------------------- The resulting bi-partite graph is almost certainly not connected.        (select only this node)     N_20210816120513c_ColinWright->N_20210816120513d_ColinWright N_20210816120513f_ColinWright    By ColinWright 2021/08/16 @ 12:05:13f -------------------------------- Our random graph process consists of inserting the edges from the third matching in that random order.        (select only this node)     N_20210816120513e_ColinWright->N_20210816120513f_ColinWright N_20210816120636a_ColinWright    By ColinWright 2021/08/16 @ 12:06:36a -------------------------------- At the end of this process our bi-partite graph is almost certainly connected, and has exactly one 2-colouring.        (select only this node)     N_20210816120513f_ColinWright->N_20210816120636a_ColinWright N_20210816120749a_ColinWright    By ColinWright 2021/08/16 @ 12:07:49a -------------------------------- At the start of this process our bi-partite graph is almost certainly not connected, and each component will have a 2-colouring.        (select only this node)     N_20210816120513f_ColinWright->N_20210816120749a_ColinWright N_20210816121259a_ColinWright    By ColinWright 2021/08/16 @ 12:12:59a -------------------------------- We can consider the emergence of the uniqueness of the colouring. If this behaves like the connectedness in the Erdos-Renyi model, a "Giant Component" will emerge.        (select only this node)     N_20210816120636a_ColinWright->N_20210816121259a_ColinWright N_20210816120831a_ColinWright    By ColinWright 2021/08/16 @ 12:08:31a -------------------------------- (Up to permutation of the colours).        (select only this node)     N_20210816120636a_ColinWright->N_20210816120831a_ColinWright N_20210816120749b_ColinWright    By ColinWright 2021/08/16 @ 12:07:49b -------------------------------- If k is the number of components there will be 2^{k-1} 2-colourings.        (select only this node)     N_20210816120749a_ColinWright->N_20210816120749b_ColinWright N_20210816120749b_ColinWright->N_20210816121259a_ColinWright N_20210816121729a_ColinWright    By ColinWright 2021/08/16 @ 12:17:29a -------------------------------- Conjecture        (select only this node)     N_20210816121259a_ColinWright->N_20210816121729a_ColinWright N_20210816121259b_ColinWright    By ColinWright 2021/08/16 @ 12:12:59b -------------------------------- At that point the graph will consist of a giant component and lots of little pieces. The colouring will then be "effectively unique" in the sense that the vast majority of vertices will have their colour determined, with a scattering of choices for the remainder.        (select only this node)     N_20210816121259a_ColinWright->N_20210816121259b_ColinWright N_20210816121259b_ColinWright->N_20210816121729a_ColinWright N_20210816121729b_ColinWright    By ColinWright 2021/08/16 @ 12:17:29b -------------------------------- Consider the full graph G with vertices AuBuC. The difficulty of 3-colouring G coincides with the emergence of the giant components in each induced bi-partite graph.        (select only this node)     N_20210816121729a_ColinWright->N_20210816121729b_ColinWright N_20210816122138a_ColinWright    By ColinWright 2021/08/16 @ 12:21:38a -------------------------------- Reasoning:        (select only this node)     N_20210816121729b_ColinWright->N_20210816122138a_ColinWright N_20210816122138b_ColinWright    By ColinWright 2021/08/16 @ 12:21:38b -------------------------------- Before the giant components emerge there are many possible colourings within each induced bi-partite graph, so choices can be wrong without necessarily preventing the full colouring being found.        (select only this node)     N_20210816122138a_ColinWright->N_20210816122138b_ColinWright N_20210816122138c_ColinWright    By ColinWright 2021/08/16 @ 12:21:38c -------------------------------- However, as the giant components emerge, then apart from the small components not yet included, the colouring is fixed. At times it will be unclear as to the choice to make, and yet the wrong choice will prevent the colouring from being completed.        (select only this node)     N_20210816122138b_ColinWright->N_20210816122138c_ColinWright N_20210816122518a_ColinWright    By ColinWright 2021/08/16 @ 12:25:18a -------------------------------- Definition: The "Shaved Graph"        (select only this node)     N_20210816122138c_ColinWright->N_20210816122518a_ColinWright N_20210816122518b_ColinWright    By ColinWright 2021/08/16 @ 12:25:18b -------------------------------- As the giant components emerge, consider each induced bi-partite subgraph. Remove the vertices not in the giant component. We are shaving off the excess.        (select only this node)     N_20210816122518a_ColinWright->N_20210816122518b_ColinWright N_20210816122518c_ColinWright    By ColinWright 2021/08/16 @ 12:25:18c -------------------------------- (We should find a better term)        (select only this node)     N_20210816122518b_ColinWright->N_20210816122518c_ColinWright N_20210816122518d_ColinWright    By ColinWright 2021/08/16 @ 12:25:18d -------------------------------- In the shaved graph, the 3-colouring will be unique.        (select only this node)     N_20210816122518b_ColinWright->N_20210816122518d_ColinWright N_20210816122518e_ColinWright    By ColinWright 2021/08/16 @ 12:25:18e -------------------------------- Conjecture: The colouring will (probably) be rendered non-unique by the removal of a comparatively small number of edges.        (select only this node)     N_20210816122518d_ColinWright->N_20210816122518e_ColinWright N_20210816122651a_ColinWright    By ColinWright 2021/08/16 @ 12:26:51a -------------------------------- Conjecture: The "Shaved Graph" will be roughly regular, with average degree between 5 and 6.        (select only this node)     N_20210816122518d_ColinWright->N_20210816122651a_ColinWright N_20210816122720a_ColinWright    By ColinWright 2021/08/16 @ 12:27:20a -------------------------------- Conjecture: The Shaved Graph will be difficult to 3-colour.        (select only this node)     N_20210816122518e_ColinWright->N_20210816122720a_ColinWright N_20210816122651a_ColinWright->N_20210816122720a_ColinWright