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