% compile using AMS-LaTeX
% An 8-page document

 
\documentclass[12pt]{amsart}
\usepackage{amssymb,amscd,amsthm,verbatim}
\textheight 8 in
\textwidth 6 in
\oddsidemargin 3 mm
\evensidemargin 3mm


\newtheorem{proposition}{Proposition}[section]
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{conjecture}[proposition]{Conjecture}
\newtheorem{question}[proposition]{Question}
\newtheorem{definition}[proposition]{Definition}

\newcommand{\vv}{{\bf v}}
\newcommand{\xx}{{\bf x}}
\newcommand{\yy}{{\bf y}}
\newcommand{\F}{\mathbb F}
\newcommand{\naturals}{\mathbb N}
\newcommand{\integers}{\mathbb Z}
\newcommand{\rationals}{\mathbb Q}
\newcommand{\reals}{\mathbb R}
\newcommand{\complexes}{\mathbb C}
\newcommand{\dimens}{\mathrm{dim}}
\newcommand{\mono}{\mathrm{mono}}
\newcommand{\nullspace}{\mathrm{ker}}
\newcommand{\row}{\mathrm{row}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\C}{{\mathcal C}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\E}{{\mathcal E}}


\begin{document}
\thispagestyle{empty}

\begin{center}
{\LARGE \bf Nim-Regularity of Graphs}

\bigskip

{\Large Nathan Reading}

\vspace{.05 cm}
{
School of Mathematics, University of Minnesota\\
Minneapolis, MN 55455\\
{\texttt{reading@math.umn.edu}}
}

\bigskip
{\small Submitted: November 24, 1998; Accepted: January 22, 1999}

\end{center}


\thanks{The author wishes to thank Vic Reiner for many helpful conversations.}

\begin{abstract}
Ehrenborg and Steingr\'\i msson defined simplicial Nim, and defined Nim-regular complexes to be simplicial complexes
	for which simplicial Nim has a particular type of winning strategy.
We completely characterize the Nim-regular graphs by the exclusion of two vertex-induced subgraphs, the graph on 
	three vertices with one edge and the graph on five vertices which is complete except for one missing edge.
We show that all Nim-regular graphs have as their basis the set of disjoint unions of circuits (minimal non-faces)
	 of the graph.
\end{abstract}

\title{}

\maketitle


\centerline{\small Mathematics Subject Classification: 90D05, 90D43,
  90D44, 90D46.}

\bigskip

\bigskip


