mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, the mex ("minimum excluded value") of a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

of a

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

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 maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...

value of the complement set. Beyond sets, subclasses of well-ordered classes have minimum excluded values. Minimum excluded values of subclasses of the

ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...

s 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. Research in this field has primarily focused on two-player games in which a ''position'' ev ...

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 be ...

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 ...

, 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 and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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

\operatorname(\) &=& \omega+1 \end

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 (not to be confused with Grundy chromatic numbers), are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordin ...

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 In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

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 In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

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