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$
0

3 Answers 3

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$
1
  • $\begingroup$ I'm definitely gonna need to read this more carefully later, but enjoy the green checkmark $\endgroup$ Commented Jul 31, 2017 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$
2
  • $\begingroup$ An example would help $\endgroup$ Commented Jul 28, 2017 at 10:32
  • $\begingroup$ I'm not sure I understand the procedure $\endgroup$ Commented Jul 30, 2017 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .