7
$\begingroup$

I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. Each move of the game consists of choosing one element $x$ of the poset; then I consider its upset $U_x = \{y \in P \mid x \leq y\}$ and:

  • If all elements of $U_x$ are off, then I can play an on-move on $x$, which turns all of $U_x$ on, so $S$ becomes $S \cup U_x$ (with the union being disjoint).
  • If all elements of $U_x$ are on, I can play an off-move on $x$ and turn all of $U_x$ off, so $S$ becomes $S \setminus U_x$ (with $U_x \subseteq S$).
  • Otherwise I cannot currently play on this $x$.

My goal is to switch on all elements of the poset, i.e., find a sequence of moves that reaches $S = P$, from the initial configuration $S = \emptyset$. However, I impose that for each element $x$, all my plays on $x$ in the sequence are of the same type, i.e., if I play an on-move on $x$ then I am not allowed to play an off-move on $x$ at any point of the sequence -- but I can play other on-moves on $x$ if I want. (If we don't impose this, then it's not too hard to show by induction that we can always win.)

My question is: What are the posets on which there is a way to win the game? In particular, can we always win when $P$ is a join-semilattice, i.e., any nonempty subset of elements has a least upper bound?

For a simple example of the game, consider $P$ with the following Hasse diagram:

Easy example

I have animated a winning strategy on the picture. Initially all vertices are off (=white). Then we do the following:

  • first play an on-move on $A$ (and $S$ becomes $\{A, D, E\}$),
  • then play an off-move on $D$ (and $S$ becomes $\{A\}$),
  • then play an on-move on $B$ (and $S$ becomes $\{A, B, D, E\}$),
  • then play an off-move on $D$ again (and $S$ becomes $\{A, B\}$),
  • last play an on-move on $C$ (and $S$ becomes $P$ and I have won).

For a more complicated example, consider the following:

enter image description here

I have animated the steps on a winning sequence: on-move on $A$, off-move on $D$, on-move on $B$, off-move on $E$, on-move on $G$, off-move on $F$, on-move on $C$. Note that this is a bit tricky to find, e.g., starting a play with $G$ cannot win.

There is a relationship between the game and the Möbius inversion formula on posets. Specifically, if I define $\mu(x) = 1 - \sum_{y < x} \mu(y)$, in particular $\mu(x) = 1$ if $x$ has no ancestors, then the sign and absolute value of $\mu(x)$ tells me which types of move I should play on $x$, and how many. In particular when $\mu(x) = 0$, we should never play on $x$, as with the vertex $H$ in the example above. Another way to see this is about a restricted way to compute the inclusion-exclusion formula with no cancellations.

I already know that we cannot win on every poset, as a computer search by Louis Jachiet turned out the following poset, where there is no winning strategy (checked by exhaustive search). There is no counterexample with less than 9 elements:

A minimal pathological case

For our purposes we are interested in knowing whether the game can always be won on join-semilattices, i.e., every nonempty set of elements has a least upper bound (i.e., a unique descendant which is as high as possible). This is not the case above (consider $A$ and $B$), and this requirement seems to constrain the structure of the graph, but we don't know how to prove the claim (or whether it is true). We have been running a computer search for join-semilattices on which the game cannot be won, but we haven't found a counterexample yet.

As for the motivation of the problem, it was originally about expressing certain kinds of Boolean functions using restricted classes of circuits, with connections to safe queries over probabilistic databases.

$\endgroup$
  • $\begingroup$ "a least upper bound (i.e., a unique descendant which is as high as possible)." Do you mean a unique ancestor which is as low as possible? Oh, I see, the descendants of a node are above it in the diagrams you draw. $\endgroup$ – Neal Young Oct 14 '19 at 15:09
  • $\begingroup$ @NealYoung: Yes I'm drawing edges from bottom to top, following the usual convention for Hasse diagrams of posets. $\endgroup$ – a3nm Oct 14 '19 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.