Hypergraph coloring problem motivated by legal billards racks - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T21:21:28Z http://mathoverflow.net/feeds/question/106013 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106013/hypergraph-coloring-problem-motivated-by-legal-billards-racks Hypergraph coloring problem motivated by legal billards racks Sam Hopkins 2012-08-31T03:06:25Z 2012-08-31T05:34:10Z <p>Motivation</p> <p>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.</p> <p>Problem</p> <p>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?</p> <p>For instance, with $n=4$, a legal coloring is,</p> <pre><code> A B A A B B B B A B </code></pre> <p>but an illegal coloring is,</p> <pre><code> A B A A A B B A B A </code></pre> <p>because it contains a triangle with three $A$s.</p> <p>If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?</p> http://mathoverflow.net/questions/106013/hypergraph-coloring-problem-motivated-by-legal-billards-racks/106016#106016 Answer by Douglas Zare for Hypergraph coloring problem motivated by legal billards racks Douglas Zare 2012-08-31T05:34:10Z 2012-08-31T05:34:10Z <p>I calculated the first few terms recursively. </p> <p>$1, 2, 6, 24, 130, 960, 9702, 134512, 2562516, 67152240, 2422643366, 120395521752, \\ 8245524190254, 778511553019200, 101361018574446630$</p> <p>They weren't in the OEIS, but taking off the initial $1$ and dividing the other terms by $2$ produced <a href="http://oeis.org/A007017" rel="nofollow">A007017</a>, which referred to "L. Vuillon, 'Contribution a l'etude des pavages et des surfaces dicretisees,' Dissertation, Universite de la mediterranee, Marseille, France 1996."</p> <p>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 <a href="http://mathworld.wolfram.com/HardSquareEntropyConstant.html" rel="nofollow">hard square entropy constant</a>.</p>