In mathematics, the mex of a subset of a

well-ordered In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...

set is the smallest value from the whole set that does not belong to the subset. That is, it is the

minimum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...

value of the

complement set In set theory, the complement of a set , often denoted by (or ), is the set of elements not in . When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is t ...

. The name "mex" is shorthand for "''m''inimum ''ex''cluded" 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 Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the player ...

to assign nim-values to

impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference bet ...

s. According to the

Sprague–Grundy theorem In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...

, 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. Minimum excluded values are also used in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, in

greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...

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.

Examples

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

\operatorname(\emptyset) = 0

\operatorname(\) = 0

\operatorname(\) = 1

\operatorname(\) = 2

\operatorname(\) = \omega

\operatorname(\) = \omega+1

where is the

limit ordinal In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists a ...

for the natural numbers.

Game theory

In the Sprague–Grundy theory the minimum excluded ordinal is used to determine the

nimber In mathematics, the nimbers, also called ''Grundy numbers'', are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with ''nimber addition'' and ' ...

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 stones, and the player to move may take any positive number of stones. If is zero stones, the nimber is 0 because the mex of the empty set of legal moves is the nimber 0. If is 1 stone, the player to move will leave 0 stones, and , gives the nimber for this case. If is 2 stones, the player to move can leave 0 or 1 stones, giving the nimber 2 as the mex of the nimbers . In general, the player to move with a pile of stones can leave anywhere from 0 to stones; the mex of the nimbers is always the nimber . 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 stones, the successor states have nimbers , 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 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 is the nimber 1, so starting with 5 stones in this game is a win for the first player. See

s for more details on the meaning of nimber values.

References

{{reflist Combinatorial game theory