Wednesday, January 29, 2025

[gyrlrjpy] enumerating monotonic colorings of hypercubes in an integer hyperbrick

consider a brick in N dimensions composed of unit hypercubes.  for example, let N=3.  each unit cube is labeled 0 or 1, subject to the following monotonicity constraints:

  1. let A = (a[1], a[2], a[3]) be the coordinates of one unit cube and B = (b[1], b[2], b[3]) be the coordinates of another unit cube.  if for all i in {1,2,3}, a[i] <= b[i], then it must not be the case that the label at A is 1 and the label at B is 0.
  2. Similarly, if A >= B, then it must not be the case that A = 0 and B = 1.

is constraint 2 necessary, or does it logically follow from 1 ?

how many valid labelings of the cubes in the brick are there?

I suspect the number is much less than total number of possible unconstrained labelings.  what is a compact way of describing a coloring, more compact than giving the label of every unit cube?

inspired by trying to generalize Conway's Game of Life cellular automata to 3D.  let neighbors through a corner of a cell, edge, and face each contribute a different amount of influence to the "number of neighbors" a cell has.  we want more generality than a weighted sum, but we want to keep rules to be monotonic: for example, if a threshold has been crossed for "too many neighbors", then it remains crossed for "more" neighbors.  (previously, 2D.)  in 3D, there can be 0 to 8 corner neighbors, 0 to 12 edge, and 0 to 6 face.  these together which define a 9 x 13 x 7 brick.  label each of its 819 unit subcubes "OK" or "too crowded".  without the monotonicity constraints, there are 2^819 possible labelings, far too large to evaluate all of them by brute force.

2D: 5 x 5 brick (0 ... 4 edge neighbors and corner neighbors), so 2^25 = 32 million unconstrained labelings.  counting those which satisfy the monotonicity constraints can be done by brute force.  finding those which yield "good" cellular automata is harder.

future work: 3 labels for unit cubes: "too isolated", "OK", "too crowded".  we need to come up with a new definition for monotonicity among the 3 ordered labels, probably not difficult.  a second brick describing births from dead cells.  perhaps constrain the conditions suitable for birth to be a subset of conditions suitable for life.

No comments:

Post a Comment