<p>For a set <span class="math-container">$V = \{0,\ldots,k\}$</span> of <em>variables</em>, let <span class="math-container">$\mathbf{G}_V$</span> be the undirected graph with set of vertices <span class="math-container">$\{S \subseteq V\}$</span> and set of edges <span class="math-container">$\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+1\}$</span>, in other words the underlying undirected graph of the Hasse diagram of the powerset of <span class="math-container">$V$</span>. Let <span class="math-container">$\phi$</span> be a Boolean function on variables <span class="math-container">$V$</span>, that we see as a set of subsets of <span class="math-container">$V$</span>. Define the graph <span class="math-container">$\mathbf{G}_V[\phi]$</span> to be the subgraph of <span class="math-container">$\mathbf{G}_V$</span> <a href="https://en.wikipedia.org/wiki/Induced_subgraph" rel="noreferrer">induced</a> by <span class="math-container">$\phi$</span>.</p>

<p><strong>I conjecture the following:</strong></p>

<p>If <span class="math-container">$\phi$</span> is monotone and <span class="math-container">$\sum_{S \in \phi} (-1)^{|S|} = 0$</span>, i.e., <span class="math-container">$\phi$</span> has as many satisfying valuations of even and odd size, then <span class="math-container">$\mathbf{G}_V[\phi]$</span> or <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> has a <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)" rel="noreferrer">perfect matching</a>.</p>

<p><strong>What I know:</strong></p>

<ul>
<li>For a Boolean function <span class="math-container">$\phi$</span>, <span class="math-container">$\sum_{S \in \phi} (-1)^{|S|}$</span> is called the <em>Euler characteristic of <span class="math-container">$\phi$</span></em>.</li>
<li>Observe that <span class="math-container">$\sum_{S \in \phi} (-1)^{|S|} = - \sum_{S \in \lnot\phi} (-1)^{|S|}$</span> (<span class="math-container">$=0$</span> in our case).</li>
<li>Of course, if <span class="math-container">$\sum_{S \in \phi} (-1)^{|S|} \neq 0$</span>, then neither <span class="math-container">$\mathbf{G}_V[\phi]$</span> nor <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> can have a perfect matching.</li>
<li><p>My claim does not hold if we do not impose <span class="math-container">$\phi$</span> to be monotone. For example, consider the following Boolean function (the satisfying valuations of <span class="math-container">$\phi$</span> are colored):<a href="https://i.sstatic.net/shSF3.png" rel="noreferrer"><img src="https://i.sstatic.net/shSF3.png" alt="not monotone"></a>
<span class="math-container">$\sum_{S \in \phi} (-1)^{|S|} = 0$</span>, but <span class="math-container">$\mathbf{G}_V[\phi]$</span> does not have a perfect matching since, for instance, <span class="math-container">$\{3,4\}$</span> is isolated. The same holds for <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> by considering <span class="math-container">$\{0,3,4\}$</span>.</p></li>
<li><p>There are examples where both have a perfect matching, and examples where only one does. Here is one such example (this is actually the smallest such example):<a href="https://i.sstatic.net/81jbr.png" rel="noreferrer"><img src="https://i.sstatic.net/81jbr.png" alt="enter image description here"></a>
<span class="math-container">$\sum_{S \in \phi} (-1)^{|S|} = 0$</span>, <span class="math-container">$\mathbf{G}_V[\phi]$</span> does not have a perfect matching, but <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> does (trust me).
I suspect that, if the claim is true, what decides if <span class="math-container">$\mathbf{G}_V[\phi]$</span> or <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> has a perfect matching is <span class="math-container">$\max(|\phi|,|\lnot\phi|)$</span>.</p></li>
<li><p>There are no counterexamples to my claim for <span class="math-container">$k \leq 5$</span>.</p></li>
<li>In the particuliar case where <span class="math-container">$\lnot \phi$</span> corresponds to a <a href="https://en.wikipedia.org/wiki/Collapse_(topology)" rel="noreferrer">collapsible abstract simplicial complex</a> (an <a href="https://en.wikipedia.org/wiki/Abstract_simplicial_complex" rel="noreferrer">abstract simplicial complex</a> is just another word for the negation of a monotone Boolean function), then <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> has a perfect matching.</li>
</ul>

<p><strong>What I have tried:</strong> </p>

<p>Since <span class="math-container">$\mathbf{G}_V[\phi]$</span> and <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span> are bipartite, I've tried using:</p>

