Nim-Regularity of Graphs

NEW

Problem: Reconstructed statement: In a finite abstract simplicial complex $\Delta$, a circuit is a minimal non-face, and a DUOC is the empty set or a disjoint union of circuits. A complex is Nim-regular if it has a Nim-basis in the sense of Reading’s Definition 2.2. Reading’s Question 4.2 asks whether, whenever $\Delta$ is Nim-regular, $F\neq\varnothing$ is a face, $\{D_i\}$ is a minimal cover of $F$ by pairwise disjoint circuits, and $D=\biguplus_iD_i$, it follows that $D-F$ is not a DUOC.

Result: The answer is no.

Let

$$X=\{1,2,3\},\qquad Y=\{4,5,6\},\qquad V=X\sqcup Y.$$

Define $\Delta$ on $V$ by taking as faces all subsets of size at most $2$, and all $3$-subsets except $X$ and $Y$. There are no faces of size $\ge4$.

The circuits are exactly

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

Let $\mathcal N=\{\varnothing\}\cup\{\text{circuits of }\Delta\}$. One checks Reading’s Nim-basis axioms as follows. Axiom (A) is immediate. For (B), no nonempty circuit contains another circuit, and a circuit itself is not a face, so no element of $\mathcal N$ exceeds another by a face. For (C), using the standard reduction to $S\cap F=\varnothing$, put $P=S\cup F$. If $P$ is a face, take $G=P$, $K=\varnothing$. If $P$ is not a face, choose a circuit $C\subseteq P$ so that $G=P-(C-F)$ is a face, and set $K=C\cap F$; then $(S-G)\sqcup K=C\in\mathcal N$. Such a $C$ exists by the type of $P$ relative to $X,Y$: use $C=P$ for types $(3,0),(0,3),(2,2)$; use $C=X$ for $(3,1)$, symmetrically $C=Y$ for $(1,3)$; handle $(3,2)$ by using $X$ if $|F\cap X|\le1$, otherwise a $(2,2)$-circuit containing the unique vertex of $X-F$, one vertex of $F\cap X$, and the two vertices of $P\cap Y$; the $(2,3)$ case is symmetric; for $P=V$, choose a $(2,2)$-circuit meeting $F$ in at most one vertex. Thus $\Delta$ is Nim-regular.

Now take

$$F=\{3,6\},\qquad D_1=X,\qquad D_2=Y.$$

Then $F$ is a nonempty face, $D_1,D_2$ are disjoint circuits, and $\{D_1,D_2\}$ is a minimal cover of $F$: removing $D_1$ loses $3$, and removing $D_2$ loses $6$. But

$$D-F=(X\sqcup Y)-\{3,6\}=\{1,2,4,5\},$$

which is itself a $(2,2)$-circuit, hence a DUOC. This directly falsifies Question 4.2.

Citation: Definitions and the question are from Nathan Reading, “Nim-Regularity of Graphs,” Electron. J. Combin. 6 (1999), #R11, Definitions 2.2 and 2.5, Question 4.2. The counterexample above is supplied here.