Characterization of monotone boolean functions with minimum number of extremal points Let $B = \{ 0, 1 \}$. For two points $\textbf{x}, \textbf{y} \in B^n$ we will write $\textbf{x} \preceq \textbf{y}$ iff $\textbf{x}_i \leq \textbf{y}_i$ for every $i \in \{ 1, \ldots, n \}$.
A boolean function $f: B^n \rightarrow B$ is called monotone if $f(\textbf{x}) \leq f(\textbf{y})$, whenever $\textbf{x} \preceq \textbf{y}$.
For a monotone boolean function $f: B^n \rightarrow B$ a point $\textbf{x} \in B^n$ is called a maximal zero of $f$, if $f(\textbf{x}) = 0$ and $f(\textbf{y}) = 1$ for every $\textbf{y}$ such that $\textbf{x} \prec \textbf{y}$. Similarly, $\textbf{x}$ is called a minimal one of $f$, if $f(\textbf{x}) = 1$ and $f(\textbf{y}) = 0$ for every $\textbf{y}$ such that $\textbf{y} \prec \textbf{x}$. A point $\textbf{x}$ is called an extremal point of $f$ if it is either maximal zero or minimal one of $f$.
If a monotone function $f: B^n \rightarrow B$ essentially depends on all its coordinates (variables), then $f$ has at least $n+1$ extremal points.
I'm wondering if there is a characterization of monotone boolean functions of $n$-variables (dependeing on all its variables) which have minimum possible number of extremal points, namely, $n+1$.
 A: Lemma
The set of functions with the minimum number of extremal points is closed under fixing variables.
That is, if $f\colon B^n\to B$ essentially depends on $k$ variables and has exactly $k+1$ extremal points,
then for each index $i$ and each $a\in\{0,1\}$, the function
$f_{i\mapsto a}\colon B^n\to B$ defined by
$$f_{i\mapsto a}(\textbf x) = (x_1,\dots,x_{i-1},a,x_{i+1},\dots,x_n)$$
has exactly $k'+1$ extremal points, where $k'$ is the number of variables that $f_{i\mapsto a}$ essentially depends on.
Proof.
We will prove a stronger version of the $k+1$ lower bound, then finally examine the induction to see where the lower bound is attained. The induction hypothesis is that if $f$ depends on each variable in a set $S$, then there are at least $|S|+1$ extremal points $\mathbf x$ of $f$ that happen to "witness" $S$ in the sense that $x_i=f(\mathbf x)$ for some $i\in S$. For $|S|=1$ this is easy, and we invoke induction on $|S|$.
Pick any $i\in S$. Let $S_0$ and $S_1$, respectively, denote the set of variables in $S$ that $f_{i\mapsto 0}$ and $f_{i\mapsto 1}$ essentially depend on. There are two cases:


*

*$S_1\setminus S_0$ is non-empty.
Note $|S_0\cup S_1|=|S|-1$. $f_{i\mapsto 0}$ has at least $|S_0|+1$ extremal points witnessing $S_0$, and $f_{i\mapsto 1}$ has at least $|S_1\setminus S_0|+1$ extremal points witnessing $S_1\setminus S_0$. These correspond as follows to distinct extremal points of $f$ witnessing $S$, giving at least $|S|+1$ in total.
The extremal points of $f_{i\mapsto 0}$ give extremal points of $f$ by setting $x_i=0$, except for those maximal zeros where $x_i=1$ gives a larger zero. Similarly the extremal points of $f_{i\mapsto 1}$ give extremal points of $f$ by setting $x_i=1$, except for those minimal ones where $x_i=0$ gives a smaller one. The extremal points coming from $f_{i\mapsto 0}$ do NOT witness $S_1\setminus S_0$, so do not clash with the extremal points coming from $f_{i\mapsto 1}$.

