TAOCP 7.1.1 Exercise 65
Let $[n]={1,2,\ldots,n}$.
Exercise 65. ▶ [M21] [M21] Any subset $X$ of ${1, 2, \ldots, n}$ corresponds to a binary vector $x = x_1 x_2 \ldots x_n$ via the rule $x_j = [j \in X]$. And every family $\mathcal{F}$ of such subsets corresponds to a Boolean function $f(x) = f(x_1, x_2, \ldots, x_n)$ of $n$ variables, via the rule $f(x) = [X \in \mathcal{F}]$. Therefore
every statement about families of subsets corresponds to a statement about Boolean functions, and vice versa.
A family $\mathcal{F}$ is called intersecting if $X \cap Y \ne \emptyset$ whenever $X, Y \in \mathcal{F}$. An intersecting family that loses this property whenever we try to add another subset is said to be maximal. Prove that $\mathcal{F}$ is a maximal intersecting family if and only if the corresponding Boolean function $f$ is monotone and self-dual.
Verified: yes
Solve time: 1m09s
Solution
Let $[n]={1,2,\ldots,n}$. For $X\subseteq [n]$, define its characteristic vector $x=x_1x_2\cdots x_n$ by $x_j=[j\in X]$. Let $\mathcal{F}$ be a family of subsets of $[n]$ and let $f(x)=[X\in\mathcal{F}]$.
For a vector $x$, write $\bar{x}$ for the componentwise complement, corresponding to the set complement $[n]\setminus X$.
($\Rightarrow$) Maximal intersecting implies monotone and self-dual
Assume $\mathcal{F}$ is intersecting and maximal.
Monotonicity
Let $X\in\mathcal{F}$ and $X\subseteq Y$. Suppose $Y\notin\mathcal{F}$. By maximality of $\mathcal{F}$, there exists $Z\in\mathcal{F}$ such that $Z\cap Y=\emptyset$.
From $X\subseteq Y$, it follows that $Z\cap X=\emptyset$. This contradicts that $\mathcal{F}$ is intersecting. Hence $Y\in\mathcal{F}$. Therefore $f(x)=1$ and $x\le y$ imply $f(y)=1$, so $f$ is monotone.
Self-duality
Let $X\subseteq [n]$. The sets $X$ and $[n]\setminus X$ are disjoint, so they cannot both lie in $\mathcal{F}$.
It remains to show that they cannot both be absent. Assume $X\notin\mathcal{F}$ and $[n]\setminus X\notin\mathcal{F}$. By maximality applied to $X$, there exists $Y\in\mathcal{F}$ such that $Y\cap X=\emptyset$, hence $Y\subseteq [n]\setminus X$.
By maximality applied to $[n]\setminus X$, there exists $Z\in\mathcal{F}$ such that $Z\cap ([n]\setminus X)=\emptyset$, hence $Z\subseteq X$.
Then $Y\subseteq [n]\setminus X$ and $Z\subseteq X$ imply $Y\cap Z=\emptyset$, contradicting that $\mathcal{F}$ is intersecting.
Thus exactly one of $X$ and $[n]\setminus X$ lies in $\mathcal{F}$. Hence
$f(x)=1-f(\bar{x}),$
so $f$ is self-dual.
($\Leftarrow$) Monotone and self-dual implies maximal intersecting
Assume $f$ is monotone and self-dual.
Intersecting
Let $X,Y\in\mathcal{F}$. Suppose $X\cap Y=\emptyset$. Then $Y\subseteq [n]\setminus X$, so by monotonicity $f([n]\setminus X)=1$. By self-duality, $f(X)=0$, contradicting $X\in\mathcal{F}$. Hence $X\cap Y\neq\emptyset$.
Maximality
Let $X\notin\mathcal{F}$. Then $f(x)=0$, so by self-duality $f(\bar{x})=1$, hence $[n]\setminus X\in\mathcal{F}$.
Since $X\cap ([n]\setminus X)=\emptyset$, adding $X$ to $\mathcal{F}$ destroys the intersecting property. Therefore $\mathcal{F}$ is maximal intersecting.
The two directions establish the equivalence between maximal intersecting families and Boolean functions that are monotone and self-dual. This completes the proof. ∎