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



Characterization of monotone boolean functions with minimum number of extremal points
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:


1. $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}$.
2. $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$.


