Hypergraph coloring problem motivated by legal billards racks

2012-08-31T03:06:25Z

Motivation

There are several rules about what makes a rack legal for a game of eight-ball: the top ball has to be a solid, the eight-ball is in the middle, the two bottom vertices have to be one solid and one stripe, etc. But a rule I learned when I first learned to play pool was that there should be no three balls which are pairwise touching each other that are all stripes or all solids. Apparently this is not an actual rule for professional eight-ball. Nevertheless, it is an interesting restriction.

Problem

Suppose we color the points in a triangular grid with base length $n$ with two colors, $A$ or $B$. How many such colorings have the property that no three points in a touching triangle are all the same color?

For instance, with $n=4$, a legal coloring is,

     A
    B A
   A B B
  B B A B

but an illegal coloring is,

     A
    B A
   A A B
  B A B A

because it contains a triangle with three $A$s.

If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?

Answer by Douglas Zare for Hypergraph coloring problem motivated by legal billards racks

2012-08-31T05:34:10Z

I calculated the first few terms recursively.

$1, 2, 6, 24, 130, 960, 9702, 134512, 2562516, 67152240, 2422643366, 120395521752, \\ 8245524190254, 778511553019200, 101361018574446630$

They weren't in the OEIS, but taking off the initial $1$ and dividing the other terms by $2$ produced A007017, which referred to "L. Vuillon, 'Contribution a l'etude des pavages et des surfaces dicretisees,' Dissertation, Universite de la mediterranee, Marseille, France 1996."

Some problems like this have a closed form solution or asymptotics, but typically there is some entropy per area which people can bound but can't compute exactly, such as the hard square entropy constant.

Hypergraph coloring problem motivated by legal billards racks - MathOverflow

Hypergraph coloring problem motivated by legal billards racks

Answer by Douglas Zare for Hypergraph coloring problem motivated by legal billards racks