<p>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).</p>

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

<ol>
<li>there are no elements <span class="math-container">$x$</span> of <span class="math-container">$P$</span> that cover exactly one element; and</li>
<li>for every minimal element <span class="math-container">$x$</span> of <span class="math-container">$P$</span>, <span class="math-container">$x$</span> is covered by at least two elements.</li>
</ol>

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

<ul>
<li><span class="math-container">$a&lt;0$</span>. We can then obtain a winning sequence for <span class="math-container">$P$</span> as follows: first, play an on-move on <span class="math-container">$x$</span>, then play an off-move on <span class="math-container">$p$</span> (this is legal since <span class="math-container">$a&lt;0$</span>), and then play the sequence <span class="math-container">$\mathbf{s}$</span>. Observe that we have <span class="math-container">$a+1 \leq 0$</span>, so in the whole sequence we will only play off-moves on <span class="math-container">$p$</span>, 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 <span class="math-container">$P$</span>.</li>
<li><span class="math-container">$a \geq 0$</span>. In this case <span class="math-container">$a+1&gt;0$</span>, which mean that in <span class="math-container">$\mathbf{s}$</span> we will only play on-moves on <span class="math-container">$p$</span>, and we will play at least one. We then obtain a winning sequence for <span class="math-container">$P$</span> as follows: play the sequence <span class="math-container">$\mathbf{s}$</span>, but the very first time we play an on-move on <span class="math-container">$p$</span>, play an on-move on <span class="math-container">$x$</span> instead. Again, it is easy to see that this is indeed a winning sequence for <span class="math-container">$P$</span>.</li>
</ul>

<p>This concludes the proof of claim (*).</p>

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

<p>Claim (*) implies in particular that join-semilattices that are obtained from <em>dismantable</em> lattices by removing the bottom element are winnable; these are lattices that can be emptied by recursively removing the <em>doubly irreducible</em> elements, see 
<em>Kelly, David; Rival, Ivan</em>, <a href="http://dx.doi.org/10.4153/CJM-1974-120-2" rel="nofollow noreferrer"><strong>Crowns, fences, and dismantlable lattices</strong></a>, 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:</p>

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

<p>Other than claim (*), we have some code (<a href="https://gitlab.com/Gruyere/a-game-on-dags" rel="nofollow noreferrer">there</a>) 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.</p>

<p>We are also working on a generalization of this problem: see <a href="http://mikael-monet.net/share/note.pdf" rel="nofollow noreferrer">this note</a>.</p>

CC BY-SA 4.0
2020-05-03T10:35:47.730Z
2020-05-03T11:27:05.770Z
2020-05-03T11:27:05.770Z
M.Monet
<p>I consider the following game on a finite poset <span class="math-container">$(P, &lt;)$</span>. At each point of the game, I have a set of elements <span class="math-container">$S$</span> of the poset which are "on", and all others are "off". Initially <span class="math-container">$S = \emptyset$</span>. Each move of the game consists of choosing one element <span class="math-container">$x$</span> of the poset; then I consider its upset <span class="math-container">$U_x = \{y \in P \mid x \leq y\}$</span> and:</p>

<ul>
<li>If all elements of <span class="math-container">$U_x$</span> are off, then I can play an <em>on-move</em> on <span class="math-container">$x$</span>, which turns all of <span class="math-container">$U_x$</span> on, so <span class="math-container">$S$</span> becomes <span class="math-container">$S \cup U_x$</span> (with the union being disjoint).</li>
<li>If all elements of <span class="math-container">$U_x$</span> are on, I can play an <em>off-move</em> on <span class="math-container">$x$</span> and turn all of <span class="math-container">$U_x$</span> off, so <span class="math-container">$S$</span> becomes <span class="math-container">$S \setminus U_x$</span> (with <span class="math-container">$U_x \subseteq S$</span>).</li>
<li>Otherwise I cannot currently play on this <span class="math-container">$x$</span>.</li>
</ul>

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

<p>My question is: <strong>What are the posets on which there is a way to win the game? In particular, can we always win when <span class="math-container">$P$</span> is a join-semilattice, i.e., any nonempty subset of elements has a least upper bound?</strong></p>

<p>For a simple example of the game, consider <span class="math-container">$P$</span> with the following Hasse diagram:</p>

<p><a href="https://i.sstatic.net/7VbO0.gif" rel="noreferrer"><img src="https://i.sstatic.net/7VbO0.gif" alt="Easy example"></a></p>

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

