Lighting up all elements of a poset by toggling upsets

Question

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:

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:

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:

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.

Answer 1

Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck).

The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements $x,y$ of the poset $P$, I say that $x$ is covered by $y$ if $x\geq y$, $x \neq y$, and there are no elements in between (i.e., $y$ is just above $x$ in the Hasse diagram of $P$). Let me now show claim (*): we can then assume without loss of generality that $P$ is such that:

1. there are no elements $x$ of $P$ that cover exactly one element; and
2. for every minimal element $x$ of $P$, $x$ is covered by at least two elements.

I will show this by taking a poset $P$ such that it has an $x$ satisfying condition 1. or 2., and then considering the poset $P'$ where we have removed $x$, and show that if $P'$ is winnable then so is $P$. Assume first that $x$ satisfies 1., and let $\mathbf{s}$ be a winning sequence for $P'$ (a sequence of moves that goes from $\emptyset$ to $P'$). Then it is easy to see that $\mathbf{s}$ is also a winning sequence for $P$; indeed the state of $x$ (on or off) will always follow the state of its unique child, and we never need to click on $x$ (this can also be explained by checking that $\mu_P(x) = 0$), so all moves are valid. Assume now that $x$ satisfies 2., and again let $\mathbf{s}$ be a winning sequence for $P'$. Let $p$ be the unique parent of $x$ in $P$, and let $a = \mu_P(p)$. It is easy to show that $\mu_{P'}(p) = a+1$ and that $\mu_{P'}(y) = \mu_P(y)$ for all $y \in P'$, $y \neq p$. I then consider two cases:

• $a<0$. We can then obtain a winning sequence for $P$ as follows: first, play an on-move on $x$, then play an off-move on $p$ (this is legal since $a<0$), and then play the sequence $\mathbf{s}$. Observe that we have $a+1 \leq 0$, so in the whole sequence we will only play off-moves on $p$, and it is clear that all the moves are valid and that we end up with everything being on, so that this is indeed a winning sequence for $P$.
• $a \geq 0$. In this case $a+1>0$, which mean that in $\mathbf{s}$ we will only play on-moves on $p$, and we will play at least one. We then obtain a winning sequence for $P$ as follows: play the sequence $\mathbf{s}$, but the very first time we play an on-move on $p$, play an on-move on $x$ instead. Again, it is easy to see that this is indeed a winning sequence for $P$.

This concludes the proof of claim (*).

If we look at the first example in the question, we can deal with it using claim (*): we can eliminate $E$ because it satisfies condition 1., then we can eliminate $A$, $B$ and $C$ (because they satisfy condition 2.), and we end up with only one node ($D$), and this is clearly a poset that is winnable. However for the second example in the question, we can eliminate $G$ (it satisfies condition 2.), but then there is nothing to eliminate, so here he'd need something else to show that $P'$ is winnable.

Claim (*) implies in particular that join-semilattices that are obtained from dismantable lattices by removing the bottom element are winnable; these are lattices that can be emptied by recursively removing the doubly irreducible elements, see Kelly, David; Rival, Ivan, Crowns, fences, and dismantlable lattices, Can. J. Math. 26, 1257-1271 (1974). This paper shows in particular that dismantable lattices are exactly the lattices that are crown-free (see the paper for the definition), so if we want to solve our problem for join-semilattices only (instead of for all posets), it becomes equivalent to the following:

Can we win for every join-semilattice that has a crown? (Note that the second example in the question is a join-semilattice that has a crown).

Other than claim (*), we have some code (there) to decide if a given poset is winnable or not, and if yes to visualize the winning strategy. In particular we have generated a lot of join-semilattices and found no counter-example so far.

We are also working on a generalization of this problem: see this note.