IMPARTIAL ACHIEVEMENT GAMES ON CONVEX GEOMETRIES

NEW

Problem: The conjecture is best formalized as follows. Let $(S,\mathcal K)$ be a finite convex geometry in the McCoy–Sieben sense: $S\in\mathcal K$, $\mathcal K$ is closed under intersections, and every proper $K\in\mathcal K$ can be enlarged by one element while staying in $\mathcal K$; $\emptyset$ is not assumed convex. Then $(S,\mathcal K)$ is isomorphic to a deletion of an affine convex geometry: there are a finite point set $T\subset\mathbb R^d$, a subset $D\subseteq T$, and a bijection $S\cong T\setminus D$, such that

Unlike the known $\emptyset$-closed case, $D$ need not be convex.

This is the natural reconstruction because Remark 2.9 explicitly refers to the Kashiwabara–Nakamura–Okamoto affine representation theorem for convex geometries containing $\emptyset$, and says that in the desired extension the deleted set need not be convex.

Result: The reconstructed conjecture is true.

Let

Since $\mathcal K$ is intersection-closed, $I\in\mathcal K$. Every convex set contains $I$. Put $S_0=S\setminus I$ and

Then $(S_0,\mathcal K_0)$ is a finite convex geometry with $\emptyset\in\mathcal K_0$: intersection-closure is immediate, and accessibility follows because if $L\ne S_0$, then $I\cup L\ne S$, so some $a\in S\setminus(I\cup L)=S_0\setminus L$ satisfies $I\cup L\cup\{a\}\in\mathcal K$.

By the affine representation theorem of Kashiwabara–Nakamura–Okamoto, there are finite point sets $G,Q\subset\mathbb R^m$, with $G$ labeled by $S_0$, such that for all $L\subseteq S_0$,

Embed $G\cup Q$ into the hyperplane $H=\mathbb R^m\times\{0\}\times\{1\}\subset\mathbb R^{m+2}$. Add two new deleted points $p,q$ in the parallel hyperplane of last coordinate $0$, and place the elements of $I$ as distinct points on the open segment $(p,q)$. Let

Every point of $I$ lies in $\operatorname{conv}(D)$. Hence if $A\subseteq S$ omits any element of $I$, then $A\cup D$ is not convex in $T$. If $A=I\cup L$ with $L\subseteq S_0$, then

because $I\subseteq\operatorname{conv}\{p,q\}$. Intersecting this convex hull with the hyperplane containing $G\cup Q$ gives exactly $\operatorname{conv}(L\cup Q)$. Therefore

Thus the convex subsets of the deletion by $D$ are exactly the original members of $\mathcal K$.

When $I\ne\emptyset$, the deleted set $D$ is indeed non-convex in $T$, since $\operatorname{conv}(D)$ contains the points of $I\not\subseteq D$. No repair is needed.

Citation: Uses the affine representation theorem for $\emptyset$-closed finite convex geometries from Kashiwabara, Nakamura, and Okamoto, “The affine representation theorem for abstract convex geometries,” Computational Geometry 30 (2005), 129–144.