8
$\begingroup$

Let $A$ be a collection of subsets of $\{1,2,\dots,n\}$ that is closed under taking subsets (that is, if $U\in A$ and $V\subseteq U$ then $V\in A$). Is there always an involution $f:A\to A$ such that $f(V)\cap V=\emptyset$ for all $V\in A$? I'm guessing yes.

Note that if $A=\mathcal P(\{1,2,\dots,n\})$, then taking the complement works. Also note that if $|A|$ is odd, we can send the empty set to itself (the empty set is disjoint from itself, isn't that weird?).

I tried working through a few small examples. I haven't found a counterexample, but I also haven't found a proof.

$\endgroup$
2
$\begingroup$

Here's a proof which gives an algorithm for constructing an involution. If the order ideal $\mathcal{A}=\emptyset$ we're done; otherwise we can select a maximal element $X$ of $\mathcal{A}$ (with respect to inclusion.) If we're really lucky, there is another maximal element $Y$ of $\mathcal{A}$ disjoint from $X$. If so, we can set $X\leftrightarrow Y$; since $\mathcal{A}'=\mathcal{A}\setminus\{X,Y\}$ is an order ideal, we can find a suitable involution on $\mathcal{A}'$ by induction on $|\mathcal{A}|$, so we're done.

In general, we won't be so lucky, but the intuition is the same. Given a maximal element $X$ of $\mathcal{A}$, select a maximal element $Y$ in $\{ Y\in \mathcal{A}\mid Y\cap X=\emptyset \}.$ We can pair $X$ with $Y$, but in general $Y$ is not maximal in $\mathcal{A}$ so we have to do a little more work before we can appeal to induction. By the choice of $Y$, every set in $\mathcal{A}$ containing $Y$ has the form $Y\cup B$ for some $B\subset X$. Let $$\mathcal{B} =\{B\subset X\mid Y\cup B\in\mathcal{A}\};$$ note that $\mathcal{B}$ is closed under taking subsets since $\mathcal{A}$ is.

For each $B\in\mathcal{B}$, we pair $Y\cup B$ with $X\setminus B$ (which we know is in $\mathcal{A}$ since $\mathcal{A}$ is an order ideal.) In short, this matches the elements of $Y\cup\mathcal{B}$ with the elements of $X\setminus\mathcal{B}$. Let $\mathcal{A}'$ be the result of removing all these paired elements from $\mathcal{A}$. Once we check $\mathcal{A}'$ is an order ideal, we're done by induction.

All we need to check is that the set of elements we removed is an order coideal of $\mathcal{A}$. (i.e. if we removed $Z$, and $W\supset Z$ is in $\mathcal{A}$, then we also removed $W$). But $Y\cup \mathcal{B}$ is an order coideal by construction; $X\setminus\mathcal{B}$ is one since $\mathcal{B}$ is an order ideal; and the union of order coideals is an order coideal. So $\mathcal{A}'$ is an order ideal, and we're done by induction. $\square$

Remark: if $\mathcal{A}$ is the power set of $X$, then $X$ is the unique maximal element of $\mathcal{A}$; the algorithm picks $Y=\emptyset$, and pairs each $B$ with the complement $X\setminus B$, so this generalizes the special case pointed out in the original post. It also generalizes the special case at the beginning of the post: if $Y$ is maximal in $\mathcal{A}$ then $\mathcal{B}=\emptyset.$

$\endgroup$
  • $\begingroup$ I'm definitely gonna need to read this more carefully later, but enjoy the green checkmark $\endgroup$ – Akiva Weinberger Jul 31 '17 at 3:37
1
$\begingroup$

I don't know the answer, but I'd like to rephrase the question in the language of graph theory. Given a finite set $X$, the powerset $\mathcal{P}(X)$ becomes the vertex set of a graph by declaring that two subsets of $X$ have an edge between them iff they're disjoint. Furthermore, the graph $\mathcal{P}(X)$ has a perfect matching, given by complementation. Your question is whether it's true that for each downward-closed subset $\mathcal{A}$ of the poset $\mathcal{P}(X)$, the graph induced on $\mathcal{A}$ has a perfect matching.

In light of this, perhaps Tutte's theorem will help.

$\endgroup$
0
$\begingroup$

For any $A$ start with the smallest powerset that includes $A$ (e.g. if $A=\{\emptyset,\{1\},\{2\}\}$ start with $\mathcal P(\{1,2\})$). Use the trivial involution you suggested for this power set. Then transform this involution to a new involution by eliminating elements one by one to reach $A$ (start with bigger elements). In doing so alternate between reassigning $\emptyset$ to itself and the element that is mapped to the eliminated element. This way you can construct an involution for any $A$. You need to prove that the required conditions are preserved under these transformations. Note that each transformation is applied on the previous transformed involution.

$\endgroup$
  • $\begingroup$ An example would help $\endgroup$ – Akiva Weinberger Jul 28 '17 at 10:32
  • $\begingroup$ I'm not sure I understand the procedure $\endgroup$ – Akiva Weinberger Jul 30 '17 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.