<ul>
<li><a href="https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)" rel="noreferrer">Kőnig's theorem</a>. So here I would need to show that for <span class="math-container">$\mathbf{G}_V[\phi]$</span> (or <span class="math-container">$\mathbf{G}_V[\lnot\phi]$</span>), there is no vertex cover of size less that <span class="math-container">$|\phi|/2$</span> (since the set of all subsets in <span class="math-container">$\phi$</span> of even size is obviously a vertex cover of <span class="math-container">$\mathbf{G}_V[\phi]$</span>).</li>
<li><a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation" rel="noreferrer">Hall's mariage theorem</a>. Here I would need to show that, for every subset <span class="math-container">$B$</span> of <span class="math-container">$\phi$</span> containing only subsets of even size, the subsets of <span class="math-container">$B$</span> are (collectively) adgacent to at least <span class="math-container">$|B|$</span> vertices in <span class="math-container">$\mathbf{G}_V[\phi]$</span>.</li>
</ul>

<p>with no luck so far. I should add that I don't have any particular reason for why this should be true, but this came to me as an intriguing question while I was working on something else.</p>

CC BY-SA 4.0
2019-04-02T22:30:44.417Z
Do you have a higher definition version of the second image so that we can read it? Also, is $\phi$ the vertices colored in green, or the others?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-04-03T14:04:42.220Z
I updated the figures, thanks. Yes, $\phi$ is the colored vertices (but it doesn't really matter if we consider $\phi$ or its negation).
M.Monet
CC BY-SA 4.0
2019-04-18T16:47:30.537Z
Random suggestions: (1) To show that a bipartite graph (as you have here), has a matching, it suffices to show that it has a fractional matching (an assignment of non-negative weights to the edges so that each vertex's edges have total weight 1).  Sometimes this is easier. (2) Is it possible that a positive answer to your question would resolve (notoriously hard) open questions about Sperner properties of lattices?  That would be evidence that it may be hard to answer.
Neal Young
CC BY-SA 4.0
2019-04-18T23:42:39.297Z
Many thanks! It gave me an idea to solve it (though not really related to fractional matchings), I'll check the details when I'll have some time (and I'll also edit my question to mention (1) as a possibility). Can you point to a reference on these open questions about Sperner properties of lattices?
M.Monet
CC BY-SA 4.0
2019-04-19T19:30:31.803Z
I would just like to point out that this (otherwise very nice) question has nothing to do with satisfying Boolean functions, as it is equivalent to the following. If for some downwards closed $\mathcal F \subset \{0,1\}^n$ we have $\sum_{F\in\mathcal F} (-1)^{|F|}=0$, then is there a perfect matching in $\mathcal F$ or $\{0,1\}^n\setminus \mathcal F$?
domotorp
CC BY-SA 4.0
2019-04-19T23:04:35.537Z
@NealYoung Do you have an example of (1) in mind? I saw this method being used in a talk I went to recently, but the example was rather complicated.
Elle Najt
CC BY-SA 4.0
2019-04-20T12:05:11.967Z
Sure.  Any bipartite graph where each vertex has the same degree $d$, has a fractional matching where every edge has weight $1/d$.  Hence, it has a perfect matching.  As for Sperner, I had in mind the question of whether the lattice formed by ideals of the Boolean lattice has the Sperner property.  See e.g. https://escholarship.org/uc/item/8wh6f7rc .
Neal Young
CC BY-SA 4.0
2019-05-26T22:40:47.477Z
(My idea did not work in the end.) @domotorp: yes, this is another way of formulating it
M.Monet
<boolean-functions><matching><monotone>
Perfect matching of monotone Boolean function with null Euler characteristic
M.Monet
# Perfect matching of monotone Boolean function with null Euler characteristic

(Asked by: username_0 on 2019-04-01)

For a set $V = \{0,\ldots,k\}$ of *variables*, let $\mathbf{G}\_V$ be the undirected graph with set of vertices $\{S \subseteq V\}$ and set of edges $\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+1\}$, in other words the underlying undirected graph of the Hasse diagram of the powerset of $V$. Let $\phi$ be a Boolean function on variables $V$, that we see as a set of subsets of $V$. Define the graph $\mathbf{G}\_V[\phi]$ to be the subgraph of $\mathbf{G}\_V$ [induced](https://en.wikipedia.org/wiki/Induced_subgraph) by $\phi$.

**I conjecture the following:**

If $\phi$ is monotone and $\sum\_{S \in \phi} (-1)^{|S|} = 0$, i.e., $\phi$ has as many satisfying valuations of even and odd size, then $\mathbf{G}\_V[\phi]$ or $\mathbf{G}\_V[\lnot\phi]$ has a [perfect matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)).

**What I know:**

* For a Boolean function $\phi$, $\sum\_{S \in \phi} (-1)^{|S|}$ is called the *Euler characteristic of $\phi$*.
* Observe that $\sum\_{S \in \phi} (-1)^{|S|} = - \sum\_{S \in \lnot\phi} (-1)^{|S|}$ ($=0$ in our case).
* Of course, if $\sum\_{S \in \phi} (-1)^{|S|} \neq 0$, then neither $\mathbf{G}\_V[\phi]$ nor $\mathbf{G}\_V[\lnot\phi]$ can have a perfect matching.
* My claim does not hold if we do not impose $\phi$ to be monotone. For example, consider the following Boolean function (the satisfying valuations of $\phi$ are colored):[![not monotone](https://i.sstatic.net/shSF3.png)](https://i.sstatic.net/shSF3.png)
  $\sum\_{S \in \phi} (-1)^{|S|} = 0$, but $\mathbf{G}\_V[\phi]$ does not have a perfect matching since, for instance, $\{3,4\}$ is isolated. The same holds for $\mathbf{G}\_V[\lnot\phi]$ by considering $\{0,3,4\}$.
* There are examples where both have a perfect matching, and examples where only one does. Here is one such example (this is actually the smallest such example):[![enter image description here](https://i.sstatic.net/81jbr.png)](https://i.sstatic.net/81jbr.png)
  $\sum\_{S \in \phi} (-1)^{|S|} = 0$, $\mathbf{G}\_V[\phi]$ does not have a perfect matching, but $\mathbf{G}\_V[\lnot\phi]$ does (trust me).
  I suspect that, if the claim is true, what decides if $\mathbf{G}\_V[\phi]$ or $\mathbf{G}\_V[\lnot\phi]$ has a perfect matching is $\max(|\phi|,|\lnot\phi|)$.
* There are no counterexamples to my claim for $k \leq 5$.
* In the particuliar case where $\lnot \phi$ corresponds to a [collapsible abstract simplicial complex](https://en.wikipedia.org/wiki/Collapse_(topology)) (an [abstract simplicial complex](https://en.wikipedia.org/wiki/Abstract_simplicial_complex) is just another word for the negation of a monotone Boolean function), then $\mathbf{G}\_V[\lnot\phi]$ has a perfect matching.

**What I have tried:**

Since $\mathbf{G}\_V[\phi]$ and $\mathbf{G}\_V[\lnot\phi]$ are bipartite, I've tried using:

* [Kőnig's theorem](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)). So here I would need to show that for $\mathbf{G}\_V[\phi]$ (or $\mathbf{G}\_V[\lnot\phi]$), there is no vertex cover of size less that $|\phi|/2$ (since the set of all subsets in $\phi$ of even size is obviously a vertex cover of $\mathbf{G}\_V[\phi]$).
* [Hall's mariage theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation). Here I would need to show that, for every subset $B$ of $\phi$ containing only subsets of even size, the subsets of $B$ are (collectively) adgacent to at least $|B|$ vertices in $\mathbf{G}\_V[\phi]$.

with no luck so far. I should add that I don't have any particular reason for why this should be true, but this came to me as an intriguing question while I was working on something else.

**Tags:** boolean-functions, matching, monotone

> **Comments:**
> **username_1**: Do you have a higher definition version of the second image so that we can read it? Also, is $\phi$ the vertices colored in green, or the others?  
> **username_0**: I updated the figures, thanks. Yes, $\phi$ is the colored vertices (but it doesn't really matter if we consider $\phi$ or its negation).  
> **username_2**: Random suggestions: (1) To show that a bipartite graph (as you have here), has a matching, it suffices to show that it has a fractional matching (an assignment of non-negative weights to the edges so that each vertex's edges have total weight 1).  Sometimes this is easier. (2) Is it possible that a positive answer to your question would resolve (notoriously hard) open questions about Sperner properties of lattices?  That would be evidence that it may be hard to answer.  
> **username_0**: Many thanks! It gave me an idea to solve it (though not really related to fractional matchings), I'll check the details when I'll have some time (and I'll also edit my question to mention (1) as a possibility). Can you point to a reference on these open questions about Sperner properties of lattices?  
> **username_3**: I would just like to point out that this (otherwise very nice) question has nothing to do with satisfying Boolean functions, as it is equivalent to the following. If for some downwards closed $\mathcal F \subset \{0,1\}^n$ we have $\sum_{F\in\mathcal F} (-1)^{|F|}=0$, then is there a perfect matching in $\mathcal F$ or $\{0,1\}^n\setminus \mathcal F$?  
> **username_4**: @NealYoung Do you have an example of (1) in mind? I saw this method being used in a talk I went to recently, but the example was rather complicated.  
> **username_2**: Sure.  Any bipartite graph where each vertex has the same degree $d$, has a fractional matching where every edge has weight $1/d$.  Hence, it has a perfect matching.  As for Sperner, I had in mind the question of whether the lattice formed by ideals of the Boolean lattice has the Sperner property.  See e.g. https://escholarship.org/uc/item/8wh6f7rc .  
> **username_0**: (My idea did not work in the end.) @username_3: yes, this is another way of formulating it  

---

## 0 answers

