The set of complements equal to the complement of set

Question

Consider $A \subset \{0,1\}^n$

I want $A$ to have two properties.

$1.$ $A$ is increasing, i.e., If $x \in A$ and $x \subseteq y$ then $y \in A$ too.

[$x \subseteq y$ means that every coordinate of $y$ is greater that or equal to corresponding coordinate of $x$]

$2.$ $A^c$ is equal to set $B=\{x \mid x^c \in A\}$

Is there any characterization for such a set? I have to example for it. But I want to find an IFF condition for such sets...

$e1)$ $A=\{x|$ first coordinate of $x$ is $1\}$

$e2)$ Fix an odd number of coordinates. $A= \{x\mid x$ contains at least half of coordinates equal to $1\}$

[For even number there is a similar example]

---

P.S. Asked It before Here: https://math.stackexchange.com/questions/2135708/when-set-of-complements-is-equal-to-complement-of-set

Answer 1

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects every element of $A$ and hence belongs to $A$.

Another characterization that follows easily from the one above but only works for finite $n$: A family $A$ satisfies $1$ and $2$ if and only if $A$ is intersecting and $|A|=2^{n-1}$.

Answer 2

This sounds like an ultrafilter without the intersection condition. So while I don't know if it already has a name, you could call it an ultra-upset (as opposed to downset) or ultra-final segment.

Answer 3

Although Emil Jeřábek is certainly right in that these, as Bjørn Kjos-Hanssen called them, ultraupsets, seem to be quite complicated, I would like to propose a combinatoric-topological reformulation which I think makes them more "touchable".

If we switch to complements, we are looking at abstract simplicial complexes with a very special property - they contain exactly one from each pair of complementary simplices.

It seems that some of the consequences can be more easily understood with the aid of this geometric intuition. In particular one can visualize such complexes in low dimensions.

Among subcomplexes of an 1-simplex, only single points are possible.

For subcomplexes of a triangle, there are two possibilities: an edge of the triangle, and the discrete 3-element set of its vertices.

For a tetrahedron, one has three (up to isomorphism) possibilities: a 2-face, the disjoint union $($boundary of a triangle$)\cup($point$)$, and three edges meeting at a vertex.

For a 4-simplex one gets:

• a 3-face;
• disjoint union $($boundary of a tetrahedron$)\cup($point$)$;
• two kinds of complexes with 7 edges:

and

• a complex with 8 edges

• one with 9 edges

• and the whole 1-skeleton.

All in all this seems to be a very interesting combinatorial object.