<ul>
<li>first play an on-move on <span class="math-container">$A$</span> (and <span class="math-container">$S$</span> becomes <span class="math-container">$\{A, D, E\}$</span>),</li>
<li>then play an off-move on <span class="math-container">$D$</span> (and <span class="math-container">$S$</span> becomes <span class="math-container">$\{A\}$</span>),</li>
<li>then play an on-move on <span class="math-container">$B$</span> (and <span class="math-container">$S$</span> becomes <span class="math-container">$\{A, B, D, E\}$</span>),</li>
<li>then play an off-move on <span class="math-container">$D$</span> again (and <span class="math-container">$S$</span> becomes <span class="math-container">$\{A, B\}$</span>),</li>
<li>last play an on-move on <span class="math-container">$C$</span> (and <span class="math-container">$S$</span> becomes <span class="math-container">$P$</span> and I have won).</li>
</ul>

<p>For a more complicated example, consider the following:</p>

<p><a href="https://i.sstatic.net/31j11.gif" rel="noreferrer"><img src="https://i.sstatic.net/31j11.gif" alt="enter image description here"></a></p>

<p>I have animated the steps on a winning sequence: on-move on <span class="math-container">$A$</span>, off-move on <span class="math-container">$D$</span>, on-move on <span class="math-container">$B$</span>, off-move on <span class="math-container">$E$</span>, on-move on <span class="math-container">$G$</span>, off-move on <span class="math-container">$F$</span>, on-move on <span class="math-container">$C$</span>. Note that this is a bit tricky to find, e.g., starting a play with <span class="math-container">$G$</span> cannot win.</p>

<p>There is a relationship between the game and the <a href="https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula#On_posets" rel="noreferrer">Möbius inversion formula</a> on posets. Specifically, if I define <span class="math-container">$\mu(x) = 1 - \sum_{y &lt; x} \mu(y)$</span>, in particular <span class="math-container">$\mu(x) = 1$</span> if <span class="math-container">$x$</span> has no ancestors, then the sign and absolute value of <span class="math-container">$\mu(x)$</span> tells me which types of move I should play on <span class="math-container">$x$</span>, and how many. In particular when <span class="math-container">$\mu(x) = 0$</span>, we should never play on <span class="math-container">$x$</span>, as with the vertex <span class="math-container">$H$</span> in the example above. Another way to see this is about a restricted way to compute the <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="noreferrer">inclusion-exclusion formula</a> with no cancellations.</p>

<p>I already know that we cannot win on every poset, as a computer search by <a href="https://louis.jachiet.com/" rel="noreferrer">Louis Jachiet</a> turned out the following poset, where there is no winning strategy (checked by exhaustive search). There is no counterexample with less than 9 elements:</p>

<p><a href="https://i.sstatic.net/ur4vL.png" rel="noreferrer"><img src="https://i.sstatic.net/ur4vL.png" alt="A minimal pathological case"></a></p>

<p>For our purposes we are interested in knowing whether the game can always be won on <em>join-semilattices</em>, 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 <span class="math-container">$A$</span> and <span class="math-container">$B$</span>), 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.</p>

<p>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 <a href="https://homes.cs.washington.edu/~suciu/jacm-dichotomy.pdf" rel="noreferrer">safe queries over probabilistic databases</a>.</p>

CC BY-SA 4.0
2019-10-14T15:09:43.827Z
"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.
Neal Young
CC BY-SA 4.0
2019-10-14T15:29:10.593Z
@NealYoung: Yes I'm drawing edges from bottom to top, following the usual convention for Hasse diagrams of posets.
Antoine Amarilli 'a3nm'
<graph-theory><boolean-functions><directed-acyclic-graph><partial-order><order-theory>
Lighting up all elements of a poset by toggling upsets
Antoine Amarilli 'a3nm'
# Lighting up all elements of a poset by toggling upsets

(Asked by: username_0 on 2019-10-12)

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](https://i.sstatic.net/7VbO0.gif)](https://i.sstatic.net/7VbO0.gif)

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](https://i.sstatic.net/31j11.gif)](https://i.sstatic.net/31j11.gif)

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](https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula#On_posets) 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](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) with no cancellations.

I already know that we cannot win on every poset, as a computer search by [Louis Jachiet](https://louis.jachiet.com/) 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](https://i.sstatic.net/ur4vL.png)](https://i.sstatic.net/ur4vL.png)

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](https://homes.cs.washington.edu/~suciu/jacm-dichotomy.pdf).

**Tags:** graph-theory, boolean-functions, directed-acyclic-graph, partial-order, order-theory

> **Comments:**
> **username_1**: "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.  
> **username_0**: @NealYoung: Yes I'm drawing edges from bottom to top, following the usual convention for Hasse diagrams of posets.  

---

## 1 answers

### Answer by username_2 on 2020-05-03. Score: 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**](http://dx.doi.org/10.4153/CJM-1974-120-2), 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](https://gitlab.com/Gruyere/a-game-on-dags)) 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](http://mikael-monet.net/share/note.pdf).


---

