The Affirmative Action ProblemThe Affirmative Action problem has been posed by Donald Newman [Zeitz, p. 23]: Consider a graph whose nodes are colored in one of two colors: black or white. The white node is called integrated if it has at least as many black as white neighbors, and similarly for the black node. A coloring of a graph is said to be integrated if each of the nodes is integrated. Prove that a graph without loops admits an integrated coloring. The applet below starts with a configuration of 20 nodes. The nodes (and edges) can be removed one at a time (Remove last) or all at once (Clear). You can create new nodes by starting to drag anywhere in the applet. Clicking inside a node changes its color.
The proof is due to Jim Propp. Call an edge balanced if it joins two differently colored nodes. The proof elaborates on the one-liner: Maximize the number of balanced edges! Since the number of nodes is finite, so is the number of possible color assignments. Hence, there are colorings with the maximal number of balanced edges. Any such coloring is bound to be integrated. To see why this is so, consider a non integrated node. Without loss of generality we may assume it colored white. The fact the the node is not integrated can be rephrased in terms of the incident edges. The edges joining the node to the black neighbors are balanced, those joining it to the white neighbors are not. We conclude, that, among the edges incident to the non integrated node, there are fewer balanced than unbalanced edges. Changing the color of such a node, makes its incident balanced edges unbalanced, and vice versa. The operation therefore increases the total number of balanced edges. Now, we see that the existence of a non integrated node in a coloring with a maximal number of balanced edges leads to a contradiction. Thus we conclude that, in such colorings, all nodes are necessarily integrated. References
|Contact| |Front page| |Contents| |Algebra| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 40620025 |
