17
$\begingroup$

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):not monotone $\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 $\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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – a3nm Apr 2 at 22:30
  • $\begingroup$ I updated the figures, thanks. Yes, $\phi$ is the colored vertices (but it doesn't really matter if we consider $\phi$ or its negation). $\endgroup$ – M.Monet Apr 3 at 14:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Neal Young Apr 18 at 16:47
  • $\begingroup$ 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? $\endgroup$ – M.Monet Apr 18 at 23:42
  • 1
    $\begingroup$ 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. escholarship.org/uc/item/8wh6f7rc . $\endgroup$ – Neal Young Apr 20 at 12:05

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.