Signed set

The number of signed subsets of a given finite set of ${\displaystyle n}$ elements is ${\displaystyle 3^{n}}$, a power of three, because there are three choices for each element: it may be absent from the subset, present with positive sign, or present with negative sign.[5] For the same reason, the number of signed subsets of cardinality ${\displaystyle r}$ is

${\displaystyle 2^{r}{\binom {n}{r}},}$

and summing these gives an instance of the binomial theorem,

${\displaystyle \sum _{r}2^{r}{\binom {n}{r}}=3^{n}.}$

An analogue of the Erdős–Ko–Rado theorem on intersecting families of sets holds also for signed sets. The intersection of two signed sets is defined to be the signed set of elements that belong to both and have the same sign in both. According to this theorem, for any a collection of signed subsets of an ${\displaystyle n}$-element set, all having cardinality ${\displaystyle r}$ and all pairs having a non-empty intersection, the number of signed subsets in the collection is at most

${\displaystyle 2^{r-1}{\binom {n-1}{r-1}}.}$

For instance, an intersecting family of this size can be obtained by choosing the sign of a single fixed element, and taking the family to be all signed subsets of cardinality ${\displaystyle r}$ that contain this element with this sign. For ${\displaystyle r\leq n/2}$ this theorem follows immediately from the unsigned Erdős–Ko–Rado theorem, as the unsigned versions of the subsets form an intersecting family and each unsigned set can correspond to at most ${\displaystyle 2^{r-1}}$ signed sets. However, for larger values of ${\displaystyle r}$ a different proof is needed.[3]