Mex (mathematics)

In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.

Beyond sets, subclasses of well-ordered classes have minimum excluded values. Minimum excluded values of subclasses of the ordinal numbers are used in combinatorial game theory to assign nim-values to impartial games. According to the Sprague–Grundy theorem, the nim-value of a game position is the minimum excluded value of the class of values of the positions that can be reached in a single move from the given position.[1]

Minimum excluded values are also used in graph theory, in greedy coloring algorithms. These algorithms typically choose an ordering of the vertices of a graph and choose a numbering of the available vertex colors. They then consider the vertices in order, for each vertex choosing its color to be the minimum excluded value of the set of colors already assigned to its neighbors.[2]

Examples

The following examples all assume that the given set is a subset of the class of ordinal numbers:

\operatorname {mex} (\emptyset )=0

\operatorname {mex} (\{1,2,3\})=0

\operatorname {mex} (\{0,2,4,6,\ldots \})=1

\operatorname {mex} (\{0,1,4,7,12\})=2

\operatorname {mex} (\{0,1,2,3,\ldots \})=\omega

\operatorname {mex} (\{0,1,2,3,\ldots ,\omega \})=\omega +1

where $ω$ is the limit ordinal for the natural numbers.

Game theory

In the Sprague–Grundy theory the minimum excluded ordinal is used to determine the nimber of a normal-play impartial game. In such a game, either player has the same moves in each position and the last player to move wins. The nimber is equal to 0 for a game that is lost immediately by the first player, and is equal to the mex of the nimbers of all possible next positions for any other game.

For example, in a one-pile version of Nim, the game starts with a pile of $n$ stones, and the player to move may take any positive number of stones. If $n$ is zero stones, the nimber is 0 because the mex of the empty set of legal moves is the nimber 0. If $n$ is 1 stone, the player to move will leave 0 stones, and $mex({0}) = 1$ , gives the nimber for this case. If $n$ is 2 stones, the player to move can leave 0 or 1 stones, giving the nimber 2 as the mex of the nimbers ${0, 1}$ . In general, the player to move with a pile of $n$ stones can leave anywhere from 0 to $n -1$ stones; the mex of the nimbers ${0, 1, ..., n -1}$ is always the nimber $n$ . The first player wins in Nim if and only if the nimber is not zero, so from this analysis we can conclude that the first player wins if and only if the starting number of stones in a one-pile game of Nim is not zero; the winning move is to take all the stones.

If we change the game so that the player to move can take up to 3 stones only, then with $n = 4$ stones, the successor states have nimbers ${1, 2, 3}$ , giving a mex of 0. Since the nimber for 4 stones is 0, the first player loses. The second player's strategy is to respond to whatever move the first player makes by taking the rest of the stones. For $n = 5$ stones, the nimbers of the successor states of 2, 3, and 4 stones are the nimbers 2, 3, and 0 (as we just calculated); the mex of the set of nimbers ${0, 2, 3}$ is the nimber 1, so starting with 5 stones in this game is a win for the first player.

See nimbers for more details on the meaning of nimber values.

References

Conway, John H. (2001). On Numbers and Games (2nd ed.). A.K. Peters. p. 124. ISBN 1-56881-127-6.
Welsh, D. J. A.; Powell, M. B. (1967). "An upper bound for the chromatic number of a graph and its application to timetabling problems". The Computer Journal. 10 (1): 85–86. doi:10.1093/comjnl/10.1.85.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Conway, John H. (2001). On Numbers and Games (2nd ed.). A.K. Peters. p. 124. ISBN 1-56881-127-6.

[2] Welsh, D. J. A.; Powell, M. B. (1967). "An upper bound for the chromatic number of a graph and its application to timetabling problems". The Computer Journal. 10 (1): 85–86. doi:10.1093/comjnl/10.1.85.