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 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.
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):
$\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):
$\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 (an 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. 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. 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.
