Random Colorings of Graphs and the Dinitz Conjecture
Ramin Naimi · 2001
are equal, there is a simple solution: Assume S i; j = f1; 2; ; ng for all i; j. Let A be the matrix given in Figure 1. Then no two entries in the same row or same column of A are equal. It seems natural to think: if, when all the sets S i; j are the equal, it's so easy to avoid identical entries in the same row or same column, then it should also be possible to do so when the sets aren't the same. And Galvin showed that this indeed is the case|except that the proof isn't so trivial. 2 6 6 6 6 4 1 2 n 1 n 2 3 n 1 . . . . . . . . . . . . . . . n 1 n 2 n 1 3 7 7 7 7 5 Figure 1: A special case of the Dinitz Conjecture Now add chance to the problem. Suppose, to pick each entry a