*$S_1\subseteq S_0$.
As in Case 1 we get $|S_0|+1$ extremal points witnessing $S_0$ coming from $f_{i\mapsto 0}$. All the minimal ones produced in this way have $x_i=0$. Since $f$ essentially depends on $i$, there is a minimal one $\mathbf x$ with $x_i=1$. In total this gives at least $|S_0|+2=|S|+1$ extremal points witnessing $S$.
In both cases we have shown that $f$ has at least $|S|+1$ extremal points witnessing $S$.
Finally, note that if $f$ has exactly $|S|+1$ extremal points, all the above inequalities must become equalities. So $f_{i\mapsto 0}$ has exactly $|S_0|+1$ extremal points, and by a similar argument $f_{i\mapsto 1}$ has exactly $|S_1|+1$ extremal points. This proves the Lemma by taking $S$ to be the set of all variables that $f$ essentially depends on.
Theorem
If $f\colon B^n\to B$ essentially depends on $k$ variables and has exactly $k+1$ extreme points then it is of the form
$$f(\textbf x)=R_1(x_{r(1)}, R_2(x_{r(2)}, \dots, R_{k-1}(x_{r(k-1)}, x_{r(k)})\dots))\tag{*}$$
where each operation $R_i$ is either AND or OR, and $1\leq r(1),\dots,r(k)\leq n$ are distinct indices.
Remark
Conversely any function of this form essentially depends on $k$ variables and has exactly $k+1$ extreme points.
Proof:
We will use induction on $k$. If $f$ has a zero of Hamming weight $n-1$, or a one of Hamming weight $1$, then we're done. For example if $f(0,1,\dots,1)=0$, then $f$ is of the form $\textrm{AND}(x_1,g(x_2,\dots,x_n))$. So we may assume $f(\mathbf x)=0$ for all $\mathbf x$ of Hamming weight 1, and $f(\mathbf x)=1$ for all $\mathbf x$ of Hamming weight $n-1$.
By the Lemma and induction, we can assume that every function of the form $f_{i\mapsto a}$ (with $f$ depending essentially on $i$) has a zero of Hamming weight $n-1$ or a one of Hamming weight $1$. The only way this can happen is for $f_{i\mapsto 1}$ to have a one of Hamming weight $1$, and $f_{i\mapsto 0}$ to have a zero of Hamming weight $n-1$.
So for each $i$ there exists $j$ such that $f(\mathbf x)=1$ where $x_i=x_j=1$ and $x_k=0$ for $k\notin\{i,j\}$. This gives at least $\lceil k/2\rceil$ ones of Hamming weight $2$. A similar argument gives at least $\lceil k/2\rceil$ zeroes of Hamming weight $n-2$. Because $2(\lceil k/2\rceil + 1)>k+1$, one of these inequalities must be an equality. Assume we have $\lceil k/2\rceil$ ones of Hamming weight $2$, and $\lfloor k/2\rfloor+1$ zeros of Hamming weight $n-2$. This is without loss of generality since we can replace $f$ by $1−f(1−x_1,\dots,1−x_n)$ if necessary.
If $k$ is even then, permuting variables if necessary, $f$ is of the form
$$f(x_1,\dots,x_n)=(x_1\wedge x_2)\vee (x_3\wedge x_4)\vee\dots\vee(x_{k-1}\wedge x_k).$$
But this function has exactly $2^{k/2}$ minimal zeroes ($x_1\neq x_2$ etc), and $2^{k/2} > k/2+1$ for $k\geq 4$ (the $k=2$ case is obvious).
If $k$ is odd then, permuting variables if necessary, $f$ is of the form
$$f(x_1,\dots,x_n)=(x_1\wedge x_2)\vee (x_3\wedge x_4)\vee\dots\vee(x_{k-2}\wedge x_{k-1})\vee(x_{k}\wedge x_{1}).$$
For $k=3$, by distributivity this is $x_1\wedge (x_2\vee x_3)$ which has a minimal zero of Hamming weight $1$. For $k\geq 5$ this function has exactly $2^{(k-1)/2}$ minimal zeroes, and $2^{(k-1)/2} > (k-1)/2+1$.