\section{Introduction}
\pagestyle{myheadings} \markboth{\hfill{\sc the electronic journal of
              combinatorics 6 (1999), \#R11}} {{\sc the electronic journal of combinatorics 6
              (1999), \#R11}\hfill} 


In \cite{Ehr-Stein}, Ehrenborg and Steingr\'\i msson defined simplicial Nim, a variant on the classic game of Nim.
In simplicial Nim, two players take markers from a number of piles.  
The piles are considered to be the vertices of some simplicial complex, and a legal move consists of choosing a 
	face of the complex and removing markers from any or all piles in the face.
The number of markers removed from each pile in the chosen face is arbitrary and independent of the number 
	removed from any other pile, except that at least one marker must be removed.
The winner is the player who removes the last marker.
For some simplicial complexes---called {\em Nim-regular} complexes---the winning strategy can be described using a 
	{\em Nim-basis}, and the strategy is similar to the winning strategy of standard Nim.
(Standard Nim can be described as simplicial Nim on a complex whose faces are all single vertices, and such a complex 
	is Nim-regular). 
They \cite{Ehr-Stein} also raise the following question:
\begin{question}
\label{main question}
Does a Nim-basis, if it exists, necessarily consist of the disjoint unions of circuits of the complex? 
\end{question}
\noindent Here a {\em circuit} is a minimal non-face.

For convenience we will name two graphs:
The graph on three vertices with one edge we call the {\em shriek}, because it resembles the symbol ``!'', which is
	pronounced ``shriek'' in certain algebraic contexts.
The graph on five vertices which is complete except for one missing edge we call $K_5^-$. 
We will prove the following:


\begin{theorem}
\label{Nim-DUOC for graphs}
Let $\Delta$ be a graph.
The following are equivalent:
\begin{enumerate}
\item[(i)]
$\Delta$ is Nim-regular.
\item[(ii)]
The disjoint unions of circuits form a Nim-basis for $\Delta$.
\item[(iii)]
$\Delta$ contains neither the shriek nor $K_5^-$ as a vertex-induced subgraph.
\item[(iv)]
The complement of $\Delta$ either consists of isolated vertices or has three or fewer components, each of
	which is a complete graph.  
\end{enumerate}
\end{theorem}
In particular, the Nim-regular graphs correspond to partitions of the vertices such that either all blocks 
	are singletons or there are fewer than four blocks.

This paper is structured as follows.
Section 2 establishes our notation, gives a few basic definitions, and proves several lemmas that simplify the 
	proof of Theorem ~\ref{Nim-DUOC for graphs}, which is contained in Section 3.
Section 4 contains comments on the case of higher-dimensional complexes.


\section{Preliminary Definitions and Results}

In this section, we give the definition of a Nim-basis and Nim-regularity, and give sufficient conditions for 
	the set of disjoint unions of circuits to be a Nim-basis.
Then we note a few additional facts about the Nim-basis which are useful for the proof of Theorem 
	~\ref{Nim-DUOC for graphs}.

We assume the definition of a simplicial complex (always assumed finite), and induced subcomplex.
A minimal non-face of $\Delta$ is called a {\em circuit}.
We will write DUOC for ``disjoint union of circuits.''
We will use $\uplus$ for disjoint union and the set-theoretic subtraction $A-B$ will be used even when 
	$B \not\subseteq A$. 
The empty set is considered to be a DUOC.
The following is clear:

\begin{proposition}
\label{circuits, DUOC of subcomplexes}
Let $\Delta$ be a simplicial complex with vertices $V$.
Let $\Gamma$ be the subcomplex of $\Delta$ induced by $U \subseteq V$.
Then $D$ is a circuit (DUOC) of $\Gamma$ if and only if $D \subseteq U$ and $D$ is a circuit (DUOC) of $\Delta$.
\end{proposition}

Let $A$ and $B$ be vertex sets in a simplicial complex $\Delta$.  
We say that $A$ {\em exceeds} $B$ {\em by a (nonempty) face} if $B \subset A$ and $A-B$ is a nonempty face of $\Delta$.

\begin{definition}
\label{Nim-basis}
A collection $\B$ of subsets of $V$ is called a {\em Nim-basis} of $\Delta$ if it satisfies the following conditions:
\begin{enumerate}
\item[(A)]
$\emptyset \in \B$.
\item[(B)]
No element of $\B$ exceeds any other by a face.
\item[(C)]
For any face $F \in \Delta$ and any vertex-subset $S \subseteq V$, there exist faces $K, G \in \Delta$ such that:
\begin{enumerate}
\item $K \subseteq F \subseteq G$, 
\item $G-F \subseteq S$ and 
\item $(S-G) \uplus K \in \B$.
\end{enumerate}
\end{enumerate}
If $\Delta$ has a Nim-basis, it is said to be {\em Nim-regular}.
\end{definition}

The definition of Nim-basis is due to \cite{Ehr-Stein}.
They showed that a Nim-basis, if it exists, gives a simple description of the winning strategy for simplicial Nim.
We will briefly describe the winning strategy for simplicial Nim on a Nim-regular complex.

A {\em Nim game} or {\em impartial two-player game} is a game where the players alternate moves.
The legal moves depend only on the position of the game, not on whose turn it is.
Such a game is called {\em short} if it must end in a finite number of moves.
In any Nim game, there is a set $W$ of {\em winning positions} with the following properties:
\begin{enumerate}
\item[(a)] $W$ contains the position(s) which results from the winning move.  
In our case, $W$ must contain the empty board.
\item[(b)] If $n$ and $m$ are positions in $W$, there is no legal move from $n$ to $m$.
\item[(c)] If $n$ is a position not in $W$ there is a legal move from $n$ to $m$ for some $m \in W$.
\end{enumerate}
Knowing the winning positions leads to a winning strategy:  If possible, the player must always move so as to leave 
	the board in a winning position.
Each time the player does so, (b) ensures that his or her opponent is unable to leave the board in a winning position.
Then (c) ensures that he or she will be able to repeat the procedure.
The shortness of the game and (a) guarantee that eventually the player will win.  
We can describe the positions in simplicial Nim as vectors $n \in \naturals^V$.
In particular, for $A \subseteq V$, we define $e(A)$ to be the vector such that $e_v(A)=1$ if $v \in A$ and 
	$e_v(A)=0$ otherwise. 
We say that a simplicial complex $\Delta$ is Nim-regular if there exists a set $\B \subseteq 2^V$ such that the 
	winning positions for simplicial Nim can be described as:
	\[W=\left \lbrace \sum_{i \ge 0} 2^i e(A_i): \,\, A_i \in \B \right \rbrace \]
Ehrenborg and Steingr\'\i msson \cite{Ehr-Stein} showed that the winning positions can be described this way if and 
	only if $\B$ is a Nim-basis for $\Delta$.

\begin{lemma}
\label{WMA assume S,F disjoint}
To verify condition (C) it suffices to consider the case where $S \cap F=\emptyset$.
\end{lemma}
\begin{proof}
Suppose (C) holds for all disjoint $S'$ and $F'$.
Let $S$ and $F$ be arbitrary.
Then $S-F$ and $F$ are disjoint, so there exist faces $K \subseteq F \subseteq G$ such that $G-F \subseteq (S-F)$ and 
	$((S-F)-G) \uplus K \in \B$.
But $(S-F)-G=S-G$ and $S-F \subseteq S$, so $K$ and $G$ satisfy condition (C) applied to $S$ and $F$.
\end{proof}

\begin{lemma}
\label{two faces for C}
In order to prove that the DUOCs satisfy property (C) of a Nim-basis, it suffices to show that (C) is satisfied when
	$F$ and $S$ are disjoint faces.
\end{lemma}
\begin{proof}
Suppose (C) is satisfied whenever $F'$ and $S'$ are disjoint faces.
Let $S$ be arbitrary and $F$ a face disjoint from $S$.
Let $D$ be maximal among DUOCs in $S$ and let $S'=S-D$.
Then $S'$ is a face, because otherwise it would contain a circuit, contradicting the maximality of $D$ in $S$. 
Then by supposition there are faces $K \subseteq F \subseteq G$ such that $G-F \subseteq S'$ and 
	$(S'-G) \uplus K$ is a DUOC.
Since $D$ is disjoint from $S'$ and $F$ it is also disjoint from $(S'-G) \uplus K$.
Because $G-F \subseteq S'$, $D$ is also disjoint from $G$, and therefore 
	$(S-G) \uplus K=((S'-G) \uplus K) \uplus D$.
Thus $(S-G) \uplus K$ is a DUOC.
Applying Lemma ~\ref{WMA assume S,F disjoint}, we are finished.
\end{proof}

\begin{definition}
Let $F$ be a non-empty face and let $D_i$ be disjoint circuits, with $D=\uplus_i D_i$, satisfying:
\begin{enumerate}
\item[(i)] $F \subseteq D$, 
\item[(ii)] $F \not\subseteq D-D_i, \forall i$,
\end{enumerate}
We say that $\lbrace D_i \rbrace$ is a {\em minimal cover of $F$ by circuits}.
\end{definition}


\begin{lemma}
\label{simplified B}
In order to prove that the DUOCs satisfy property (B) of a Nim-basis, it suffices to show the following:

If $F$ is a non-empty face, $\lbrace D_i \rbrace$ is a minimal cover of $F$ by circuits and $D=\uplus_i D_i$,
	then $D-F$ is not a DUOC. 
\end{lemma}
\begin{proof}
Suppose that for all faces $F$ and minimal covers $\lbrace D_i \rbrace $ of $F$ by circuits, $D-F$ is not a DUOC.  
Suppose also that there are pairs of DUOCs which differ by a non-empty face.
Let $A$ and $B$, with $B \subseteq A$, be minimal among such pairs in the sense that there is no pair of 
	DUOCs $A'$ and $B'$ with $|A'|+|B'|<|A|+|B|$ such that $A'$ exceeds $B'$ by a non-empty face.
Let $F=A-B$.
Write $A=\uplus_i A_i$ where the $A_i$ are disjoint circuits.
Let $D$ be the union of those $A_i$ which intersect $F$.
By supposition $D-F$ is not a DUOC.
Let $E$ be maximal among DUOCs contained in $D-F$.
Then $(D-F)-E$ is a face.
But $(D-F) \uplus (A-D)=B$ and $E \uplus (A-D)$ are both DUOCs,
and $B$ exceeds $(E \uplus (A-D))$ by the face $(D-F)-E$, contradicting the minimality of the pair $A, B$.
\end{proof}

Nim-regularity is inherited by subcomplexes.
This fact is easily proven by considering simplicial Nim, or by checking the definition directly, as follows:

\begin{lemma}
\label{Nim-basis of subcomplex}
If $\Delta$ is Nim-regular with basis $\B$ and vertex set $V$, and $\Gamma$ is the subcomplex induced by $U \subseteq V$,
	then $\Gamma$ is Nim-regular with basis 
	\[\A=\lbrace B \in \B :B \subseteq U \rbrace.\]
\end{lemma}
\begin{proof}
We check that $\A$ satisfies conditions (A), (B) and (C) of Definition ~\ref{Nim-basis}.
Conditions (A) and (B) are trivial.
If $S \subseteq U$ and $F \in \Gamma$ then $S \subseteq V$ and $F \in \Delta$.
Then by condition (C) applied to $\Delta$, there are faces $K \subseteq F \subseteq G$ of $\Delta$ 
	such that $G-F \subseteq S$ and $(S-G) \uplus K \in \B$.
But then $G$ and $K$ are contained in $S$, which is contained in $U$, so $G$ and $K$ are faces of $\Gamma$.
Also, $(S-G) \uplus K \subseteq U$, so $(S-G) \uplus K \in \A$.
\end{proof}

\begin{lemma}
\label{basis inclusiveness}
Let $\Delta$ have Nim-basis $\B$ and $B$ be a vertex set that doesn't exceed any basis element by a face.
Specifically, if $A \in \B$  and $A \ne B$ then $B$ does not exceed $A$ by a face.
Then $B \in \B$.
\end{lemma}

\begin{proof}
We use condition (C) of Definition ~\ref{Nim-basis}, with $S=B$ and $F$ is any face contained in $B$.
Condition (C) requires that there exist faces $K \subseteq F \subseteq G$ with $G-F \subseteq B$ and 
	$(B-G) \uplus K \in \B$.
But $K \subseteq B$ so $(B-G) \uplus K=B-(G-K) \in \B$.  
$B$ can not exceed $B-(G-K)$ by a non-empty face, and $G-K$ is a face, so $G-K=\emptyset$.
Thus $B \in \B$.
\end{proof}

Lemma ~\ref{basis inclusiveness} is not surprising, given that only condition (B) limits what sets can be in $\B$, 
	while (A) and (C) require certain sets to be in $\B$.

Lemma ~\ref{basis inclusiveness} has two immediate corollaries.

\begin{corollary}[\cite{Ehr-Stein}, Corollary 4.5, p.12]
\label{circuits in basis}
If $\Delta$ has Nim-Basis $\B$ then the circuits of $\Delta$ are contained in $\B$.
\end{corollary}

\begin{corollary}[\cite{Ehr-Stein}, p.12]
If $\Delta$ has a Nim-basis, that Nim-basis is unique.
\end{corollary}


\section{The Graph Case}

In this section we will prove Theorem ~\ref{Nim-DUOC for graphs}.
We will begin by showing that, in the graph case, exclusion of the shriek and $K_5^-$ implies that the DUOCs 
	form a Nim-basis.
Then we will show that neither the shriek nor $K_5^-$ is Nim regular. 
These facts, together with Lemma ~\ref{Nim-basis of subcomplex}, prove the equivalence of (i), (ii) and (iii) in 
	Theorem ~\ref{Nim-DUOC for graphs}.
Finally, we prove the equivalence of (iii) and (iv).

We will call a complex {\em shriekless} if it does not contain a shriek as a vertex-induced subcomplex.


\begin{proposition}
\label{shriekless graphs satisfy C}
Let $\Delta$ be a shriekless graph.
Then the set of DUOCs of $\Delta$ satisfies condition (C) for a Nim-basis.
\end{proposition}

\begin{proof}
Let $S$ and $F$ be disjoint faces.  
We need to find faces $K \subseteq F \subseteq G$ such that $(G-F) \subseteq S$ and $(S-G) \uplus K$ is a DUOC.
Then we will apply Lemma ~\ref{two faces for C}.
If $S=\emptyset$ we let $G=F$ and $K=\emptyset$.
If $F=\emptyset$, necessarily $K=\emptyset$, and we let $G=S$.
There are four remaining possibilities for the cardinalities of $F$ and $S$.

If $F=ab$ then we must take $G=F$.
If $S$ is an edge, write $S=cd$.
If $\Delta$ has edges $ac$ and $ad$, then $acd$ is a circuit.
We can set $K=a$ and we are finished.
Similarly, if $\Delta$ has edges $bc$ and $bd$, then we are finished.
Because $\Delta$ is shriekless, the only alternative left is that the edges connecting $S$ to $F$ are either
	 exactly edges $ac$ and $bd$ or edges $ad$ and $bc$.
In either case, $abcd$ is a DUOC.  Set $K=F$.

If $F=ab$ and $S=c$, WLOG $ac$ is an edge because $\Delta$ is shriekless. 
If $bc$ is also an edge, $abc$ is a circuit.  Set $K=F$.
If $bc$ is not an edge then it is a circuit.  Set $K=b$.

If $F=a$ and $S=bc$, WLOG $ab$ is an edge.
If $ac$ is also an edge, $abc$ is a circuit, and we let $K=F=G$.
If not, $ac$ is a circuit, and we let $G=ab$, $K=F$.

If $F=a$ and $S=b$:
If $ab$ is an edge, let $G=ab$, $K=\emptyset$.
If $ab$ is a circuit, let $K=F=G$.
\end{proof}

\begin{proposition}
\label{shriekless no K_5^- implies B}
Let $\Delta$ be a shriekless graph not containing $K_5^-.$
Then the DUOCs of $\Delta$ satisfy condition (B) for a Nim-basis.
\end{proposition}
\begin{proof}
We will use Lemma ~\ref{simplified B}.
Let $F$ be a nonempty face and let $D=\uplus_i D_i$ where the $\lbrace D_i \rbrace$ is a minimal cover of $F$
	by circuits.
We need to show that $D-F$ is not a DUOC. 

If $D$ is a single circuit, then $D-F$ is a face (by definition of circuit), and hence not a DUOC.
This disposes of the case where $F$ is a single vertex, because in that case, $D$ is a single circuit.

If $F$ is an edge $ab$ then $D$ is the disjoint union of at most 2 circuits, which we will call $D_1$ and $D_2$.
We proceed in cases based on the cardinality of $D_1$ and $D_2$.

If $D_1=ac$ and $D_2=bd$ we need to show that $cd$ is not a circuit, ie that it is an edge.
Since $ab$ is an edge and $ac$ is not, and since $\Delta$ is shriekless, $bc$ is an edge.
Then since $bc$ is an edge and $bd$ is not, $cd$ is an edge.

If $D_1=acd$ and $D_2=be$, we need to show that $cde$ is not a circuit.
Since $ab$ is an edge and $eb$ is not, $ae$ is a edge.
Since $cd$ is an edge, either $bc$ or $bd$ is an edge.
Without loss of generality, $bc$ is an edge.
Then since $be$ is not an edge, $ce$ is.
If $de$ is an edge, $bd$ is also, and we have the forbidden configuration $K_5^-$.
So $de$ is not an edge and therefore $cde$ is not a circuit.

If $D_1=acd$ and $D_2=bef$, then suppose $D-F$ is a DUOC, and we will obtain a contradiction.
Then WLOG $ce$ and $df$ are circuits.
Because $ac$ is an edge but $ce$ is not, $ae$ is an edge.
Similarly, $de$, $bc$ and $cf$ are edges.
Because $bf$ is an edge and $df$ is not, $bd$ is an edge.
By considering only vertices $a$, $b$, $c$, $d$ and $e$, we see the vertex-induced subcomplex $K_5^-$, with $ce$ 
	as the missing edge.  
Contradiction.
\end{proof}

\begin{lemma}
\label{shriek and K_5^-}
The shriek and $K_5^-$ are not Nim-regular.
\end{lemma}
\begin{proof}
Non-Nim-regularity of the shriek is an easy proof and can be found in \cite{Ehr-Stein}.

Let the vertices of $K_5^-$ be $a$, $b$, $c$, $d$ and $e$, and $ae$ be the pair of vertices that do not form an edge.
By Corollary ~\ref{circuits in basis}, the circuits are in the basis.
If we let $S=abcde$ and $F=cd$ we find that we can't satisfy condition (C) of the definition of Nim-basis---every 
	choice for the required basis element exceeds some circuit by a face.
\end{proof}

There is a simple alternate characterization of shriekless graphs not containing $K_5^-$.
Consider the following binary relation: For all vertices $a$ and $b$ of a graph $\Delta$,
\begin{enumerate}
	\item[] $a \sim a$ and,
	\item[] $a \sim b$ if and only if $ab$ is not an edge of $\Delta$.
\end{enumerate}
\begin{proposition}
\label{shriekless iff partition}
$\Delta$ is shriekless if and only if the relation ``$\sim$'' is an equivalence relation. 
Alternately $\Delta$ is shriekless if and only if its complement is a disjoint union of complete graphs.
(The {\em complement} is the graph $\Delta^c$ with the same vertices such that $ab$ is an 
	edge of $\Delta^c$ if and only if $ab$ is not an edge of $\Delta$.)
\end{proposition}
\begin{proof}
The relation is reflexive and symmetric in any case.
The requirement that a graph be shriekless is equivalent to the following:  
For vertices $a$, $b$ and $c$, if $ab$ and $ac$ are not edges, then $bc$ is not an edge.
This is the transitive property of the relation.
The statement about $\Delta^c$ follows easily.
\end{proof}
An immediate consequence of Proposition ~\ref{shriekless iff partition} is that isomorphism classes of shriekless 
	graphs correspond to integer partitions.
\begin{proposition}
\label{complement characterization}
Shriekless graphs not containing $K_5^-$ correspond to integer partitions which either have three or fewer parts
	or whose parts are all of size one.
Alternately, the complement of such a graph either has no edges or consists of the the disjoint union of three or 
	fewer complete graphs. 
\end{proposition}
\begin{proof}
The complement of $K_5^-$ is a graph on five vertices with only one edge.
It is clear that the complement $\Delta^c$ of a shriekless graph will contain $(K_5^-)^c$ if and only if 
	we can find four components of $\Delta^c$ such that not all four are isolated vertices.
The statement about integer partitions follows easily. 
\end{proof}

Assembling these results yields the

\begin{proof}[Proof of Theorem ~\ref{Nim-DUOC for graphs}]
By definition, (ii) implies (i).
Propositions ~\ref{shriekless graphs satisfy C} and ~\ref{shriekless no K_5^- implies B}, taken together, state that 
	(iii) implies (ii).
By Lemma ~\ref{Nim-basis of subcomplex} and Lemma ~\ref{shriek and K_5^-}, we know that (i) implies (iii).
Proposition ~\ref{complement characterization} states that (iii) holds if and only if (iv) holds. 
\end{proof}


\section{Remarks on the General Case}

The obvious question is whether we can carry out similar proofs for complexes of dimension 2 and higher.
We conjecture that the answer is ``yes,'' but the complexity of the proof would be astronomical, even for dimension 2.
Hidden in the proof of Proposition ~\ref{shriekless graphs satisfy C} is an enumeration of all isomorphism classes 
	of shriekless graphs on 4 or fewer vertices.
Analogously, by Lemma ~\ref{two faces for C}, if we want to find the minimal 2-complexes whose DUOCs violate (C), 
	we need to know all the shriekless 2-complexes on 6 or fewer vertices, because 6 is the largest
	number of vertices that can make up two disjoint faces. 

The author wrote a Prolog program to find all isomorphism-classes of 2-complexes on 6 or fewer vertices.
The DUOCs of each complex satisfy (C) unless the complex contains the shriek or one of the following minors:
(We use the notation $[n]=\lbrace 1,2, \ldots, n \rbrace$).
\begin{enumerate}
\item
The complex on $[4]$ with facets 123, 14 and 24.
\item
The complex on $[4]$ with facets 123, 124 and 34.
\item
The complex on $[5]$ with complete 1-skeleton and a single 2-face.
\item
The complex on $[5]$ with complete 1-skeleton and 2-faces 123, 124 and 134.
\item
The complex on $[5]$ with complete 1-skeleton and all 2-faces present EXCEPT 123, 124, and 134.
\item
The complex on $[6]$ with complete 1-skeleton and all 2-faces present EXCEPT 123, 145, and 246.
\end{enumerate}
Furthermore, it can be checked that none of these minors is Nim-regular, a fact that would be necessary for a 
	2-dimensional version of Theorem ~\ref{Nim-DUOC for graphs}.

However, proving a 2-dimensional version of Proposition ~\ref{shriekless no K_5^- implies B} by an analogous method 
	would be a huge computational task.
By Lemma ~\ref{simplified B} the excluded minors for graphs must necessarily have six or fewer vertices.
This is because the largest set of vertices we have to consider is when $|F|=2$ and $D$ is the disjoint union of two 
	circuits, each of which has cardinality 3.
In two dimensions, we would have to consider the case where $|F|=3$ and $D$ is the disjoint union of three circuits,
	each of which has cardinality 4.
Thus, finding the excluded minors for a 2-dimensional version of Proposition ~\ref{shriekless no K_5^- implies B} 
	would involve enumerating a large number of the 2-complexes on 12 vertices.
However, it is possible that some characterization of the excluded minors could be found, which would reduce the 
	complexity sufficiently.

In particular, it is possible that such a characterization could arise from a generalization of 
	Proposition ~\ref{complement characterization} to higher dimensions.
However, such a generalization is not likely to be simple.
Presumably a two-dimensional complex would give rise to a ternary relation, rather than a well-understood binary 
	relation like equivalence.

Or we might hope to answer Question ~\ref{main question} directly, without considering excluded minors.
The following may be useful.

\begin{lemma}
\label{(B) is enough}
If $\Delta$ is Nim-regular with basis $\B$ and the DUOCs satisfy (B) then $\B=\lbrace DUOCs\rbrace$.
\end{lemma}
\begin{proof}
Let $\B=\D \uplus \E$, where $\D=\B \cap \lbrace DUOCs\rbrace$.
Suppose $\E \ne \emptyset$.
Let $E$ be minimal in $\E$.
Since $E$ is not a DUOC, let $D$ be maximal among DUOCs in $E$.  
Since $E$ is minimal in $\E$, every basis element contained in $D$ is a DUOC.
By hypothesis, $D$ does not exceed any basis element by a face, so by Lemma ~\ref{basis inclusiveness}, $D \in \B$.
But because $D$ is a maximal DUOC in $E$, $E-D$ is a face.
This is a contradiction to property (B), and therefore $\B=\D$.
Because no DUOCs differ by a face, by Lemma ~\ref{basis inclusiveness}, $\B=\lbrace DUOCs\rbrace$.
\end{proof}

In light of Lemmas ~\ref{(B) is enough} and ~\ref{simplified B}, Question ~\ref{main question} is equivalent 
	to the following:

\begin{question}
Let $\Delta$ be a Nim-regular complex, $F$ a nonempty face, $\lbrace D_i \rbrace$ a minimal cover of $F$ by circuits 
	and $D=\uplus_iD_i$.
Is it necessarily true that $D-F$ is not a DUOC?
\end{question}


\newcommand{\journalname}[1]{\textrm{#1}}
\newcommand{\booktitle}[1]{\textrm{#1}}

\begin{thebibliography}{9}

\bibitem{Ehr-Stein}
R. Ehrenborg and E. Steingr\'\i msson,
\textit{Playing Nim on a simplicial complex},
\journalname {Electron. J. Combin.}{\bf 3}(1996),\#R9.

\end{thebibliography}


\end{document}