Identical lists maximize the probability of a non-distinguishing coloring

Let GG be a graph, and let L=L\mathcal{L}=\mathcal{L} be a collection of equal-sized lists, each of size kk, indexed by the vertices veq0v eq 0 of GG. Choose a color from each vertex's list uniformly and independently, and let p(L)p(\mathcal{L}) be the probability that the resulting coloring admits a non-trivial automorphism preserving every color class. List-probability strengthening. The probability p(L)p(\mathcal{L}) is maximized when all the lists are identical. This would strengthen the List Distinguishing Conjecture by identifying the worst-case list assignment for random colorings.

Sources & referencesView supporting material

Primary source

Niranjan Balachandran and Sajith Padinhatteeri, “The List Distinguishing Number of Kneser Graphs”, arXiv:1602.03741 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.