Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ is only polynomially larger than $s(f)$. What about the opposite direction? What is known about functions where $s(f) = bs(f)$?
Trivially, constant functions have $0=s(f)=bs(f)$. Also trivially, any function with $s(f) = n$ also has $s(f) = bs(f)$. It is non-trivial but not too hard to show that any monotone function also satisfies this equality. Are there any other nice classes of functions that have $s(f) = bs(f)$? A complete characterization would be ideal. What if we further strengthen the requirements to $s^0(f) = bs^0(f)$ and $s^1(f) = bs^1(f)$?
The motivation for this question is simply to get some intuition for how sensitivity relates to block sensitivity.
Definitions
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function on $n$-bit words. For $x \in \{0,1\}^n$ and $A \subseteq \{1,\ldots,n\}$, let $x^A$ denote the $n$-bit word obtained from $x$ by flipping the bits specified by $A$. In the case that $A = \{i\}$, we will simply denote this as $x^i$.
We define the sensitivity of $f$ at $x$ as $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$. In other words, it is the number of bits in $x$ that we can flip in order to flip the output of $f$. We define the sensitivity of $f$ as $s(f) = \text{max}_x s(f,x)$.
We define the block sensitivity of $f$ at $x$ (denoted $bs(f,x)$) as the maximum $k$ such that there are disjoint subsets $B_1, B_2, \ldots, B_k$ of $\{1,2,\ldots, n\}$ such that $f(x^{B_i}) \neq f(x)$. We define the block sensitivity of $f$ as $bs(f) = \text{max}_x bs(f,x)$.
Finally, we define the 0-sensitivity of $f$ as $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$. We similarly define 1-sensitivity, 0-block sensitivity, and 1-block sensitivity , denoted $s^1(f)$, $bs^0(f)$, and $bs^1(f)$, respectively.
