Coloring hypercubes

Jinyoung Park (박진영)

Department of Mathematics, Rutgers, Piscataway, NJ, USA

Department of Mathematics, Rutgers, Piscataway, NJ, USA

2018/06/26 Tuesday 5PM

We discuss the number of proper colorings of the hypercube (the covering graph of the Boolean algebra) given q colors. When q=2, it is easy to see that there are only 2 possible colorings. However, it is already highly nontrivial to figure out the number of colorings when q=3. Since Galvin (2002) proved the asymptotics for the number of 3-colorings, the rest cases remained open so far. In this talk, I will introduce a recent work about the number of 4-colorings, mainly focusing on 1. how entropy can be used in counting and 2. isoperimetric properties of hypercube. This is joint work with Jeff Kahn.