Identical lists maximize the probability of a non-distinguishing coloring
Identical lists maximize the probability of a non-distinguishing coloring
Let be a graph, and let be a collection of equal-sized lists, each of size , indexed by the vertices of . Choose a color from each vertex's list uniformly and independently, and let be the probability that the resulting coloring admits a non-trivial automorphism preserving every color class. List-probability strengthening. The probability 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.