Nim-Regularity of Graphs

NEW

Problem: Reconstructed statement: for a finite abstract simplicial complex $\Delta$, if a Nim-basis exists, then the Nim-basis is the family of all DUOCs, i.e. all subsets that are disjoint unions of circuits, where a circuit is a minimal non-face. This is the natural Reading/Ehrenborg–Steingrímsson formulation; the wording is slightly ambiguous, but Reading’s later DUOC condition concerns the full DUOC family.

Result: The statement is false.

Let $V=A\sqcup B$, with

$$A=\{1,2,3\},\qquad B=\{4,5,6\}.$$

Define $\Delta$ to have as faces all subsets of size at most $2$, and all $3$-subsets except $A$ and $B$. No subset of size $\ge4$ is a face.

The circuits are exactly

$$A,\quad B,\quad\text{and the }4\text{-sets }C\text{ with }|C\cap A|=|C\cap B|=2.$$

Indeed, $A,B$ are missing triangles, and a $4$-set is minimal non-face precisely when it contains neither $A$ nor $B$.

Let

$$\mathcal B=\{\varnothing\}\cup\{\text{circuits of }\Delta\}.$$

We verify that $\mathcal B$ is a Nim-basis. Condition (A) is immediate. For (B), no nonempty face can be the difference of two elements of $\mathcal B$: circuits are nonfaces, and no circuit properly contains another circuit.

For (C), reduce to $S\cap F=\varnothing$. Put $P=F\cup S$. If $P$ is a face, take $G=P$, $K=\varnothing$. If $P$ is not a face, choose a circuit $C\subseteq P$ such that

$$G=P-(C-F)$$

is a face, and set $K=C\cap F$. Then $K\subseteq F\subseteq G$, $G-F\subseteq S$, and

$$(S-G)\sqcup K=C\in\mathcal B.$$

Such $C$ exists by cases on $(|P\cap A|,|P\cap B|)$: use $C=P$ for types $(3,0),(0,3),(2,2)$; use $C=A$ for $(3,1)$, symmetrically for $(1,3)$; for $(3,2)$, use $A$ if $|F\cap A|\le1$, otherwise use a $(2,2)$-circuit containing the unique vertex of $A-F$, one vertex of $F\cap A$, and the two vertices of $P\cap B$. The $(2,3)$ case is symmetric. For $P=V$, choose a $(2,2)$-circuit meeting $F$ in at most one vertex; then $G$ has type $(1,1),(2,1)$, or $(1,2)$, hence is a face. Thus $\mathcal B$ is a Nim-basis.

However, the full vertex set

$$V=A\sqcup B$$

is a disjoint union of two circuits, hence is a DUOC. But $V\notin\mathcal B$. In fact the full DUOC family is not a Nim-basis: the circuit

$$C=\{1,2,4,5\}$$

and the DUOC $V$ satisfy

$$V=C\sqcup\{3,6\},$$

where $\{3,6\}$ is a nonempty face, violating Nim-basis condition (B).

So $\Delta$ is Nim-regular, but its DUOCs do not form a Nim-basis. This refutes the reconstructed conjecture.

Citation: Definitions and the question are from Nathan Reading, “Nim-Regularity of Graphs,” Electronic Journal of Combinatorics 6 (1999), #R11. The counterexample above is supplied here.