Generating random m x n grid 3-colourings is even less trivial than had previously appeared. Frustrated by inability to progress with the d = 5/8 = 0.625 conjecture, I resorted to a census of all m x n arrays of small size --- only to discover the density of equal diagonals heading gleefully northward towards somewhere in the region of d = 11/16 = 0.6875 instead! To produce that density, it would seem that the "random" constructor should select each new bit equal to its diagonal neighbour with probability p = 3/4 , rather than the p = 1/2 naïvely assumed earlier. Incidentally, just exactly why should d = 1/2 + p/4 in this context --- is that (a) obvious; (b) well-known; (c) true; (d) provable either? It's actually rather easier to deal instead with Hardin binary arrays, where each 2x2 square has some diagonal neighbours assigned equal bits. Provided the top left nodes of both 3-colourings and Hardin arrays are fixed assignments, there is a bijection between the two sets. This is thrown off casually in a comment on OEIS A078099 --- puzzle: provide the proof! Fred Lunnon O I OO I OOOO PRPQRQPQP I OOOOO I O I RPQPQPRPR OO I OOOO I I PQRQPQPRQ O I I I O I OO I QRPRQRQPR I I O I I O I OO RPQPRQRQP I I I O I I I I O PRPQPRPRQ O I I I I I I OO QPRPRPRQP I I I I O I OOO PRPRQRQPQ I I I I I OO I O RPRPRQPRP On 2/1/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On further reflection, a modicum of conscience might extract the admission that the order of T(m, n) is not (directly) related to 1+d after all (where d denotes the proportion of diagonal pairs with same colour).
Still d is of independent interest. A program generating random colourings (not in itself an entirely trivial exercise) leads to the conjecture
*** d = 5/8 ***
for almost all colourings of a large grid.
Is this (a) obvious; (b) well-known; (c) true; (d) provable?
Fred Lunnon
On 1/9/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On reflection, a modicum of signposting might be in order: so note that colourings (of either class) number (2 or 3 times) T(m, n) = O(1+d)^(m n) .
Note also that the Maple counting program given under A078099 requires substantial editing, and is impracticably slow for m > 8 . Results from a more elaborate Magma program can be made available, should anyone feel sufficiently motivated to demand them ...
Fred Lunnon
On 1/9/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Within the (exiguous) bowels of OEIS A078099 there lurks a throwaway comment to the effect that 3-colouring the nodes of a m x n grid such that edge-adjacent pairs of nodes are assigned distinct colours is equivalent to 2-colouring the nodes such that no square (4-circuit) has both diagonals assigned distinct colours. [Establishing this equivalence is not entirely trivial.] In default of any earlier attribution, I propose to dub the latter colourings "Hardin" colourings.
Though I haven't sat down to prove it, it seems reasonable to assume that as n,m -> oo the density of diagonal pairs with equal colours approaches a limit d , for a `random' Hardin colouring. [We can just sum frequencies over distinct n x n colourings where n is large, then take means.]
I can show d > 0.5382 , and extrapolation suggests d ~ 0.5395 +/- 0.00005 ; can anybody improve on these values, find an explicit expression, or show a non-trivial upper bound for d ?
Fred Lunnon