List-Distinguishing Cartesian Products of Cliques

Abstract The distinguishing number of a graph G , denoted D ( G ) , is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial automorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L -coloring of G is a coloring in which each vertex is colored with a color from L ( v ) . The list distinguishing number of G , denoted D l ( G ) is the minimum k such that every list assignment L that assigns a list of size at least k to every vertex permits a distinguishing L -coloring. In this paper, we prove that when n is large enough, the distinguishing and list-distinguishing numbers of K n □ K m agree for almost all m > n , and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to setting of distinguishing graph colorings and also prove an inequality for the binomial distribution that may be of independent interest.